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