Simpler proof for nonlinearity of majority function

2017/10/05 by Cusick, Thomas W.
#94A60 06E30 #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · doi:10.48550/arxiv.1710.02034

Abstract

Given a Boolean function f, the (Hamming) weight wt(f) and the nonlinearity N(f) are well known to be important in designing functions that are useful in cryptography. The nonlinearity is expensive to compute, in general, so any shortcuts for doing that for particular functions f are significant. The well known majority function has been extensively studied in a cryptographic context for the last dozen years or so, and there is a formula for its nonlinearity. The known proofs for this formula rely on many detailed results for the Krawtchouk polynomials. This paper gives a much simpler proof.

Related

• Non-linearity of the Carlet-Feng function, and repartition of Gauss sums
• On plateaued functions
• Two Boolean functions with five-valued Walsh spectra and high nonlinearity
• Weightwise perfectly balanced functions with high weightwise nonlinearity profile
• An algorithmic approach using multivariate polynomials for the nonlinearity of Boolean functions