Cryptology ePrint Archive: Report 2007/037

Best Quadratic Approximations of Cubic Boolean Functions

Nicholas Kolokotronis and 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)$.

Category / Keywords: foundations / Bent functions; boolean functions; covering radius; lower order approximations; nonlinearity; nonquadricity; Reed-Muller codes.

Date: received 5 Feb 2007

Contact author: nkolok at di uoa gr

Available format(s): PDF | BibTeX Citation

Version: 20070214:103421 (All versions of this report)

Discussion forum: Show discussion | Start new discussion


[ Cryptology ePrint archive ]