Paper 2019/708

Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions

Luís T. A. N. Brandão, Çağdaş Çalık, Meltem Sönmez Turan, and René Peralta

Abstract

A special metric of interest about Boolean functions is multiplicative complexity (MC): the minimum number of 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 (1975), we introduce new techniques that yield circuits with fewer AND gates than upper bounded by Boyar et al. in 2000 and by Boyar and Peralta in 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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision.Cryptography and Communications Discrete Structures, Boolean Functions and Sequences
DOI
10.1007/s12095-019-00377-3
Keywords
symmetric Boolean functionsmultiplicative complexityupper boundslogic minimization
Contact author(s)
luis papers @ gmail com
luis brandao @ nist gov
cagdas calik @ nist gov
meltem turan @ nist gov
rene peralta @ nist gov
History
2019-06-18: received
Short URL
https://ia.cr/2019/708
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2019/708,
      author = {Luís T.  A.  N.  Brandão and Çağdaş Çalık and Meltem Sönmez Turan and René Peralta},
      title = {Upper Bounds on the Multiplicative Complexity of Symmetric Boolean Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2019/708},
      year = {2019},
      doi = {10.1007/s12095-019-00377-3},
      note = {\url{https://eprint.iacr.org/2019/708}},
      url = {https://eprint.iacr.org/2019/708}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.