zbMATH — the first resource for mathematics

On cryptographic properties of the cosets of \(R(1,m)\). (English) Zbl 1021.94014
A new approach for the study of weight distribution of cosets of the Reed-Muller code of order 1 is presented. First, some algebraic properties of Boolean functions of \(m\) variables are studied; this study leads to the study of binary codewords of length \(2^m\) and their relation with Reed-Muller codes. These tools are then used to study the maximal odd-weighting subspace of a given Boolean function \(f\), a concept known to be linked with the nonlinearity of \(f\). Here also the existence of maximal odd-weighting subspaces for any \(f\) is proved.
Then, the nonlinearity of \(f\) is investigated through the properties of weight polynomials of cosets of \(R(1,m)\). General results on the weight polynomial of any binary linear code of length \(2^m\) and dimension \(m+2\) is established here as well as results for some subcases.
Finally, the propagation criterion and its relations with the nonlinearity are investigated. Besides other results, links between bent functions and three-valued almost-optimal functions are given here.

94A60 Cryptography
94B05 Linear codes, general
Full Text: DOI