Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality

An Braeken; Christopher Wolf; Bart Preneel

Paper 2004/214

Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality

An Braeken, Christopher Wolf, and Bart Preneel

Abstract

A Boolean function is called normal if it is constant on flats of certain dimensions. This property is relevant for the construction and analysis of cryptosystems. This paper presents an asymmetric Monte Carlo algorithm to determine whether a given Boolean function is normal. Our algorithm is far faster than the best known (deterministic) algorithm of Daum et al. In a first phase, it checks for flats of low dimension whether the given Boolean function is constant on them and combines such flats to flats of higher dimension in a second phase. This way, the algorithm is much faster than exhaustive search. Moreover, the algorithm benefits from randomising the first phase. In addition, by evaluating several flats implicitly in parallel, the time-complexity of the algorithm decreases further. As an application, we determine the level of normality for several, highly nonlinear Boolean power functions.

Metadata

Available format(s): PDF PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: boolean functions normality power-functions Monte Carlo
Contact author(s): Christopher Wolf @ esat kuleuven ac be
History: 2005-04-15: last of 5 revisions; 2004-08-30: received; See all versions
Short URL: https://ia.cr/2004/214
License: CC BY

BibTeX

@misc{cryptoeprint:2004/214,
      author = {An Braeken and Christopher Wolf and Bart Preneel},
      title = {Classification of Highly Nonlinear Boolean Power Functions with a Randomised Algorithm for Checking Normality},
      howpublished = {Cryptology {ePrint} Archive, Paper 2004/214},
      year = {2004},
      url = {https://eprint.iacr.org/2004/214}
}