The Modular Inversion Hidden Number Problem (MIHNP), which was proposed at Asiacrypt 2001 by Boneh, Halevi, and Howgrave-Graham, is summarized as follows: Assume that the$\delta $most significant bits of$z$are denoted by${\mathrm {MSB}}_{\delta }(z)$. The goal is to retrieve the hidden number$\alpha \in \mathbb {Z}_{p}$given many samples$\left ({t_{i}, {\mathrm {MSB}}_{\delta }((\alpha + t_{i})^{-1} \bmod {p})}\right)$for random$t_{i} \in \mathbb {Z}_{p}$. MIHNP is a significant subset of Hidden Number Problems. Eichenauer and Lehn introduced the Inversive Congruential Generator (ICG) in 1986. It is basically characterized as follows: For iterated relations$v_{i+1}=(av^{-1}_{i}+b)\bmod {p}$with a secret seed$v_{0} \in \mathbb {Z}_{p}$, each iteration produces$\mathrm {MSB}_{\delta }(v_{i+1})$where$i \geq 0$. The ICG family of pseudorandom number generators is a significant subclass of number-theoretic pseudorandom number generators. Sakai-Kasahara scheme is an identity-based encryption (IBE) system proposed by Sakai and Kasahara. It is one of the few commercially implemented identity-based encryption schemes. We explore the Coppersmith approach for solving a class of modular polynomial equations, which is derived from the recovery issue for the hidden number$\alpha $in MIHNP and the secret seed$v_{0}$in ICG, respectively. Take a positive integer$n=d^{3+o(1)}$for some positive integer constant$d$. We propose a heuristic technique for recovering the hidden number$\alpha $or secret seed$v_{0}$with a probability close to 1 when$\delta /\log _{2} p>\frac {1}{d+1}+o\left({\frac {1}{d}}\right)$. The attack’s total time complexity is polynomial in the order of$\log _{2} p$, with the complexity of the LLL algorithm increasing as$d^{\mathcal {O}(d)}$and the complexity of the Gröbner basis computation increasing as$d^{\mathcal {O}(n)}$. When$d> 2$, this asymptotic bound surpasses the asymptotic bound$\delta /\log _{2} p>\frac {1}{3}$established by Boneh, Halevi, and Howgrave-Graham at Asiacrypt 2001. This is the first time a more precise constraint for solving MIHNP is established, implying that the claim that MIHNP is difficult is violated whenever$\delta /\log _{2} p < \frac {1}{3}$. Then we study ICG. To our knowledge, we achieve the best performance for attacking ICG to date. Finally, we provide an MIHNP-based lattice approach that recovers the signer’s secret key in the Sakai-Kasahara type signatures when the most (least) significant bits of the signing exponents are exposed. This improves the existing work in this direction.

In this study, the authorspresent two rigorous algorithms to certify the trapdoor permutation property of the RSAfunction , where is a multi‐power RSA modulus with unknown factorisation and r is a known positive integer. Their work gives effective certification for a prime exponent e when and for a composite integer when for , where is a known prime, is a positive integer, and is some small enough constant. The algorithms apply Coppersmith's method for solving univariate modular polynomial equations and run in time , where is a constant number.

Two public key cryptosystems based on the two intractable number‐theoretic problems, integer factorisation and simultaneous Diophantine approximation, were proposed in 2005 and 2009, respectively. In this study, the authors break these two cryptosystems for the recommended minimum parameters by solving the corresponding modular linear equations with small unknowns. For the first scheme, the public modulus is factorised and the secret key is recovered with the Gauss algorithm. By using the LLL basis reduction algorithm for a seven‐dimensional lattice, the public modulus in the second scheme is also factorised and the plaintext is recovered from a ciphertext. The author's attacks are efficient and verified by experiments which were done within 5s.

The original Number Theory Research Unit (NTRU) public key cryptosystem is vulnerable to multiple transmission attacks, and the designers of NTRU presented two countermeasures to prevent such attacks. In this study, the authors show that the first countermeasure is still not secure, the plaintext can be revealed by a linearisation attack technique. Moreover, they demonstrate that the first countermeasure is even not secure for broadcast attacks, a class of more general attacks than multiple transmission attacks. For the second countermeasure, they show that one special case of its padding function for the plaintext is also insecure and the original plaintext can be obtained by lattice methods.

Two knapsack‐based public key cryptosystems were proposed recently, in which the entries of the secret knapsack sequences are composed of products of random integers and the knapsack problems have nonbinary solutions. These features make the cryptosystems to be secure against low density attacks. In this study, the authors present lattice‐based complete private key recovery attacks on these two schemes. The authors attacks firstly find short vectors related to the public key and with some orthogonality to the secret knapsack sequences and then recover some components of the private key by computing common factors of the entries of the short vectors. Especially, the authors attack can both completely recover the unique key for these two schemes. The attacks are of practical complexities and verified by experiments.