Cryptology ePrint Archive: Report 2000/050

Spectral Analysis of High Order Correlation Immune Functions

Yuriy Tarannikov and Denis Kirienko

Abstract: We use the recent results on the spectral structure of correlation immune and resilient Boolean functions for the investigations of high order correlation immune functions. At first, we give simple proofs of some theorems where only long proofs were known. Next, we introduce the matrix of nonzero Walsh coefficients and establish important properties of this matrix. We use these properties to prove the nonexistence of some high order correlation immune functions. Finally, we establish the order of magnitude for the number of (n-4)th order correlation immune functions of n variables.

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

Date: received 6 Oct 2000, revised 17 Oct 2000

Contact author: yutaran at mech math msu su

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

Version: 20001017:081734 (All versions of this report)

Short URL: ia.cr/2000/050

Discussion forum: Show discussion | Start new discussion