Title :
Fast computation of Boolean influences
Author_Institution :
Sch. of Math. & Geospatial Sci., RMIT Univ., Melbourne, VIC
Abstract :
We introduce a fast spectral algorithm for computing influences of variables for Boolean functions. The influence of variables, as defined in computer science has close relationships with some criteria used in cryptographic evaluation of boolean functions, especially resilience. Our spectral algorithm can also be utilized to compute the resilience of Boolean functions. The algorithm is also of independent interest as a generalization of the Walsh-Hadamard transform.
Keywords :
Boolean functions; Hadamard transforms; Walsh functions; Boolean functions; Boolean influences; Walsh-Hadamard transform; cryptographic evaluation; resilience; spectral algorithm; variable influence; Australia; Binary sequences; Boolean functions; Computer science; Cryptography; Galois fields; Resilience;
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.4595266