Paper 2023/1970

Efficient Hardware Implementation for Maiorana-McFarland type Functions

Anupam Chattopadhyay
Subhamoy Maitra
Bimal Mandal
Manmatha Roy
Deng Tang

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 cryptology and coding theory applications. The straightforward hardware implementation of such functions using decoders (Khairallah et al., WAIFI 2018; Tang et al., SIAM Journal on Discrete Mathematics, 2019) requires 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 for hardware implementation. Related combinatorial results of theoretical nature are also analyzed in this regard. Finally, we present a novel construction of a new class of balanced Boolean functions with very low absolute indicators and very high nonlinearity that can be implemented in polynomial-size circuits over the number of inputs. We underline that these constructions have immediate applications to resist the signature generation in Differential Fault Attack (DFA) and to implement functions on a large number of variables in designing ciphers for the paradigm of Fully Homomorphic Encryption (FHE).

Note: Minor revisions made

Available format(s)
Secret-key cryptography
Publication info
BalancednessBent FunctionBoolean FunctionHardware ImplementationMaiorana-McFarland Construction.
Contact author(s)
anupam @ ntu edu sg
subho @ isical ac in
bimalmandal @ iitj ac in
manmatha @ isical ac in
dtang @ foxmail com
2024-05-10: last of 2 revisions
2023-12-29: received
See all versions
Short URL
Creative Commons Attribution


      author = {Anupam Chattopadhyay and Subhamoy Maitra and Bimal Mandal and Manmatha Roy and Deng Tang},
      title = {Efficient Hardware Implementation for Maiorana-{McFarland} type Functions},
      howpublished = {Cryptology ePrint Archive, Paper 2023/1970},
      year = {2023},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.