Paper 2007/037

Best Quadratic Approximations of Cubic Boolean Functions

Nicholas Kolokotronis, Konstantinos Limniotis, and Nicholas Kalouptsidis

Abstract

The problem of computing best low order approximations of Boolean functions is treated in this paper. We focus on the case of best quadratic approximations of a wide class of cubic functions of arbitrary number of variables, and provide formulas for their efficient calculation. Our methodology is developed upon Shannon's expansion formula and properties of best affine approximations of quadratic functions, for which we prove formulas for their direct computation, without use of the Walsh-Hadamard transform. The notion of nonquadricity is introduced, as the minimum distance from all quadratic functions, and cubic functions that achieve the maximum possible nonquadricity are determined, leading to a lower bound for the covering radius of second order Reed-Muller code $\mthf{R}(2,n)$ in $\mthf{R}(3,n)$.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Unknown where it was published
Keywords
Bent functionsboolean functionscovering radiuslower order approximationsnonlinearitynonquadricityReed-Muller codes.
Contact author(s)
nkolok @ di uoa gr
History
2007-02-14: received
Short URL
https://ia.cr/2007/037
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/037,
      author = {Nicholas Kolokotronis and Konstantinos Limniotis and Nicholas Kalouptsidis},
      title = {Best Quadratic Approximations of Cubic Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2007/037},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/037}},
      url = {https://eprint.iacr.org/2007/037}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.