Paper 2018/284

Hadamard Matrices, $d$-Linearly Independent Sets and Correlation-Immune Boolean Functions with Minimum Hamming Weights

Qichun Wang

Abstract

It is known that correlation-immune (CI) Boolean functions used in the framework of side channel attacks need to have low Hamming weights. In 2013, Bhasin et al. studied the minimum Hamming weight of $d$-CI Boolean functions, and presented an open problem: the minimal weight of a $d$-CI function in $n$ variables might not increase with $n$. Very recently, Carlet and Chen proposed some constructions of low-weight CI functions, and gave a conjecture on the minimum Hamming weight of $3$-CI functions in $n$ variables. In this paper, we determine the values of the minimum Hamming weights of $d$-CI Boolean functions in $n$ variables for infinitely many $n$'s and give a negative answer to the open problem proposed by Bhasin et al. We then present a method to construct minimum-weight 2-CI functions through Hadamard matrices, which can provide all minimum-weight 2-CI functions in $4k-1$ variables. Furthermore, we prove that the Carlet-Chen conjecture is equivalent to the famous Hadamard conjecture. Most notably, we propose an efficient method to construct low-weight $n$-variable CI functions through $d$-linearly independent sets, which can provide numerous minimum-weight $d$-CI functions. Particularly, we obtain some new values of the minimum Hamming weights of $d$-CI functions in $n$ variables for $n\leq 13$. We conjecture that the functions constructed by us are of the minimum Hamming weights if the sets are of absolute maximum $d$-linearly independent. If our conjecture holds, then all the values for $n\leq 13$ and most values for general $n$ are determined.

Metadata
Available format(s)
PDF
Publication info
Preprint. MINOR revision.
Keywords
Boolean functionsCorrelation-immuneMinimum-weightHadamard matrices$d$-linearly independent sets
Contact author(s)
qcwang @ fudan edu cn
History
2018-03-23: received
Short URL
https://ia.cr/2018/284
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/284,
      author = {Qichun Wang},
      title = {Hadamard Matrices, $d$-Linearly Independent Sets and Correlation-Immune Boolean Functions with Minimum Hamming Weights},
      howpublished = {Cryptology ePrint Archive, Paper 2018/284},
      year = {2018},
      note = {\url{https://eprint.iacr.org/2018/284}},
      url = {https://eprint.iacr.org/2018/284}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.