Paper 2023/1970

Construction of Maiorana-McFarland type cryptographically significant Boolean functions with good implementation properties

Abstract

We present a new construction of cryptographically significant Boolean functions defined over a large number of variables, with an emphasis on efficient circuit realizability. Our method is based on a variant of the well-known Maiorana-McFarland (MM) construction, adapted to enable circuit structures with less than $6n$ gates on the number of input bits $n$. We evaluate the circuit efficiency in terms of the total number of logic gates (for example AND, OR, NOT, and XOR, each with a maximum fan-in of two) required to implement a given function. While prior studies have explored cryptographic parameters of such functions in theory, they often overlooked circuit-level efficiency, especially in high-dimensional settings. In this work, we construct a class of balanced functions with high nonlinearity, low absolute autocorrelation and high algebraic degree, yet realizable using a small number of logic gates. Towards application, this work provides additional design directions for cryptographic primitives in domains such as fault-resistant cryptography and homomorphic encryption, where both security and circuit efficiency at scale are critical. Further investigations are required towards actual hardware implementation of our proposed functions as well as to exploit them in concrete cipher designs.

Note: Major revision.