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.

Multiplicative complexity of autosymmetric functions: Theory and applications to security

Bernasconi A.;
2020-01-01

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.
2020
978-1-7281-1085-1
File in questo prodotto:
Non ci sono file associati a questo prodotto.

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11568/1067774
 Attenzione

Attenzione! I dati visualizzati non sono stati sottoposti a validazione da parte dell'ateneo

Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 5
  • ???jsp.display-item.citation.isi??? 1
social impact