## CryptoDB

### Jun Xu

#### 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.

2006

EPRINT

A New family of Ideal Multipartite Access Structure Based on MSP
Abstract

Any access structure is the multipartite access structure, The set of players is devided into K different entities, in such a way that all players of the same role in the multipartite access structure, we suppose there is a threshold access structure in every different entity, there is also a threshold access structure in K different entities, we consider their composite access structure, then a new family of Multipartite Access Structure will be given, we will provide secret shring scheme realizing it and prove it is ideal.

#### Coauthors

- Lei Hu (1)
- Yanbin Pan (1)
- Santanu Sarkar (1)
- Huaxiong Wang (1)
- Jiwen Zeng (1)
- Xiaomin Zha (1)