International Association
for Cryptologic Research

In this paper, we first propose a rigorous polynomial time algorithm based on the univariate Coppersmith theorem that factorizes an integer $N=PQ^r$ with unknown primes $P, Q$ and $r \geq 1$, for an arbitrary given prime $e>N^{\frac{1}{4r}}$ satisfying $e\mid \phi(N)$. Furthermore, the bound $e>N^{\frac{1}{4r}}$ is improved to $e>N^{\beta-r\beta^2}$ if the value of $\beta$ such that $Q\geq N^\beta$ is known. Moreover, these two bounds can also be obtained respectively when $e$ is no longer a prime number. Specifically, we address the scenario where $e$ is a square-free composite number with known factorization, as well as the case where $e$ is a composite number with known factorization, and the corresponding prime factors $P$ and $Q$ of $N$ satisfy $\gcd(P-1, Q-1)=2$. In both cases, in order to make the corresponding algorithms polynomial time, we limit the number of prime factors of $e$ to $O (\log \log N)$ and $r$ to be any integer constant. When applied to the $\phi$-hiding assumption, our bounds are significantly better than previous results. When applied to standard RSA moduli, we extend the case where $e$, which was involved in the previous best bound $e>N^{\frac{1}{4}}$, is no longer a prime number. This can highlight the security vulnerability introduced by the function $\mathrm{RSA}_{N,e}$, as discussed by Kakvi et al. in \cite{May2012}, being at least $e_i$-to-1 lossy for some prime factors $e_i$ of $e$. When applied to decompose the semi-smooth RSA subgroup moduli, we provide a rigorous proof for the second bound presented by Naccache and Stern for the first time. We validate the effectiveness of algorithms through experiments.

The Number Theoretic Transform (NTT) is widely employed to accelerate computations in lattice-based cryptography. At CHES 2024, Yu et al. introduced a class of side-channel attacks targeting NTT operations in the simplified Kyber and NTTRU schemes. Their work demonstrated that side-channel leakages - modeled as modular hints - can reveal partial information about the private key. These modular hints were subsequently integrated into the Learning With Errors (LWE) or NTRU lattices to reduce the overall computational complexity of key recovery. However, their approach fails to fully exploit the potential of these modular hints. Our key observation is that these modular hints is sufficient to directly construct lowdimensional lattices, rather than integrating them into the original high-dimensional one.In this paper, for the simplified CPA-secure Kyber scheme, we directly utilize the extracted modular hints to construct low-dimensional lattices. Subsequently, the adversary leverages lattice reduction algorithms to search for non-zero shortest vectors within these lattices. Our experimental results confirm that the full private key can be recovered within 400 seconds on a personal computer. Therefore, our attack practically recovers the private key. However, the method proposed by Yu et al. at CHES 2024 cannot achieve this.Furthermore, for the CCA-secure NTTRU scheme, we extract additional modular hints based on the side-channel methodology proposed by Yu et al. We combine the special structure of the NTTRU private key with the Gaussian elimination to generate low-dimensional lattices, and subsequently estimate the hardness of solving the non-zero Shortest Vector Problem using the estimation methodology adopted by Yu et al. The results indicate that we reduce the computational complexity of key recovery to 234-a significant improvement over the 2114 computational complexity reported by Yu et al. at CHES 2024.

Elliptic Curve Hidden Number Problem (EC-HNP) was first introduced by Boneh, Halevi and Howgrave-Graham at Asiacrypt 2001. To rigorously assess the bit security of the Diffie--Hellman key exchange with elliptic curves (ECDH), the Diffie--Hellman variant of EC-HNP, regarded as an elliptic curve analogy of the Hidden Number Problem (HNP), was presented at PKC 2017. This variant can also be used for practical cryptanalysis of ECDH key exchange in the situation of side-channel attacks. In this paper, we revisit the Coppersmith method for solving the involved modular multivariate polynomials in the Diffie--Hellman variant of EC-HNP and demonstrate that, for any given positive integer $d$, a given sufficiently large prime $p$, and a fixed elliptic curve over the prime field $\mathbb{F}_p$, if there is an oracle that outputs about $\frac{1}{d+1}$ of the most (least) significant bits of the $x$-coordinate of the ECDH key, then one can give a heuristic algorithm to compute all the bits within polynomial time in $\log_2 p$. When $d>1$, the heuristic result $\frac{1}{d+1}$ significantly outperforms both the rigorous bound $\frac{5}{6}$ and heuristic bound $\frac{1}{2}$. Due to the heuristics involved in the Coppersmith method, we do not get the ECDH bit security on a fixed curve. However, we experimentally verify the effectiveness of the heuristics on NIST curves for small dimension lattices.

Any non-zero ideal in a number field can be factored into a product of prime ideals. In this paper we report a surprising connection between the complexity of the shortest vector problem (SVP) of prime ideals in number fields and their decomposition groups. When applying the result to number fields popular in lattice based cryptosystems, such as power-of-two cyclotomic fields, we show that a majority of rational primes lie under prime ideals admitting a polynomial time algorithm for SVP. Although the shortest vector problem of ideal lattices underpins the security of the Ring-LWE cryptosystem, this work does not break Ring-LWE, since the security reduction is from the worst case ideal SVP to the average case Ring-LWE, and it is one-way.

The Modular Inversion Hidden Number Problem (MIHNP), introduced by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001, is briefly described as follows: Let $${\mathrm {MSB}}_{\delta }(z)$$ refer to the $$\delta $$ most significant bits of z. Given many samples $$\left( t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})\right) $$ for random $$t_i \in \mathbb {Z}_p$$, the goal is to recover the hidden number $$\alpha \in \mathbb {Z}_p$$. MIHNP is an important class of Hidden Number Problem.In this paper, we revisit the Coppersmith technique for solving a class of modular polynomial equations, which is respectively derived from the recovering problem of the hidden number $$\alpha $$ in MIHNP. For any positive integer constant d, let integer $$n=d^{3+o(1)}$$. Given a sufficiently large modulus p, $$n+1$$ samples of MIHNP, we present a heuristic algorithm to recover the hidden number $$\alpha $$ with a probability close to 1 when $$\delta /\log _2 p>\frac{1}{d\,+\,1}+o(\frac{1}{d})$$. The overall time complexity of attack is polynomial in $$\log _2 p$$, where the complexity of the LLL algorithm grows as $$d^{\mathcal {O}(d)}$$ and the complexity of the Gröbner basis computation grows as $$(2d)^{\mathcal {O}(n^2)}$$. When $$d> 2$$, this asymptotic bound outperforms $$\delta /\log _2 p>\frac{1}{3}$$ which is the asymptotic bound proposed by Boneh, Halevi and Howgrave-Graham in Asiacrypt 2001. It is the first time that a better bound for solving MIHNP is given, which implies that the conjecture that MIHNP is hard whenever $$\delta /\log _2 p<\frac{1}{3}$$ is broken. Moreover, we also get the best result for attacking the Inversive Congruential Generator (ICG) up to now.