Families of special Boolean functions help build secure cryptography
Explicit Constructions of Maximum-Cardinality Families of Plateaued Functions with Pairwise Disjoint Walsh Supports
Information Theory
Summary
This paper focuses on creating large groups of special Boolean functions called plateaued functions that have unique properties useful in cryptography. These functions do not share certain patterns that could weaken security and come with explicit algebraic formulas. The authors develop two new ways to construct these functions with controlled complexity and guarantee they don’t have certain weaknesses. This work advances methods for designing cryptographic components with strong and predictable properties.
What this means in practice
- •For cryptographic engineers: Design cryptographic Boolean functions with guaranteed maximal size families and no weak linear structures using explicit algebraic formulas.
- •For hardware security teams: Implement secure components in hardware by employing plateaued functions with disjoint spectral supports to enhance resistance to linear attacks.
Authors
Chen Wang, Shuailong Li
Abstract
Families of plateaued Boolean functions with pairwise disjoint Walsh supports are useful in secondary constructions of cryptographic Boolean functions. Of particular interest are maximum-cardinality families whose members admit no nonzero linear structures. To the best of our knowledge, the previously known general construction attaining both properties is spectral (Hodžić et al., IEEE Trans. Inf. Theory 65(9): 5865--5879, 2019). In that work, explicit algebraic normal forms are not generally provided, and no general method is established for prescribing a common algebraic degree for all family members. In this paper, we present two new explicit algebraic constructions within a unified framework, one based on linear functions and the other on partially linear functions with bent components. Let $p\geq 2$ and $q\geq 0$ satisfy $q<2^p-p-1$, and set $m=p+q$. Both constructions yield maximum-cardinality families of $2^{q+1}$ $(q+1)$-plateaued Boolean functions with pairwise disjoint Walsh supports. No member admits a nonzero linear structure, and every member has an explicit generalized Maiorana--McFarland representation. The first construction produces functions in $m+p+1$ variables and realizes any prescribed common algebraic degree $3\leq d\leq p+1$, provided that $q<\sum_{i=2}^{d-1}\binom{p}{i}$; its maximum attainable degree $p+1$ is optimal. The second construction produces functions in $n+p+1$ variables, where $n>m$ and $n-m$ is even, and realizes any prescribed common algebraic degree $3\leq d\leq p+(n-m)/2$, provided that $q<\sum_{i=2}^{\min\{d-1,p\}}\binom{p}{i}$; its maximum attainable degree $p+(n-m)/2$ is next-to-optimal.