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.