International Association for Cryptologic Research

International Association
for Cryptologic Research


Paper: New Directions in Design of Resilient Boolean Functions

Palash Sarkar
Subhamoy Maitra
Search ePrint
Search Google
Abstract: There has been a recent upsurge of research in the design of resilient Boolean functions for use in stream cipher systems. The existing research concentrates on maximum degree resilient functions and tries to obtain as high nonlinearity as possible. In sharp contrast to this approach we identify the class of functions with {\em provably best} possible trade-off among the parameters: number of variables, resiliency, nonlinearity and algebraic degree. We first prove a sharper version of McEliece theorem for Reed-Muller codes as applied to resilient functions, which also generalizes the well known Xiao-Massey characterization. As a consequence a nontrivial upper bound on the nonlinearity of resilient functions is obtained. This result coupled with Siegenthaler's inequality naturally leads to the notion of provably best resilient functions. We further show that such best functions can be constructed by the Maiorana-McFarland like technique. In cases where this method fails, we provide new ideas to construct best functions. We also briefly discuss efficient implementation of these functions in hardware.
  title={New Directions in Design of Resilient Boolean Functions},
  booktitle={IACR Eprint archive},
  keywords={secret-key cryptography / Boolean functions, Balancedness, Algebraic Degree, Nonlinearity, Correlation Immunity, Resiliency, Stream Ciphers, Combinatorial Cryptography},
  note={ 11039 received 22 Mar 2000},
  author={Palash Sarkar and Subhamoy Maitra},