## CryptoDB

### Jun Xu

#### Publications

Year
Venue
Title
2021
EUROCRYPT
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.
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.
2006
EPRINT
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

Qi Cheng (1)
Lei Hu (1)
Yanbin Pan (2)
Santanu Sarkar (1)
Nick Wadleigh (1)
Huaxiong Wang (1)
Jiwen Zeng (1)
Xiaomin Zha (1)