Abstract

In [1] we showed that any Boolean function can be associated to a Cayley graph whose spectrum coincides with the Walsh spectrum of the function, and used this idea to inves- tigate the spectrum of certain special functions. In this paper we further exploit this idea by studying the class of functions whose associated Cayley graph is bipartite. We derive an algebraic characterization for these functions, analyze their circuit complexity and argue that some of them might be of interest for cryptographic applications.