Paper Info
Title
New Constructions of Resilient and Correlation Immune Boolean Functions Achieving Upper Bound on Nonlinearity
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 requirement in the design of resilient Boolean functions (which optimizes Siegenthaler'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 was posed 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 ≥ 0) with order of resiliency m = 2 + 2i, algebraic degree 4 + i and nonlinearity 2n-1 - 2m+1, which were not known earlier. We conclude with constructions of some unbalanced correlation immune functions of 5 and 6 variables which attain the upper bound on nonlinearity.
Year
DOI
Venue
2000
10.1016/S1571-0653(04)00167-2
Electronic Notes in Discrete Mathematics
Keywords
Field
DocType
Boolean functions,Nonlinearity,Correlation Immunity,Resiliency,Stream Ciphers
Maximum satisfiability problem,Boolean function,Discrete mathematics,Combinatorics,Algebraic number,Nonlinear system,Upper and lower bounds,Sequence,Divisibility rule,Parity function,Mathematics
Journal
Volume
ISSN
Citations 
6
1571-0653
52
PageRank 
References 
Authors
4.83
13
4
Name
Order
Citations
PageRank
Emir Pasalic119255.42
Subhamoy Maitra21753140.09
Thomas Johansson31336115.80
Palash Sarkar41505130.85