Paper 2007/037 Original: eprint.iacr.org/2007/037 ↗
Best Quadratic Approximations of Cubic Boolean Functions
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
- Preprint.
- History
- 2007-02-14: last updated
- 2007-02-14: published
- Short URL
- https://ia.cr/2007/037
- License
- https://creativecommons.org/licenses/by/4.0/
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},
url = {https://eprint.iacr.org/2007/037}
}