Paper 2017/449
Differentially 4Uniform Permutations with the Best Known Nonlinearity from Butterflies
Shihui Fu, Xiutao Feng, and Baofeng Wu
Abstract
Many block ciphers use permutations defined over the finite field $\mathbb{F}_{2^{2k}}$ with low differential uniformity, high nonlinearity, and high algebraic degree to provide confusion. Due to the lack of knowledge about the existence of almost perfect nonlinear (APN) permutations over $\mathbb{F}_{2^{2k}}$, which have lowest possible differential uniformity, when $k>3$, constructions of differentially 4uniform permutations are usually considered. However, it is also very difficult to construct such permutations together with high nonlinearity; there are very few known families of such functions, which can have the best known nonlinearity and a high algebraic degree. At Crypto'16, Perrin et al. introduced a structure named butterfly, which leads to permutations over $\mathbb{F}_{2^{2k}}$ with differential uniformity at most 4 and very high algebraic degree when $k$ is odd. It is posed as an open problem in Perrin et al.'s paper and solved by Canteaut et al. that the nonlinearity is equal to $2^{2k1}2^k$. In this paper, we extend Perrin et al.'s work and study the functions constructed from butterflies with exponent $e=2^i+1$. It turns out that these functions over $\mathbb{F}_{2^{2k}}$ with odd $k$ have differential uniformity at most 4 and algebraic degree $k+1$. Moreover, we prove that for any integer $i$ and odd $k$ such that $\gcd(i,k)=1$, the nonlinearity equality holds, which also gives another solution to the open problem proposed by Perrin et al. This greatly expands the list of differentially 4uniform permutations with good nonlinearity and hence provides more candidates for the design of block ciphers.
Metadata
 Available format(s)
 Category
 Foundations
 Publication info
 Published by the IACR in TOSC 2017 ISSUE 2
 Keywords
 SboxesAPNbutterfly structurepermutationdifferential uniformitynonlinearity
 Contact author(s)
 fushihui @ amss ac cn
 History
 20170523: received
 Short URL
 https://ia.cr/2017/449
 License

CC BY
BibTeX
@misc{cryptoeprint:2017/449, author = {Shihui Fu and Xiutao Feng and Baofeng Wu}, title = {Differentially 4Uniform Permutations with the Best Known Nonlinearity from Butterflies}, howpublished = {Cryptology ePrint Archive, Paper 2017/449}, year = {2017}, note = {\url{https://eprint.iacr.org/2017/449}}, url = {https://eprint.iacr.org/2017/449} }