New nonexistence results on (m, n)-generalized bent functions

Ka Hin Leung, Qi Wang

TL;DR

This paper establishes new boundaries for the existence of $(m, n)$-generalized bent functions (GBFs), which are mathematical objects used to build secure cryptographic systems. By leveraging group ring theory and the study of vanishing sums of roots of unity, the authors prove that these functions cannot exist under several previously unknown conditions, including a complete nonexistence proof for the case where $n=3$ and $m$ is odd or $m \equiv 2 \pmod 4$.

What Problem Does This Paper Address?

In cryptography and coding theory, "bent functions" are highly prized because they are as far from being linear as possible. This "perfect nonlinearity" makes them excellent building blocks for S-boxes in block ciphers and for spreading sequences in CDMA communications, as they provide maximum resistance to linear cryptanalysis.

While standard Boolean bent functions (mapping bits to bits) are well-understood, generalized bent functions—which map a vector of $n$ bits to an integer modulo $m$—are much more elusive. Researchers know some cases where they do exist (e.g., when $m$ is a power of 2), but the "forbidden zones" where they cannot exist remain poorly mapped. This paper aims to fill those gaps, specifically focusing on cases where $m$ is odd or twice an odd number.

Methods

The authors move away from pure functional analysis and instead use Algebraic Group Theory and Character Theory.

  1. Group Rings: They represent the GBF as an element within a group ring $\mathbb{Z}[C_m][G]$. This allows them to transform the "bentness" property into a structural equation.
  2. Vanishing Sums of Roots of Unity: A core challenge in this field is understanding when a sum of complex roots of unity equals zero. The authors utilize the concept of "minimal relations" and "c-exponents" to analyze these sums.
  3. Reduction Theorem: A key strategic move in the paper is a "reduction" approach. They prove that if a prime factor of $m$ is larger than $2^n$, it essentially doesn't contribute to the existence of the function, allowing them to simplify complex values of $m$ into smaller, more manageable cases.

Datasets

Not discussed in the paper. As a theoretical work in pure mathematics and cryptography, the results are derived through formal proofs rather than empirical testing on datasets.

Key Insights and Ideas

  • The "Large Prime" Filter: One of the most powerful insights (Proposition 3.1) is that if $m$ has a prime factor $p > 2^n$, the existence of an $(m, n)$-GBF implies the existence of an $(m/p, n)$-GBF. This allows researchers to "ignore" very large prime factors when searching for nonexistence.
  • Structural Constraints on $m$: The paper shows that for odd $m$, a GBF can only exist if $m$ has at least two distinct prime factors and those factors satisfy a specific inequality relative to $2^n$ ($3p_1 + p_2 \le 2^n$).
  • The $n=3$ Breakthrough: By combining their new tools, the authors provide a definitive answer for $n=3$. They prove that no $(m, 3)$-GBF exists for any $m$ that is odd or $m \equiv 2 \pmod 4$. This settles a specific case that had remained open in previous literature.

Key Results

  • Theorem 3.4: For odd $m = \prod p_i^{\alpha_i}$, if an $(m, n)$-GBF exists, then $m$ must have at least two distinct prime factors ($s \ge 2$) and $3p_1 + p_2 \le 2^n$. This significantly narrows the search space for these functions.
  • Theorem 3.8: For $m = 2p^\alpha$ and odd $n$, the authors show that $p$ must be quite small ($p < 2^{n-3}$) unless $p$ is a specific type of Mersenne prime.
  • Complete Nonexistence for $n=3$: The paper concludes that for the specific dimension $n=3$, generalized bent functions simply do not exist for the targeted classes of $m$.

Limitations and Future Work

The paper primarily focuses on the "negative" side—proving where functions cannot exist. While this is vital for narrowing the search, it does not provide new constructions for cases where they might exist.

The authors note that their results improve upon recent work by Liu, Feng, and Feng (2017), but there are still "gray areas" where the existence of GBFs is neither proven nor disproven, particularly for larger values of $n$ and more complex prime factorizations of $m$. Future research could apply these group ring techniques to higher dimensions or different group structures (like non-Abelian groups).

Summary updated

Abstract

In this paper, we present some new nonexistence results on (m, n)-generalized bent functions, which improved recent results. More precisely, we derive new nonexistence results for general n and m odd or $$m \equiv 2 \pmod {4}$$ m≡2(mod4), and further explicitly prove nonexistence of (m, 3)-generalized bent functions for all integers m odd or $$m \equiv 2 \pmod {4}$$ m≡2(mod4). The main tools we utilized are certain exponents of minimal vanishing sums from applying characters to group ring equations that characterize (m, n)-generalized bent functions.
BibTeX
@inproceedings{leung2020new,
  author = {Ka Hin Leung and Qi Wang},
  title = {{New nonexistence results on (m, n)-generalized bent functions}},
  booktitle = {Des. Codes Cryptogr},
  year = {2020},
  url = {https://openreview.net/forum?id=bqjDytWOAe},
}
Figure