A New Lever Function with Adequate Indeterminacy

Shenghui Su, Ping Luo, Shuwang Lv, Maozhi Xu

TL;DR

This paper introduces a new "lever function" for the REESSE1+ asymmetrical cryptosystem designed to inject "adequate indeterminacy" into the encryption process. By using a one-to-one mapping to a set of small positive and negative integers, the authors demonstrate that even a simplified version of the cryptosystem can resist powerful probabilistic polytime attacks, such as continued fraction analysis.

What Problem Does This Paper Address?

Most modern asymmetrical cryptosystems, like RSA or ElGamal, rely on the presumed hardness of specific mathematical problems—namely, Integer Factorization (IFP) and Discrete Logarithms (DLP). However, these problems are not proven to be NP-complete, leaving a theoretical door open for efficient future attacks.

The REESSE1+ cryptosystem takes a different approach by utilizing a "lever function" ($\ell(i)$) within its key transformation. The authors specifically address the vulnerability of simplified versions of this system to Continued Fraction Attacks and W-parameter Intersection Attacks. These attacks attempt to recover private keys by exploiting mathematical regularities in the public key. The challenge is to design a lever function that provides enough "indeterminacy"—essentially mathematical unpredictability—to make these attacks computationally infeasible ($O(2^n)$) without sacrificing decryption efficiency.

Methods

The authors analyze a simplified version of the REESSE1+ transform: $$C_i \equiv A_i W^{\ell(i)} \pmod M$$ where $C_i$ is the public key, $A_i$ is a coprime sequence, $W$ is a secret parameter, and $M$ is a large prime.

The core innovation is the New Lever Function:

  • Mapping: It maps the index $i \in \{1, \dots, n\}$ to a codomain $\Omega_{\pm} = \{\pm 5, \pm 6, \dots, \pm(n + 4)\}$.
  • Properties: The function must be an injection (one-to-one) and established randomly without a simple analytical expression.
  • Indeterminacy: By including both positive and negative exponents, the function prevents attackers from easily "neutralizing" the powers of $W$ when they multiply or divide public key elements during an attack.

The paper uses number theory proofs to show that if $\ell(i)$ is a constant, the system is easily broken. However, when $\ell(i)$ is a random permutation, the attacker is faced with an exponential number of possible arrangements.

Datasets

As a theoretical cryptography paper, it does not use standard large-scale datasets. Instead, the authors evaluate their approach using:

  • Numerical Simulations: Small-scale examples (e.g., $n=6$ and $n=10$) are used to walk through the math of why a Continued Fraction Attack fails against the new lever function.
  • Complexity Analysis: They calculate the theoretical running times of known attack algorithms against their proposed function to prove exponential hardness.

Key Insights and Ideas

  • Indeterminacy as a Security Primitive: The authors argue that security doesn't just come from "hard" problems, but from the "indeterminacy" brought by permutations. If an attacker cannot predict which exponent $\ell(i)$ corresponds to which index $i$, they cannot set up the equations needed for a continued fraction attack.
  • The Power of Negative Exponents: Moving from a set of only positive integers to $\Omega_{\pm}$ (including negative values) significantly increases the difficulty for an attacker to find a product of public keys where the secret $W$ parameters cancel out.
  • Lever Function as a Random Oracle: The authors bridge the gap between their function and the "Random Oracle Model" used in cryptographic proofs. They show that a properly designed lever function acts like a local random oracle, providing unpredictable outputs for given inputs.

Key Results

  • Proof of Insecurity for Constants: The paper proves that if the lever function is a constant ($\ell(i) = c$), the private key can be recovered in polytime using continued fractions.
  • Resistance to Attacks: With the new lever function, the Continued Fraction Attack's complexity jumps to $O(2^n)$. For a standard block size of $n=80$ or higher, this is practically impossible to solve.
  • W-parameter Intersection Attack: The authors show that while this attack is polynomial in $n$, the search space for the intersection becomes too large to handle when the mapping is indeterminate, effectively neutralizing the threat.

Limitations and Future Work

The authors acknowledge that the simplified version of the cryptosystem ($\delta = 1$) is not "robust" if the bit-length of the modulus $M$ is too small (specifically under 1024 bits). In such cases, the problem can be reduced to a subset sum problem, which might be vulnerable to other types of lattice-based attacks.

For future work and practical implementation, the authors suggest that the lever function should be used in conjunction with the full REESSE1+ transform (keeping the random $\delta$ parameter) to provide "redundant security" and allow for shorter modulus lengths without compromising the system.

Summary updated

Abstract

The key transform of the REESSE1+ asymmetrical cryptosystem is Ci = (Ai * W ^ l(i)) ^ d (% M) with l(i) in Omega = {5, 7, ..., 2n + 3} for i = 1, ..., n, where l(i) is called a lever function. In this paper, the authors give a simplified key transform Ci = Ai * W ^ l(i) (% M) with a new lever function l(i) from {1, ..., n} to Omega = {+/-5, +/-6, ..., +/-(n + 4)}, where "+/-" means the selection of the "+" or "-" sign. Discuss the necessity of the new l(i), namely that a simplified private key is insecure if the new l(i) is a constant but not one-to-one function. Further, expound the sufficiency of the new l(i) from four aspects: (1) indeterminacy of the new l(i), (2) insufficient conditions for neutralizing the powers of W and W ^-1 even if Omega = {5, 6, ..., n + 4}, (3) verification by examples, and (4) running times of continued fraction attack and W-parameter intersection attack which are the two most efficient algorithms of the probabilistic polytime attacks so far. Last, the authors detail the relation between a lever function and a random oracle.
BibTeX
@misc{su2021new,
  author = {Shenghui Su and Ping Luo and Shuwang Lv and Maozhi Xu},
  title = {{A New Lever Function with Adequate Indeterminacy}},
  year = {2021},
  eprint = {2108.13086},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2108.13086},
}

Loading related content...

Figure