Boolean functions with multiplicative complexity 3 and 4
- PDF / 598,092 Bytes
- 12 Pages / 439.642 x 666.49 pts Page_size
- 69 Downloads / 232 Views
Boolean functions with multiplicative complexity 3 and 4 ˘ ¸ C¸alık1 C¸agdas
¨ · Meltem Sonmez Turan1 · Rene´ Peralta1
Received: 20 September 2019 / Accepted: 22 June 2020 / © This is a U.S. Government work and not under copyright protection in the US; foreign copyright protection may apply 2020
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 Fisher and Peralta (2002), and Find et al. (IJICoT 4(4), 222–236, 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 the multiplicative complexity of f is at least dim(f )/2. For MC 3, this implies that there are no equivalence classes other than those 24 identified in C¸alık et al. 2018). Using the techniques from C¸alık et al. and the new relation between the dimension and MC, we identify all 1277 equivalence classes having MC 4. We also provide a closed formula for the number of n-variable functions with MC 3 and 4. These results allow us to construct AND-optimal circuits for Boolean functions that have MC 4 or less, independent of the number of variables they are defined on. Keywords Affine equivalence · Boolean functions · Multiplicative complexity Mathematics Subject Classification (2010) 94A60 · 06E30
1 Introduction In cryptographic protocols such as fully-homomorphic encryption (e.g., [6]), zeroknowledge proofs (e.g., [3]), and secure multi-party computation (e.g. [15]), Boolean circuits using fewer nonlinear gates are preferred for efficiency. This promoted the design of symmetric primitives (e.g., Rasta [9], LowMC [1]), which are inherently designed to use only a small number of AND gates. Multiplicative Complexity (MC) is defined as the minimum number of AND gates required to implement a given function by a circuit over the basis (AND, XOR, NOT). The C ¸ a˘gdas¸ C ¸ alık
[email protected] 1
NIST Computer Security Division, 100 Bureau Dr, Gaithersburg, MD, 20899, USA
Cryptography and Communications
MC of a random n-variable Boolean function f , denoted C∧ (f ), is at least 2n/2 − On with high probability [4]. The MC of a random Boolean function is hard to calculate even for a small number of variables. For up to 6 variables, the MC of each Boolean function has been established in [8, 22]. For arbitrary n, it is known that under standard cryptographic assumptions, computing the MC in polynomial time in the length of the truth table [10] is not possible. There are, however, results for special classes of Boolean functions. In [17], Mirwald and Schnorr studied the MC of quadratic functions and showed that C∧ (f ) = k, iff f is isomorphic to the canonical form ki=1 x2i−1 x2i . In [7], Brand˜ao et al. studied the MC of symmetric Boolean functio
Data Loading...
