Paper 2003/198

Construction of Perfect Nonlinear and Maximally Nonlinear Multi-Output Boolean Functions Satisfying Higher Order Strict Avalanche Criteria

Kishan Chand Gupta and Palash Sarkar

Abstract

We consider the problem of constructing perfect nonlinear multi-output Boolean functions satisfying higher order strict avalanche criteria (SAC). Our first construction is an infinite family of 2-ouput perfect nonlinear functions satisfying higher order SAC. This construction is achieved using the theory of bilinear forms and symplectic matrices. Next we build on a known connection between 1-factorization of a complete graph and SAC to construct more examples of 2 and 3-output perfect nonlinear functions. In certain cases, the constructed S-boxes have optimal trade-off between the following parameters: numbers of input and output variables, nonlinearity and order of SAC. In case the number of input variables is odd, we modify the construction for perfect nonlinear S-boxes to obtain a construction for maximally nonlinear S-boxes satisfying higher order SAC. Our constructions present the first examples of perfect nonlinear and maximally nonlinear multioutput S-boxes satisfying higher order SAC. Lastly, we present a simple method for improving the degree of the constructed functions with a small trade-off in nonlinearity and the SAC property. This yields functions which have possible applications in the design of block ciphers.

Metadata
Available format(s)
PDF PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
boolean functionsblock ciphers
Contact author(s)
kishan_t @ isical ac in
History
2003-09-25: revised
2003-09-24: received
See all versions
Short URL
https://ia.cr/2003/198
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2003/198,
      author = {Kishan Chand Gupta and Palash Sarkar},
      title = {Construction of Perfect Nonlinear and Maximally Nonlinear Multi-Output Boolean Functions Satisfying Higher Order Strict Avalanche Criteria},
      howpublished = {Cryptology ePrint Archive, Paper 2003/198},
      year = {2003},
      note = {\url{https://eprint.iacr.org/2003/198}},
      url = {https://eprint.iacr.org/2003/198}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.