Paper 2013/639

Differentially 4-Uniform Bijections by Permuting the Inverse Function

Deng Tang, Claude Carlet, and Xiaohu Tang

Abstract

Block ciphers use Substitution boxes (S-boxes) to create confusion into the cryptosystems. Functions used as S-boxes should have low differential uniformity, high nonlinearity and algebraic degree larger than 3 (preferably strictly larger). They should be fastly computable; from this viewpoint, it is better when they are in even number of variables. In addition, the functions should be bijections in a Substitution-Permutation Network. Almost perfect nonlinear (APN) functions have the lowest differential uniformity 2 and the existence of APN bijections over $\F_{2^n}$ for even $n\ge 8$ is a big open problem. In the present paper, we focus on constructing differentially 4-uniform bijections suitable for designing S-boxes for block ciphers. Based on the idea of permuting the inverse function, we design a construction providing a large number of differentially 4-uniform bijections with maximum algebraic degree and high nonlinearity. For every even $n\ge 12$, we mathematically prove that the functions in a subclass of the constructed class are CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. This is the first mathematical proof that an infinite class of differentially 4-uniform bijections is CCZ-inequivalent to known differentially 4-uniform power functions and to quadratic functions. We also get a general lower bound on the nonlinearity of our functions, which can be very high in some cases, and obtain three improved lower bounds on the nonlinearity for three special subcases of functions which are extremely large.

Metadata
Available format(s)
PDF
Category
Secret-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
block ciphersubstitution boxdifferentially 4-uniform bijectionCCZ-equivalencenonlinearity.
Contact author(s)
dtang @ foxmail com
History
2013-10-05: received
Short URL
https://ia.cr/2013/639
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/639,
      author = {Deng Tang and Claude Carlet and Xiaohu Tang},
      title = {Differentially 4-Uniform Bijections by Permuting the Inverse Function},
      howpublished = {Cryptology ePrint Archive, Paper 2013/639},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/639}},
      url = {https://eprint.iacr.org/2013/639}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.