17.08.2019
Upper bounds on the multiplicative complexity of symmetric Boolean functions
Erschienen in: Cryptography and Communications | Ausgabe 6/2019
EinloggenAktivieren Sie unsere intelligente Suche um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Abstract
AND
gates sufficient to implement a function with a Boolean circuit over the basis {XOR
, AND
, NOT
}. In this paper we study the MC of symmetric Boolean functions, whose output is invariant upon reordering of the input variables. Based on the Hamming weight method from Muller and Preparata (J. ACM 22(2), 195–201, 1975), we introduce new techniques that yield circuits with fewer AND
gates than upper bounded by Boyar et al. (Theor. Comput. Sci. 235(1), 43–57, 2000) and by Boyar and Peralta (Theor. Comput. Sci. 396(1–3), 223–246, 2008). We generate circuits for all such functions with up to 25 variables. As a special focus, we report concrete upper bounds for the MC of elementary symmetric functions \({{\Sigma }^{n}_{k}}\) and counting functions \({E^{n}_{k}}\) with up to n = 25 input variables. In particular, this allows us to answer two questions posed in 2008: both the elementary symmetric \({{\Sigma }^{8}_{4}}\) and the counting \({E^{8}_{4}}\) functions have MC 6. Furthermore, we show upper bounds for the maximum MC in the class of n-variable symmetric Boolean functions, for each n up to 132.