Multiplicative Complexity of Autosymmetric Functions: Theory and Applications to Security

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.