Generalized Maiorana-McFarland Constructions for Almost Optimal Resilient Functions

2010/03/17 by Weiguo Zhang, Zhang, WeiGuo, Xiao, GuoZhen
Computer Science · Mathematics · #Advanced Differential Equations and Dynamical Systems #Coding theory and cryptography #Combinatorics (math.CO) #Cryptography and Security (cs.CR) #FOS: Computer and information sciences #FOS: Mathematics #Finite Group Theory Research #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1003.3492

openalex publication_date 2010/03/17 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

In a recent paper \citeZhang-Xiao, Zhang and Xiao describe a technique on constructing almost optimal resilient functions on even number of variables. In this paper, we will present an extensive study of the constructions of almost optimal resilient functions by using the generalized Maiorana-McFarland (GMM) construction technique. It is shown that for any given m, it is possible to construct infinitely many n-variable (n even), m-resilient Boolean functions with nonlinearity equal to 2^n-1-2^n/2-1-2^k-1 where k2^n-2-2^(n-1)/2 (n odd) by using Patterson-Wiedemann functions or Kavut-Yucel functions. Finally, we provide a GMM construction technique for multiple-output almost optimal m-resilient functions F: \mathbbF₂ⁿ↦ \mathbbF₂^r (n even) with nonlinearity >2^n-1-2^n/2. Using the methods proposed in this paper, a large class of previously unknown cryptographic resilient functions are obtained.

Related

• Explicit resilient functions matching Ajtai-Linial
• On Boolean Functions with Low Polynomial Degree and Higher Order Sensitivity
• Constructions of Efficiently Implementable Boolean Functions with Provable Nonlinearity/Resiliency/Algebraic Immunity Trade-Offs
• Constructing Boolean Functions With Potential Optimal Algebraic Immunity Based on Additive Decompositions of Finite Fields
• Vectorial Resilient PC(l) of Order k Boolean Functions from AG-Codes