Cryptology ePrint Archive: Report 2020/706

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

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

Abstract: 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.

Category / Keywords: implementation / multiplicative complexity, logic synthesis, XOR AND graphs, secure multi-party computation

Original Publication (in the same form): Design, Automation and Test in Europe Conference (DATE) 2020

Date: received 12 Jun 2020

Contact author: testa eleonora91 at gmail com

Available format(s): PDF | BibTeX Citation

Version: 20200614:201739 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]