You are looking at a specific version 20000926:205428 of this paper. See the latest version.

Paper 2000/048

New Constructions of Resilent and Correlation Immune Boolean Functions achieving Upper Bounds on Nonlinearity

Enes Pasalic and Thomas Johansson and Subhamoy Maitra and Palash Sarkar

Abstract

Recently weight divisibility results on resilient and correlation immune Boolean functions have received a lot of attention. These results have direct consequences towards the upper bound on nonlinearity of resilient and correlation immune Boolean functions of certain order. Now the clear benchmark in the design of resilient Boolean functions (which optimizes Sigenthaler's inequality) is to provide results which attain the upper bound on nonlinearity. Here we construct a 7-variable, 2-resilient Boolean function with nonlinearity 56. This solves the maximum nonlinearity issue for 7-variable functions with any order of resiliency. Using this 7-variable function, we also construct a 10-variable, 4-resilient Boolean function with nonlinearity 480. Construction of these two functions were justified as important open questions in Crypto 2000. Also we provide methods to generate an infinite sequence of Boolean functions on $n = 7 + 3i$ variables $(i \geq 0)$ with order of resiliency $m = 2 + 2i$, algebraic degree $4 + i$ and nonlinearity $2^{n-1} - 2^{m+1}$, which were not known earlier. We conclude with a few interesting construction results on unbalanced correlation immune functions of 5 and 6 variables.

Metadata
Available format(s)
PS
Category
Secret-key cryptography
Publication info
Published elsewhere. Unknown where it was published
Keywords
boolean function
Contact author(s)
subho @ isical ac in
History
2000-09-26: received
Short URL
https://ia.cr/2000/048
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.