Title :
Matriochka symmetric Boolean functions
Author :
Lauradoux, Cedric ; Videau, Marion
Author_Institution :
Dept. of Electr. Eng., Princeton Univ., Princeton, NJ
Abstract :
We present the properties of a new class of Boolean functions defined as the sum of m symmetric functions with decreasing number of variables and degrees. The choice of this construction is justified by the possibility to study these functions by using tools existing for symmetric functions. On the one hand we show that the synthesis is well understood and give an upper bound on the gate complexity. On the other hand, we investigate the Walsh spectrum of the sum of two functions and get explicit formulae for the case of degree at most three.
Keywords :
Boolean functions; Walsh functions; circuit complexity; cryptography; logic gates; set theory; symmetric switching functions; Walsh spectrum; cryptographic property; logic gate complexity; matriochka symmetric Boolean function; set theory; Algorithm design and analysis; Boolean functions; Circuits; Cryptography; Hamming weight; Polynomials; Symmetric matrices; Tin; Upper bound; Vectors;
Conference_Titel :
Information Theory, 2008. ISIT 2008. IEEE International Symposium on
Conference_Location :
Toronto, ON
Print_ISBN :
978-1-4244-2256-2
Electronic_ISBN :
978-1-4244-2257-9
DOI :
10.1109/ISIT.2008.4595264
