Abstract
In symmetric-key cryptography, Boolean functions serve as critical components for providing nonlinearity in ciphers. This paper provides a rigorous mathematical characterization of the correlation properties for two foundational classes: Dillon type and Patterson-Wiedemann (PW) type Boolean functions. By utilizing interleaved sequences and subspace intersection counting, we demonstrate that the crosscorrelation spectra of Dillon type functions are restricted to at most five values, and only three for bent functions. These results provide significantly tighter bounds than previously established and offer new insights into the behavior of Weil sums in number theory.
Introduction
Boolean functions are the building blocks of S-boxes and filter generators in modern cryptographic systems. To ensure resistance against linear and differential cryptanalysis, these functions must exhibit high nonlinearity, low autocorrelation, and low crosscorrelation. While "bent functions"—those achieving the maximum possible nonlinearity—have been extensively studied, the crosscorrelation spectra between different functions within specific classes have remained largely uncharacterized.
This research addresses this gap for Dillon type functions (defined on an even number of variables $n$) and Patterson-Wiedemann type functions (defined on an odd number of variables). Both classes are highly valued for their nonlinearity, but their crosscorrelation properties were previously poorly understood.
Methodology: Beyond Fourier Techniques
Traditional analysis of Boolean functions often relies on Fourier-based techniques. However, the authors demonstrate that these standard methods are insufficient for fully characterizing the crosscorrelation spectra of Dillon and PW type functions. Instead, the paper employs a multi-faceted approach:
- Interleaved Sequences: Boolean functions are represented as matrices or interleaved sequences. This structural representation allows the support of the function to be analyzed as a union of cosets of subspaces within the finite field $GF(2^n)$.
- Subspace Intersection Counting: By calculating the exact points of intersection between $n/2$-dimensional subspaces, the authors derive precise formulas for correlation values.
- Trace Map Analysis: The properties of the trace map in finite fields are used to link cryptographic properties directly to exponential sums.
- Generalized Autocorrelation: The study introduces a framework for analyzing autocorrelation at different "decimations" (powers coprime to the field size), which is essential for evaluating "hyper-bent" functions.
Characterizing Dillon Type Functions
The primary insight of this work is that the specific construction of Dillon type functions—built from the union of specific cosets—mathematically constrains their crosscorrelation into a very limited set of values.
For Dillon type functions on an even number of variables $n$, the research proves that the crosscorrelation spectra is at most 5-valued. In the specific case of Dillon type bent functions, this spectrum is further restricted to at most 3-valued, with a maximum absolute value at nonzero points $\le 2^{n/2+1}$. This provides a much tighter bound than the general estimates used in previous literature.
Extensions to Patterson-Wiedemann Functions
The analysis is extended to Patterson-Wiedemann type functions, which are defined on an odd number of variables. The authors prove that the crosscorrelation spectra for these functions contain at most $r$ distinct values, where $r$ represents the number of equivalence classes under Frobenius automorphisms. This extension demonstrates the versatility of the interleaved sequence approach across different dimensions.
Implications for Weil Sums and Number Theory
One of the most significant contributions of this research lies in its connection to number theory. The Weil bound is a classic universal upper bound for exponential sums. However, the authors demonstrate that for the specific polynomials associated with Dillon type functions, the actual absolute value of the Weil sum is much lower than the general bound predicts.
Specifically, for a certain class of polynomials, the authors improved the predicted maximum value from $2^n - 2^{n/2+1}$ down to approximately $2^{n/2+1}$. This massive reduction highlights how the structural properties of these cryptographic functions can be used to solve or refine classic problems in mathematics.
Conclusion and Future Directions
While the paper successfully characterizes the spectra for several classes, it also identifies a combinatorial bottleneck. The authors found Dillon type bent functions where $f(x) + f(x^c)$ is also bent for $n=4$ and $n=6$, but were unable to find such instances for $n=8$. This suggests that as the number of variables increases, the combinatorial restrictions become increasingly severe.
Future research may focus on whether such functions exist for $n \ge 10$ or applying these interleaved sequence techniques to other emerging classes of Boolean functions to determine if they similarly outperform the standard Weil bound.
Summary updated