On Sum-Free Functions

Basic Information

• Paper ID: 2410.10426
• Title: On Sum-Free Functions
• Authors: Alyssa Ebeling, Xiang-Dong Hou, Ashley Rydell, Shujun Zhao
• Classification: math.NT (Number Theory), cs.IT (Information Theory), math.IT (Mathematical Information Theory)
• Publication Date: October 2024 (arXiv preprint)
• Paper Link: https://arxiv.org/abs/2410.10426

Abstract

This paper investigates the concept of sum-free functions over finite fields. A function from $\mathbb{F}_{2^n}$ to $\mathbb{F}_{2^n}$ is called $k$-th order sum-free if the sum of its values on every $k$-dimensional $\mathbb{F}_2$-affine subspace is nonzero. This concept was recently introduced by C. Carlet as a generalization of APN functions. The core of the research concerns a conjecture about the sum-free properties of the multiplicative inverse function $f_{\text{inv}}(x)=x^{-1}$. It is known that $f_{\text{inv}}$ is 2-nd order (equivalently, $(n-2)$-th order) sum-free if and only if $n$ is odd. The conjecture states that for $3\le k\le n-3$, $f_{\text{inv}}$ is never $k$-th order sum-free. This conjecture has been verified for even $n$, but remains unresolved for odd $n$.

Research Background and Motivation

1. Problem Definition: This paper studies the properties of sum-free functions, particularly the sum-free properties of the multiplicative inverse function. A sum-free function is one whose values sum to a nonzero element on all $k$-dimensional affine subspaces.
2. Significance:
   • Sum-free functions are a natural generalization of almost perfect nonlinear (APN) functions, which are widely studied in cryptography for their resistance to differential attacks
   • Addresses the vulnerability of block ciphers to integral attacks, which exploit the predictability of sums of S-box values on affine subspaces
   • From a theoretical perspective, the concept of sum-freedom possesses rich mathematical content
3. Existing Limitations:
   • For odd $n$, the central conjecture (Conjecture 1.1) regarding the sum-free properties of the multiplicative inverse function remains incompletely resolved
   • Lack of research on appropriate generalizations to the $q$-ary case
4. Research Motivation: To advance understanding of the theory of sum-free functions, particularly by resolving important conjectures related to the multiplicative inverse function and exploring its generalizations over more general finite fields.

Core Contributions

1. Proved Conjecture 1.1 under multiple conditions:
   • The case $n=13$
   • The case where $3|n$
   • The case where $5|n$
   • The case where the smallest prime factor $l$ of $n$ satisfies $(l-1)(l+2)\le (n+1)/2$
2. Determined the "correct" $q$-ary generalization of the binary multiplicative inverse function: Proved that the function $g_{q-1}(x)=1/x^{q-1}$ is the appropriate $q$-ary generalization of $f_{\text{inv}}$ in the binary case
3. Provided new proof methods: Gave a new proof that $4\in K_n$ (for all $n\ge 6$) using the Lang-Weil bound
4. Discovered anomalous phenomena in the $q$-ary case: Through computational search, found that for $q=3,5$ and $n=7$, $g_{q-1}$ is $k$-th order sum-free for all $1\le k\le 6$ on $\mathbb{F}_{q^7}$

Detailed Methodology

Task Definition

Given a function $f: \mathbb{F}_{q^n} \to \mathbb{F}_{q^n}$ over a finite field $\mathbb{F}_{q^n}$, study its $k$-th order sum-free property, namely that for all $k$-dimensional $\mathbb{F}_q$-affine subspaces $A$, we have $\sum_{x\in A} f(x) \neq 0$.

Core Methodological Framework

1. Moore Determinant Method:
   • Uses the Moore determinant $\Delta(X_1,\ldots,X_k)$ to characterize linear independence
   • Establishes connections between sum-free properties and zeros of the Moore determinant
2. Symmetric Polynomial Method:
   • Reformulates Carlet's discrimination criterion in terms of symmetric polynomials
   • Introduces the polynomial $\Theta_k(X_1,\ldots,X_k)$
3. Lang-Weil Bound Method:
   • Applies the Lang-Weil bound from algebraic geometry to estimate the number of points on algebraic varieties over finite fields
   • Proves absolute irreducibility of $\Theta_4$

Technical Innovations

1. Unified Theoretical Framework:
   • Establishes a unified theoretical framework from the binary to the $q$-ary case
   • Proves that most binary results can be generalized to the $q$-ary case
2. New Construction Techniques:
   • Theorem 3.3 provides a systematic method for constructing new counterexamples from known sum-free violations
   • Employs recursive construction using subfield structures
3. Absolute Irreducibility Proof:
   • Provides a technical proof of absolute irreducibility of the $\Theta_4$ polynomial in the appendix
   • This is a key step for applying the Lang-Weil bound

Main Theorems and Results

Core Theorems

Theorem 3.6: Let $n\ge 3$ be odd, and let $l$ be the smallest prime factor of $n$. If $(l-1)(l+2)\le (n+1)/2$, then Conjecture 1.1 holds for $n$.

Theorem 4.6 ($q$-ary version of the discrimination criterion): The function $g_{q-1}$ is not $k$-th order sum-free if and only if there exist $v_1,\ldots,v_k\in \mathbb{F}_{q^n}$ such that $\Delta(v_1,\ldots,v_k)\neq 0$ but $\Delta_1(v_1,\ldots,v_k)=0$.

Important Corollaries

Corollary 3.7: If $3|n$, then Conjecture 1.1 holds for $n$.

Theorem 3.13: If $5|n$, then Conjecture 1.1 holds for $n$.

$q$-ary Generalization Results

Proposition 4.7:

• $g_{q-1}$ is 1-st order sum-free
• When $n\ge 2$, $g_{q-1}$ is 2-nd order sum-free if and only if $n$ is odd

Experimental Setup and Results

Computational Verification

1. Case $n=13$: Verified through computer search that Conjecture 1.1 holds for $n=13$
2. Numerical results for the $q$-ary case: Systematically verified computationally for $q=3,5$ and $7\le n\le 11$

Main Findings

• For $q=3,5$ and $n=7$, the function $g_{q-1}$ is $k$-th order sum-free for all $1\le k\le 6$
• This phenomenon has never been observed in the binary case, demonstrating the unique properties of the $q$-ary case

Related Work

This paper builds upon the following important works:

1. Carlet's pioneering work: Introduced the concept of sum-free functions and fundamental theory
2. APN function theory: Sum-free functions are generalizations of APN functions
3. Moore determinant theory over finite fields: Provides important technical tools
4. Algebraic geometry methods: Applications of tools such as the Lang-Weil bound

Conclusions and Discussion

Main Conclusions

1. Resolved the important conjecture regarding sum-free properties of the multiplicative inverse function under multiple conditions
2. Established a complete theoretical framework from the binary to the $q$-ary case
3. Discovered novel phenomena in the $q$-ary case

Limitations

1. Conjecture 1.1 for general odd $n$ remains incompletely resolved
2. The most difficult cases are when $n$ is prime or a product of two nearby primes
3. Theoretical explanations for the anomalous phenomena in the $q$-ary case require further investigation

Future Directions

1. Completely resolve Conjecture 1.1
2. Deepen understanding of the special properties of the $q$-ary case
3. Explore applications of sum-free functions in cryptography
4. Study the irreducibility of more general $\Theta_k$ polynomials

In-Depth Evaluation

Strengths

1. Significant theoretical contributions: Made substantial progress on an important open problem
2. Methodological innovation: Combines number theory, algebraic geometry, and computational methods
3. Complete results: Includes both theoretical proofs and computational verification
4. Generalization value: Establishes a unified framework from binary to $q$-ary cases

Weaknesses

1. Core conjecture not completely resolved: Some cases remain uncovered
2. Technical complexity: Some proofs (such as the irreducibility proof in the appendix) are quite technical
3. Limited exploration of applications: Discussion of practical cryptographic applications is limited

Impact

1. Academic value: Advances the development of sum-free function theory, an emerging field
2. Methodological contribution: Provides new tools and techniques for addressing similar problems
3. Interdisciplinary significance: Connects number theory, algebraic geometry, and cryptography

Applicable Scenarios

1. S-box design and analysis in cryptography
2. Study of algebraic properties of functions over finite fields
3. Design of cryptographic systems resistant to integral attacks

Technical Details Supplement

Role of Moore Determinant

The Moore determinant $\Delta(X_1,\ldots,X_k) = \det(X_j^{q^{i-1}})_{1\le i,j\le k}$ plays a key role in determining linear independence of vectors. The zero-point properties of its variant $\Delta_1$ are directly related to violations of sum-free properties.

Symmetric Polynomial Representation

By expressing Carlet's discrimination criterion in terms of symmetric polynomials, the authors can leverage deep results from symmetric function theory, laying the foundation for subsequent irreducibility analysis.

Application of Lang-Weil Bound

By proving the absolute irreducibility of $\Theta_4$, the authors can apply the Lang-Weil bound to precisely estimate the number of points on related algebraic varieties, thereby completing the new proof that $4\in K_n$.

This paper makes important contributions to the emerging field of sum-free functions, advancing theoretical understanding of the central conjecture and establishing a framework for generalization to more general cases, providing a solid foundation for subsequent research.