Autosymmetric and D-reducible Functions: Theory and Application to Security

In this paper we study Boolean functions that exhibit two different XOR-based regularities (i.e., autosymmetry and D-reducibility) at the same time. XOR-based regularities can be exploited for the efficient computation of multiplicative complexity of a Boolean function f (i.e., the minimum number of AND gates that are necessary and sufficient to represent f over the basis {AND, XOR, NOT}). The multiplicative complexity is crucial in cryptography protocols such as zero-knowledge protocols and secure two-party computation, where processing AND gates is more expensive than processing XOR gates.