International Association
for Cryptologic Research

Maiorana--McFarland type constructions are basically concatenating the truth tables of linear functions on a smaller number of variables to obtain highly nonlinear ones on larger inputs. Such functions and their different variants have significant applications in cryptology and coding theory. Straightforward hardware implementation of such functions may require exponential resources on the number of inputs. In this paper, we study such constructions in detail and provide implementation strategies for a selected subset of this class with polynomial many gates over the number of inputs. We demonstrate that such implementations cover the requirement of cryptographic primitives to a great extent. Several existing constructions are revisited in this direction and exact implementations are provided with specific depth and gate counts in the hardware implementation. Related combinatorial as well as circuit complexity-related results of theoretical nature are also analyzed in this regard. Finally we present a novel construction of a new class of balanced Boolean functions having very low absolute indicator and very high nonlinearity that can be implemented in polynomial circuit size over the number of inputs. In conclusion, we present that these constructions have immediate applications to resist the signature generation in Differential Fault Attack (DFA) and to implement functions on large number of variables in designing ciphers for the paradigm of Fully Homomorphic Encryption (FHE).