Sur la non-linéarité des fonctions booléennes (Q4829485)

From MaRDI portal

!

This is the item page for this Wikibase entity, intended for internal use and editing purposes. Please use the normal view instead:

scientific article; zbMATH DE number 2120185
Language Label Description Also known as
default for all languages
No label defined
    English
    Sur la non-linéarité des fonctions booléennes
    scientific article; zbMATH DE number 2120185

      Statements

      Sur la non-linéarité des fonctions booléennes (English)
      0 references
      0 references
      29 November 2004
      0 references
      covering radius
      0 references
      error-correcting code
      0 references
      cryptography
      0 references
      nonlinearity
      0 references
      Boolean function
      0 references
      random polynomial
      0 references
      Fourier transform
      0 references
      Boolean functions on the space \(F_2^m\) have important applications in the theory of error correcting codes, specifically the Reed-Muller codes, and in cryptography, specifically in private key systems. The nonlinearity of the functions plays an important role in both applications. Inspired by the results from Salem, Zygmund and Kahane on real polynomials with random coefficients the author investigates the degree of nonlinearity of these functions. Defining the spectral amplitude of a function \(g\) by \[ S(g) = \sup_{v \in F_2^m} | \sum_{x \in F_2^m} (-1)^{g(x) + v \cdot x}| \] he shows that the degree of nonlinearity, defined by the minimum over affine functions \(h\) of \(d(g,h)\) where \(d\) is the Hamming distance, is \(2^{m-1} - \tfrac12 S(g).\) Using the spectral amplitude he is able to show that nearly all Boolean functions in \(m\) variables have nonlinearity between \(2^{m-1} - 2^{\frac{m}{2}-1} \sqrt{2m\log (2) }\) and \(2^{m-1} - 2^{\frac{m}{2} - 2}\sqrt{m \log(2)}.\) Moreover he shows that the nonlinearity is of the order of \(2^{\frac{m}{2}} \sqrt{m}.\) Two conjectures are studied. The first by Patterson and Wiedemann conjectures that the minimum of the spectral amplitude approaches \(2^{\frac{m}{2}}\) and the second concerns the moments of order 4 of their Fourier transform.
      0 references

      Identifiers

      0 references
      0 references
      0 references
      0 references
      0 references
      0 references
      0 references