Multiplicative Complexity of Autosymmetric Functions: Theory and Applications to Security
Anna Bernasconi, Stelvio Cimato, Valentina Ciriani, Maria Chiara Molteni
Abstract
The multiplicative complexity of a Boolean function is the minimum number of AND gates (i.e., multiplications) that are sufficient to represent the function over the basis AND, XOR, NOT. The multiplicative complexity measure plays a crucial role in cryptography-related applications. In fact, the minimization of the number of AND gates is important for high-level cryptography protocols such as secure multiparty computation, where processing AND gates is more expensive than processing XOR gates. Moreover, it is an indicator of the degree of vulnerability of the circuit, as a small number of AND gates corresponds to a high vulnerability to algebraic attacks. In this paper we study a particular structure regularity of Boolean functions, called autosymmetry, and exploit it to decrease the number of ANDs in XOR-AND Graphs (XAGs), i.e., Boolean networks composed by ANDs, XORs, and inverters. The interest in autosymmetric functions is motivated by the fact that a considerable amount of standard Boolean functions of practical interest presents this regularity; indeed, about 24% of the functions in the classical ESPRESSO benchmark suite have at least one autosymmetric output. The experimental results validate the proposed approach.
Ask Lune
Know this paper in minutes, not an afternoon.
Lune can read every page of it and the top-tier papers that cite it, and gives you its claims, its evidence and its limits, each one cited to the paper it comes from. No skimming, no AI slop.
Related papers
- Tight Bounds on the Randomness Complexity of Secure Multiparty ComputationVipul Goyal, Yuval Ishai, Yifan SongCRYPTO 2022 · 2 citations
- Three Halves Make a Whole? Beating the Half-Gates Lower Bound for Garbled CircuitsMike Rosulek, Lawrence RoyCRYPTO 2021 · 78 citations
- Global-Scale Secure Multiparty ComputationXiao Wang, Samuel Ranellucci, Jonathan KatzCCS 2017 · 220 citations
- Large Scale, Actively Secure Computation from LPN and Free-XOR Garbled CircuitsAner Ben-Efraim, Kelong Cong, Eran Omri, Emmanuela Orsini et al.EUROCRYPT 2021 · 21 citations
- Efficient Batchable Secure Outsourced Computation: Depth-Aware Arithmetization of Common Primitives for BFV & BGVJelle Vos, Mauro Conti, Zekeriya ErkinUSENIX Security 2025
