## CryptoDB

### Yanbin Pan

#### Affiliation: Academy of Mathematics and Systems Science, CAS

#### Publications

**Year**

**Venue**

**Title**

2019

CRYPTO

New Results on Modular Inversion Hidden Number Problem and Inversive Congruential Generator
📺
Abstract

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.

2008

EPRINT

Cryptanalysis of the Cai-Cusick Lattice-based Public-key Cryptosystem
Abstract

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)