Nonlinearity measures of random Boolean functions

DOI10.1007/S12095-015-0164-3MaRDI QIDQ301648zbMATH OpenOpenAlexFDO

Authors Kai-Uwe Schmidt

Publication date 1 July 2016

Published in Cryptography and Communications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1308.3112

zbMATH Keywords

convergenceBoolean functionnonlinearityReed-muller code

Mathematics Subject Classification ID

Convergence of probability measures (60B10) Algebraic coding theory; cryptography (number-theoretic aspects) (11T71)

Abstract: The r-th order nonlinearity of a Boolean function is the minimum number of elements that have to be changed in its truth table to arrive at a Boolean function of degree at most r. It is shown that the (suitably normalised) r-th order nonlinearity of a random Boolean function converges strongly for all rge 1. This extends results by Rodier for r=1 and by Dib for r=2. The methods in the present paper are mostly of elementary combinatorial nature and also lead to simpler proofs in the cases that r=1 or 2.

Recommendations

• Distribution of Boolean functions according to the second-order nonlinearity
• Nonlinearity statistical properties of Boolean function restrictions on a randomly chosen subspace
• On the distribution of Boolean function nonlinearity
• Sur la non-linéarité des fonctions booléennes
• scientific article; zbMATH DE number 1191206

Cites work

• scientific article; zbMATH DE number 5862915 (Why is no real title available?)
• scientific article; zbMATH DE number 4170917 (Why is no real title available?)
• scientific article; zbMATH DE number 3577144 (Why is no real title available?)
• scientific article; zbMATH DE number 1543297 (Why is no real title available?)
• scientific article; zbMATH DE number 3450812 (Why is no real title available?)
• scientific article; zbMATH DE number 3249395 (Why is no real title available?)
• Asymptotic nonlinearity of Boolean functions
• Distribution of Boolean functions according to the second-order nonlinearity
• Non-linear approximations in linear cryptanalysis
• On the distribution of Boolean function nonlinearity
• Sur la non-linéarité des fonctions booléennes
• Weight Distribution and List-Decoding Size of Reed–Muller Codes

Cited in

(14)

• Power laws variance scaling of Boolean random varieties
• Nonlinearity of functions constructed from de Bruijn sequences
• \(r\)-th order nonlinearity, correlation measure and least significant bit of the discrete logarithm
• Error-correction capability of Reed-Muller codes
• On the distribution of Boolean function nonlinearity
• On the number of the rational zeros of linearized polynomials and the second-order nonlinearity of cubic Boolean functions
• Gowers \(U_2\) norm as a measure of nonlinearity for Boolean functions and their generalizations
• Limit distribution of the Hamming distance from the random Boolean function to the set of affine functions
• Nonlinearity statistical properties of Boolean function restrictions on a randomly chosen subspace
• Periodic autocorrelation of sequences
• Improving bounds on probabilistic affine tests to estimate the nonlinearity of Boolean functions
• Distribution of Boolean functions according to the second-order nonlinearity
• Distribution of the autocorrelation of random Boolean functions
• scientific article; zbMATH DE number 5022109 (Why is no real title available?)

This page was built for publication: Nonlinearity measures of random Boolean functions

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q301648)