中国科学院软件研究所机构知识库
Advanced  
ISCAS OpenIR  > 信息安全国家重点实验室  > 学位论文
学科主题: 计算机科学技术基础学科::数据安全与计算机安全
题名:
具有密码学意义的置换多项式的存在性及构造
作者: 李永强
答辩日期: 2011-11-21
导师: 王明生
专业: 信息安全
授予单位: 中国科学院研究生院
授予地点: 北京
学位: 博士
关键词: AB函数 ; APN函数 ; 置换多项式 ; EA等价 ; CCZ等价
摘要:
    S盒为对称密码算法提供了混淆作用, 并且对于很多对称密码算法, S盒是其唯一的非线性部分, 因此S盒在对称密码中起着重要的作用. 考虑到实现的高效性, 在实际应用中, S盒通常设计为$\mathbb{F}_{2^{2n}}$上的置换. S盒的优劣通常由其抵抗线性分析和差分分析的能力来衡量. 因此, 构造$\mbf_{2^{2n}}$上的具有低差分均匀度, 高非线性度的置换是密码学中一个重要的问题.
    差分均匀度, 非线性度是EA等价和CCZ等价的不变量, 但置换在这两个等价关系下并不保持. 因此, 在本文中, 我们详细讨论了从AB, APN函数出发, 利用EA等价以及CCZ等价构造$\mbf_{2^n}$上的置换多项式的可能性.
    根据EA等价的定义, 如果存在置换与$F(x)\in\mbf_{2^n}[x]$ EA等价, 则存在线性多项式$L(x)\in\mbf_{2^n}[x]$, 使得$F(x)+L(x)$是$\mbf_{2^n}$上的置换. 在第三章中, 我们详细讨论了$\mbf_{2^n}$上形如$F(x)+L(x)$的置换多项式的存在性, 得到如下结果:
    1. 当$F(x)$为幂函数时, 我们证明了对于某些特定$d$, 不存在线性多项式$L(x)\in\mbf_{2^n}[x]$, 使得$x^d+L(x)$是$\mbf_{2^n}$上的置换.
    2. 当$F(x)$为Gold函数时, 我们证明了$x^{2^i+1}+L(x)$为置换当且仅当$n$为奇数且对于某个$\alpha\in\mbf_{2^n}^{*}$, 有$L(x)=\alpha x^{2^i}+\alpha^{2^i}x$.
    3. 当$F(x)$为逆函数时, 我们证明了当$n\ge5$时, 不存在线性多项式$L(x)\in\mbf_{2^n}[x]$, 使得$x^{-1}+L(x)$是$\mbf_{2^n}$上的置换.
    4. 当$F(x)$为AB函数$x^{2^i+1}+(x^{2^i}+x)\Tr(x^{2^i+1}+x)$时, 我们证明了当$m\ge2$时, $\mbf_{2^{2m+1}}$上不存在与$F(x)$ EA等价的置换多项式.
该结果否证了Carlet在98年提出的``任意一个AB函数都EA等价于一个置换''的猜想.
    形如$L_1(F(x))+L_2(x)$的置换多项式在构造与$F(x)$ CCZ等价的函数中起着最本质的作用. 在第四章, 我们刻画了上述形式的置换多项式. 主要有如下结果:
    1. 我们给出了一个存在线性多项式$L_1(x), L_2(x)$, 使得$L_1(F(x))+L_2(x)$为置换的充分条件.
    2. 证明了对于任意的差分均匀度小于$2^n$的二次函数$F(x)\in\mbf_{2^n}[x]$, 都存在线性多项式$L_1(x), L_2(x)\in\mbf_{2^n}[x]$, 使得$L_1(F(x))+L_2(x)$是$\mbf_{2^n}$上的置换. 因此, 对于任意的二次AB, APN函数, 我们都可以构造与其CCZ等价的函数.
    3. 对于$F(x)$为Gold函数, $n$为偶数, 我们找到了所有$\ker(L)\ge2^{n-2}$的线性多项式$L(x)$, 其使得$L(x^{2^i+1})+x$是$\mbf_{2^n}$上的置换多项式.
    4. 对于逆函数, 我们也得到了部分结果.
    在第五章, 我们讨论了利用三轮Feistel结构所构造的S盒的差分均匀度, 非线性度等密码学性质. 证明了其差分均匀度大于等于$2\delta(P_2)$.
    在第六章, 我们给出了一个利用$\mbf_{2^{2m+1}}$上的二次APN置换构造$\mbf_{2^{2m}}$上具有已知最高非线性度的4差分均匀的置换的方法, 并利用Gold函数给出了几个具体的构造.
英文摘要:
    S(ubstitution)-boxes play an important role in symmetric
cryptography since they serve as the confusion part and in most cases are the only nonlinear part of round functions. For efficiency of implementations, S-boxes are often designed as permutations over $\mbf_{2^{2n}}$ in practice. The performance of these boxes is often measured by their resistance to linear and differential cryptanalysis. Therefore, constructing permutation polynomials with low differential uniformity and high nonlinearity over $\mbf_{2^{2n}}$ is of significant importance in cryptography.

    Notice that the differential uniformity and nonlinearity of
functions are invariant under EA-equivalence and CCZ-equivalence, but permutation is not. Thus, we discuss the existence of permutation polynomials EA-equivalent or CCZ-equivalent to AB and APN polynomials in detail in the thesis.

    According to the definition of EA-equivalence, if there exists a permutation polynomial EA-equivalent to $F(x)\in\mbf_{2^n}[x]$, then there exists a linear polynomial $L(x)\in\mbf_{2^n}[x]$ such that $F(x)+L(x)$ is a permutation polynomial over $\mbf_{2^n}$. In Chapter 3, we discuss the existence of permutation polynomials of the type $F(x)+L(x)$ over $\mbf_{2^n}$ and obtain main results as follows:
    1. As for power functions, we proved that for some special $d$, there are no permutations EA-equivalent to $x^d$ over $\mbf_{2^n}$.
    2. As for Gold function, we proved that $x^{2^i+1}+L(x)$ is a permutation over $\mbf_{2^n}$ if
and only if $n$ is odd and $L(x)=\alphax^{2^i}+\alpha^{2^i}x$ for some $\alpha\in\mbf_{2^n}^{*}$.
     3. As for inverse function, we proved that there do not exist linear polynomials $L(x)\in\mbf_{2^n}[x]$, such that $x^{-1}+L(x)$ is a permutation polynomial over $\mbf_{2^n}$ when $n\ge5$.
    4. As for the AB function $x^{2^i+1}+(x^{2^i}+x)\Tr(x^{2^i+1}+x)$, we proved that when
$m\ge2$, there are no permutations EA-equivalent to $F(x)$ over $\mbf_{2^{2m+1}}$. This result disproved the conjecture of ``Every AB function is EA-equivalent to a permutation'', which is raised by Carlet in 1998.

    Permutation polynomials of the type $L_1(F(x))+L_2(x)$ are essential for constructing polynomials CCZ-equivalent to $F(x)$. We characterize the permutation polynomials of the above type in Chapter 4. We obtained main results as follows:
    1. We give a sufficient condition for getting linear polynomials $L_1(x), L_2(x)\in\mbf_{2^n}[x]$ such that $L_1(F(x))+L_2(x)$ is a permutation over $\mbf_{2^n}$.
    2. We proved that for any quadratic polynomials  $F(x)\in\mbf_{2^n}[x]$ with differential uniformity less than $2^n$, there always exist linear polynomials $L_1(x),
L_2(x)\in\mbf_{2^n}[x]$, such that $L_1(F(x))+L_2(x)$ is a permutation over $\mbf_{2^n}$. Therefore, for any quadratic AB or APN functions, we always can construct AB or APN functions CCZ-equivalent to them.
    3. As for Gold functions, we get all linear polynomials with $\ker(L)\ge2^{n-2}$, such that $L(x^{2^i+1})+x$ is
a permutation over $\mbf_{2^n}$ when $n$ is even.
    4. We also get some results for inverse function.

    In chapter 5, we discuss the differential uniformity and
nonlinearity of the S-boxes constructed by using three rounds Feistel structure. We proved that their differential uniformity always large than or equal to $2\delta(P_2)$.

    In Chapter 6, we give a method for constructing differentially 4-uniform permutations with the best known nonlinearity over $\mbf_{2^{2m}}$ from quadratic APN permutations over $\mbf_{2^{2m+1}}$. Several constructions are given by using Gold functions.
内容类型: 学位论文
URI标识: http://ir.iscas.ac.cn/handle/311060/14400
Appears in Collections:信息安全国家重点实验室_学位论文

Files in This Item:
File Name/ File Size Content Type Version Access License
博士学位论文_李永强.pdf(1890KB)----限制开放 联系获取全文

Recommended Citation:
李永强. 具有密码学意义的置换多项式的存在性及构造[D]. 北京. 中国科学院研究生院. 2011-11-21.
Service
Recommend this item
Sava as my favorate item
Show this item's statistics
Export Endnote File
Google Scholar
Similar articles in Google Scholar
[李永强]'s Articles
CSDL cross search
Similar articles in CSDL Cross Search
[李永强]‘s Articles
Related Copyright Policies
Null
Social Bookmarking
Add to CiteULike Add to Connotea Add to Del.icio.us Add to Digg Add to Reddit
所有评论 (0)
暂无评论
 
评注功能仅针对注册用户开放,请您登录
您对该条目有什么异议,请填写以下表单,管理员会尽快联系您。
内 容:
Email:  *
单位:
验证码:   刷新
您在IR的使用过程中有什么好的想法或者建议可以反馈给我们。
标 题:
 *
内 容:
Email:  *
验证码:   刷新

Items in IR are protected by copyright, with all rights reserved, unless otherwise indicated.

 

 

Valid XHTML 1.0!
Copyright © 2007-2017  中国科学院软件研究所 - Feedback
Powered by CSpace