Cryptology ePrint Archive: Report 2000/009

New Directions in Design of Resilient Boolean Functions

Palash Sarkar and Subhamoy Maitra

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.

Category / Keywords: secret-key cryptography / Boolean functions, Balancedness, Algebraic Degree, Nonlinearity, Correlation Immunity, Resiliency, Stream Ciphers, Combinatorial Cryptography

Date: received 22 Mar 2000

Contact author: subho at isical ac in

Available format(s): Postscript (PS) | Compressed Postscript (PS.GZ) | BibTeX Citation

Version: 20000323:165950 (All versions of this report)

Short URL: ia.cr/2000/009

Discussion forum: Show discussion | Start new discussion