Cryptology ePrint Archive: Report 2000/049

Spectral Domain Analysis of Correlation Immune and Resilient Boolean Functions

Palash Sarkar

Abstract: In this paper we prove a general result on the Walsh Transform of an arbitrary Boolean function. As a consequence, we obtain several divisibility results on the Walsh Transform of correlation immune and resilient Boolean functions. This allows us to improve upper bounds on the nonlinearity of correlation immune and resilient Boolean functions. Also we provide new necessary conditions on the algebraic normal form of correlation immune/resilient functions attaining the maximum possible nonlinearity.

Category / Keywords: secret-key cryptography / Boolean function, correlation immunity, resiliency, nonlinearity, Walsh Transform

Date: received 26 Sep 2000

Contact author: psarkar at cacr math uwaterloo ca

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

Version: 20000926:221420 (All versions of this report)

Short URL: ia.cr/2000/049

Discussion forum: Show discussion | Start new discussion