Welcome to the resource topic for 2019/1364
Title:
Boolean Functions with Multiplicative Complexity 3 and 4
Authors: Cagdas Calik, Meltem Sonmez Turan, Rene Peralta
Abstract:Multiplicative complexity (MC) is defined as the minimum number of AND gates required to implement a function with a circuit over the basis (AND, XOR, NOT). Boolean functions with MC 1 and 2 have been characterized in Fischer and Peralta ( 2002) and Find et al. (2017), respectively. In this work, we identify the affine equivalence classes for functions with MC 3 and 4. In order to achieve this, we utilize the notion of the dimension dim(f) of a Boolean function in relation to its linearity dimension, and provide a new lower bound suggesting that multiplicative complexity of f is at least \ceil{dim(f)/2}. For MC 3, this implies that there are no equivalence classes other than those 24 identified in Calik et al (2018). Using the techniques from Calik et al. (2018) and the new relation between dimension and MC, we identify the 1277 equivalence classes having MC 4. We also provide a closed formula for the number of n-variable functions with MC 3 and 4. The techniques allow us to construct MC-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on.
ePrint: https://eprint.iacr.org/2019/1364
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .