Spectral Analysis of High Order Correlation Immune Functions

Yuriy Tarannikov; Denis Kirienko

Paper 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.

Metadata

Available format(s): PS
Category: Secret-key cryptography
Publication info: Published elsewhere. Unknown where it was published
Keywords: Boolean function correlation immunity resiliency Walsh Transform
Contact author(s): yutaran @ mech math msu su
History: 2000-10-17: revised; 2000-10-06: received; See all versions
Short URL: https://ia.cr/2000/050
License: CC BY

BibTeX

@misc{cryptoeprint:2000/050,
      author = {Yuriy Tarannikov and Denis Kirienko},
      title = {Spectral Analysis of High Order Correlation Immune Functions},
      howpublished = {Cryptology {ePrint} Archive, Paper 2000/050},
      year = {2000},
      url = {https://eprint.iacr.org/2000/050}
}