TL;DR
This paper introduces three new families of Boolean functions that exhibit a limited number of distinct Walsh transform values. These functions are constructed using existing classes like bent and Gold functions, and their properties are analyzed to provide insights into their cryptographic and communication system applications.
What Problem Does This Paper Address?
In the fields of cryptography and communication systems, particularly in code-division multiple-access (CDMA) and sequence design, understanding the correlation properties of sequences is crucial. A key tool for this analysis is the Walsh transform. Functions with few distinct Walsh transform values are highly desirable because they often lead to sequences with good correlation properties, which are essential for efficient and secure communication. While bent functions (with exactly two Walsh transform values) are well-studied, constructing and characterizing balanced Boolean functions with a small number of Walsh transform values (beyond two) remains a significant challenge. This paper aims to address this by constructing and analyzing new classes of such functions.
Methods
The paper focuses on constructing Boolean functions of the form $g(x) = f(x) \text{Tr}_1(x) + (f(x) + 1) \text{Tr}_1(\delta x)$, where $f(x)$ is a known Boolean function, $\delta$ is a non-identity element, and $\text{Tr}_1$ is the trace function. The core of the methodology involves:
- Leveraging Existing Function Classes: The authors construct new functions by choosing $f(x)$ from well-known classes like bent functions (including Dillon, Kasami, and Gold-like bent functions) and Gold functions.
- Walsh Transform Analysis: The paper extensively uses the properties of the Walsh transform. Proposition 1 provides a general formula relating the Walsh transform of $g(x)$ to that of $f(x)$, $f(x+\delta)$, and $f(x+1)$.
- Utilizing Field Theory and Number Theory: Concepts like finite fields ($F_{2^n}$), multiplicative groups, trace functions, and properties of linearized polynomials are fundamental to the analysis. Lemmas are used to handle specific cases of these functions and their properties.
- Case Analysis: The analysis is broken down into various cases based on parameters like $n/d$ (where $d = \text{gcd}(i,n)$), the value of $a$, and the solvability of certain polynomial equations. This detailed case analysis is crucial for determining the exact Walsh spectrum distributions.
Datasets
Not discussed in the paper. The paper focuses on theoretical constructions and analyses of Boolean functions rather than empirical evaluation on datasets.
Key Insights and Ideas
- Constructing New Functions from Old: The paper demonstrates a systematic way to generate new Boolean functions with desirable Walsh transform properties by combining existing, well-understood functions (like bent and Gold functions) with trace functions. This is a powerful constructive approach.
- Limited Walsh Transform Values are Achievable: The constructions show that it's possible to create balanced Boolean functions with a small, finite number of Walsh transform values (specifically, at most five in this work), which are crucial for applications.
- Connection to Algebraic Degree: The paper hints at the possibility of achieving high algebraic degrees (up to $n$) for these constructed functions, which is another important cryptographic property.
- Generalization of Properties: By analyzing the structure of $g(x)$, the paper provides a unified framework to study the Walsh transform of functions derived from various classes, offering a deeper understanding of their spectral properties.
Key Results
The paper presents three main classes of Boolean functions with few Walsh transform values:
- Functions derived from bent functions: These functions, when constructed under specific conditions (e.g., $f^*(\delta+1) = \epsilon$), exhibit at most five Walsh transform values. The paper provides detailed Walsh spectrum distributions for these functions, particularly for those derived from Dillon, Kasami, and Gold-like bent functions.
- Functions derived from Gold functions: The analysis of Gold functions leads to functions with at most five Walsh transform values, with specific distributions determined based on whether $n/d$ is even or odd, and the properties of the parameter $a$.
- Functions derived from the product of linearized polynomials: These constructions yield functions with at most three or four Walsh transform values, depending on the parameters.
The paper also provides specific theorems (Theorem 3.3, 3.4, 3.5, 3.6, 3.8) detailing the exact Walsh spectrum distributions for these newly constructed classes under various conditions.
Limitations and Future Work
- Specific Construction Form: The constructions are limited to the specific form $g(x) = f(x) \text{Tr}_1(x) + (f(x) + 1) \text{Tr}_1(\delta x)$. While this form is versatile, it doesn't cover all possible ways to construct functions with few Walsh transform values.
- Complexity of Analysis: The analysis involves intricate case distinctions and relies heavily on advanced concepts from finite field theory. This complexity might limit direct application without further simplification or computational tools.
- Future Work: The authors suggest that their techniques could be useful for finding new (balanced) Boolean functions with few Walsh transform values, implying that further exploration of similar construction methods and analysis of dual functions of known classes are promising avenues. The paper also mentions that the Walsh spectrum of $g(x)$ derived from other bent functions with known dual functions deserves further study.
Summary updated