Constructing Differentially 4-Uniform Permutations Over ${\BBF}_{2^{2k}}$ via the Switching Method
Constructing Differentially 4-Uniform Permutations Over ${\BBF}_{2^{2k}}$ via the Switching Method
复制标题
DOI：
10.1109/tit.2013.2252420
复制
发表时间：
2013-07
影响因子：
2.5
通讯作者：
Longjiang Qu;Yin Tan;C. H. Tan;C. Li
中科院分区：
文献类型：
--
作者：
Longjiang Qu;Yin Tan;C. H. Tan;C. Li
许多块密码使用在低差异均匀性，高非线性和高代数度的F（22K）上定义的排列作为其S盒，以提供混乱。众所周知，对于F（2N）上的功能，最低的差异均匀性为2，而实现该下限的功能称为几乎完美的非线性（APN）函数。但是，由于缺乏对F（22K）的APN排列的知识，因此通常选择4-均匀排列的S-BoxE。例如，当前认可的高级加密标准选择一个这样的功能，即乘法逆函数，作为其S-box。通过最近对F（22K）差异4-均匀排列的调查，只有五个已知的无限族家庭，其中大多数具有较小的代数学位。在本文中，我们采用强大的切换方法来发现F（22K）上具有最佳代数程度的F（22K）上的许多CCZ授权无限族，其中k是任意的正整数。这大大扩展了差异4-均匀排列的列表，因此为S-Boxes提供了更多选择。此外，提出了本文获得的功能非线性的下限，它们暗示某些无限家庭具有很高的非线性。
Many block ciphers use permutations defined on F(22k ) with low differential uniformity, high nonlinearity, and high algebraic degree as their S-boxes to provide confusion. It is well known that, for a function on F(2n), the lowest differential uniformity is 2 and the functions achieving this lower bound are called almost perfect nonlinear (APN) functions. However, due to the lack of knowledge on APN permutations on F(22k ), differentially 4-uniform permutations are usually chosen as S-boxes. For example, the currently endorsed Advanced Encryption Standard chooses one such function, the multiplicative inverse function, as its S-box. By a recent survey on differentially 4-uniform permutations over F(22k ), there are only five known infinite families of such functions, and most of them have small algebraic degrees. In this paper, we apply the powerful switching method to discover many CCZ-inequivalent infinite families of such functions on F(22k ) with optimal algebraic degree, where k is an arbitrary positive integer. This greatly expands the list of differentially 4-uniform permutations and hence provide more choices for the S-boxes. Furthermore, lower bounds for the nonlinearity of the functions obtained in this paper are presented and they imply that some infinite families have high nonlinearity.