Welcome to the resource topic for 2018/284
Title:
Hadamard Matrices, d-Linearly Independent Sets and Correlation-Immune Boolean Functions with Minimum Hamming Weights
Authors: 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.
ePrint: https://eprint.iacr.org/2018/284
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .