Paper 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.
Metadata
- Available format(s)
- PS
- Category
- Secret-key cryptography
- Publication info
- Published elsewhere. Unknown where it was published
- Keywords
- Boolean functionsBalancednessAlgebraic DegreeNonlinearityCorrelation ImmunityResiliencyStream CiphersCombinatorial Cryptography
- Contact author(s)
- subho @ isical ac in
- History
- 2000-03-23: received
- Short URL
- https://ia.cr/2000/009
- License
-
CC BY
BibTeX
@misc{cryptoeprint:2000/009,
author = {Palash Sarkar and Subhamoy Maitra},
title = {New Directions in Design of Resilient Boolean Functions},
howpublished = {Cryptology {ePrint} Archive, Paper 2000/009},
year = {2000},
url = {https://eprint.iacr.org/2000/009}
}
