The Fourier Entropy-Influence conjecture holds for a log-density 1 class of cryptographic Boolean functions

Sugata Gangopadhyay; Pantelimon Stanica

eprint.iacr.org will be offline for approximately an hour for routine maintenance at 11pm UTC on Tuesday, April 16. We lost some data between April 12 and April 14, and some authors have been notified that they need to resubmit their papers.

Paper 2014/054

The Fourier Entropy-Influence conjecture holds for a log-density 1 class of cryptographic Boolean functions

Sugata Gangopadhyay and Pantelimon Stanica

Abstract

We consider the Fourier Entropy-Influence (FEI) conjecture in the context of cryptographic Boolean functions. We show that the FEI conjecture is true for the functions satisfying the strict avalanche criterion, which forms a subset of asymptotic log--density~$1$ in the set of all Boolean functions. Further, we prove that the FEI conjecture is satisfied for plateaued Boolean functions, monomial algebraic normal form (with the best involved constant), direct sums, as well as concatenations of Boolean functions. As a simple consequence of these general results we find that each affine equivalence class of quadratic Boolean functions contains at least one function satisfying the FEI conjecture. Further, we propose some ``leveled'' FEI conjectures.

Metadata

Available format(s): PDF
Category: Foundations
Publication info: Preprint. MINOR revision.
Keywords: Boolean functions Fourier and Walsh-Hadamard transforms entropy influence
Contact author(s): pstanica @ nps edu
History: 2014-01-26: received
Short URL: https://ia.cr/2014/054
License: CC BY

BibTeX

@misc{cryptoeprint:2014/054,
      author = {Sugata Gangopadhyay and Pantelimon Stanica},
      title = {The Fourier Entropy-Influence conjecture holds for a log-density 1 class of cryptographic Boolean functions},
      howpublished = {Cryptology ePrint Archive, Paper 2014/054},
      year = {2014},
      note = {\url{https://eprint.iacr.org/2014/054}},
      url = {https://eprint.iacr.org/2014/054}
}