Nonlinearity measures of random Boolean functions

DOI10.1007/S12095-015-0164-3zbMATH Open1386.94121arXiv1308.3112OpenAlexW2136871609MaRDI QIDQ301648FDOQ301648

Authors: Kai-Uwe Schmidt 

Publication date: 1 July 2016

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

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.

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

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

zbMATH Keywords

convergenceBoolean functionnonlinearityReed-muller code

Mathematics Subject Classification ID

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

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Title not available (Why is that?)
• Distribution of Boolean functions according to the second-order nonlinearity
• Title not available (Why is that?)
• Non-linear approximations in linear cryptanalysis
• Title not available (Why is that?)
• Asymptotic nonlinearity of Boolean functions
• Title not available (Why is that?)
• Sur la non-linéarité des fonctions booléennes
• On the distribution of Boolean function nonlinearity
• Weight Distribution and List-Decoding Size of Reed–Muller Codes

Cited In (12)

• Power laws variance scaling of Boolean random varieties
• Limit distribution of the Hamming distance from the random Boolean function to the set of affine functions
• \(r\)-th order nonlinearity, correlation measure and least significant bit of the discrete logarithm
• Error-correction capability of Reed-Muller codes
• 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
• Distribution of Boolean functions according to the second-order nonlinearity
• Nonlinearity of functions constructed from de Bruijn sequences
• On the distribution of Boolean function nonlinearity
• Title not available (Why is that?)
• Periodic autocorrelation of sequences
• Nonlinearity statistical properties of Boolean function restrictions on a randomly chosen subspace

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)