Paper 2020/706

A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks

Eleonora Testa, Mathias Soeken, Heinz Riener, Luca Amaru, and Giovanni De Micheli


Logic synthesis is a fundamental step in the realization of modern integrated circuits. It has traditionally been employed for the optimization of CMOS-based designs, as well as for emerging technologies and quantum computing. Recently, it found application in minimizing the number of AND gates in cryptography benchmarks represented as xor-and graphs (XAGs). The number of AND gates in an XAG, which is called the logic network’s multiplicative complexity, plays a critical role in various cryptography and security protocols such as fully homomorphic encryption (FHE) and secure multi-party computation (MPC). Further, the number of AND gates is also important to assess the degree of vulnerability of a Boolean function, and influences the cost of techniques to protect against side-channel attacks. However, so far a complete logic synthesis flow for reducing the multiplicative complexity in logic networks did not exist or relied heavily on manual manipulations. In this paper, we present a logic synthesis toolbox for cryptography and security applications. The proposed tool consists of powerful transformations, namely resubstitution, refactoring, and rewriting, specifically designed to minimize the multiplicative complexity of an XAG. Our flow is fully automatic and achieves significant results over both EPFL benchmarks and cryptography circuits. We improve the best-known results for cryptography up to 59%, resulting in a normalized geometric mean of 0.82.

Available format(s)
Publication info
Published elsewhere. Design, Automation and Test in Europe Conference (DATE) 2020
multiplicative complexitylogic synthesisXOR AND graphssecure multi-party computation
Contact author(s)
testa eleonora91 @ gmail com
2020-06-14: received
Short URL
Creative Commons Attribution


      author = {Eleonora Testa and Mathias Soeken and Heinz Riener and Luca Amaru and Giovanni De Micheli},
      title = {A Logic Synthesis Toolbox for Reducing the Multiplicative Complexity in Logic Networks},
      howpublished = {Cryptology ePrint Archive, Paper 2020/706},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.