Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions

Published: August 17, 2019


Luis Brandao, Cagdas Calik, Meltem Sonmez Turan, Rene C. Peralta


Symmetric Boolean functions are of fundamental interest for cryptography, logic circuit design, sorting networks and software applications. A special metric of interest about these functions is multiplicative complexity (MC): the minimum number of AND gates sufficient to implement a function with a circuit over the basis XOR, AND, NOT. In this paper we introduce new techniques that enable constructing circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and Boyar and Peralta in 2008. Our results for symmetric Boolean functions include improved upper bounds for: the MC of each function with up to n=25 input variables; for n up to 129, the maximum MC in the class of n-variable functions. We also answer two questions posed in 2008 by Boyar and Peralta: both the elementary symmetric \Sigma^8_4 and counting E^8_4 functions of degree 4 and 8 variables have MC 6.
Citation: Cryptography and Communication
Pub Type: Journals


Symmetric Boolean functions, multiplicative complexity, logic minimization, upper bounds
Created August 17, 2019, Updated September 05, 2019