## CryptoDB

### Yanbin Pan

#### Publications

Year
Venue
Title
2019
CRYPTO
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.
2014
PKC
2014
EPRINT
2008
EPRINT
In 1998, Cai and Cusick proposed a lattice-based public-key cryptosystem based on the similar ideas of the Ajtai-Dwork cryptosystem, but with much less data expansion. However, they didn't give any security proof. In our paper, we present an efficient ciphertext-only attack which runs in polynomial time against the cryptosystem to recover the message, so the Cai-Cusick lattice-based public-key cryptosystem is not secure. We also present two chosen-ciphertext attacks to get a similar private key which acts as the real private key.

#### Coauthors

Yingpu Deng (1)
Gengran Hu (2)
Lei Hu (1)
Santanu Sarkar (1)
Huaxiong Wang (1)
Jun Xu (1)
Feng Zhang (2)