6 papers
Faster SVP in Polynomial Space
Yansong Feng, Yiming Gao, Jiaqi Liu
Kannan's algorithm, as analyzed by Hanrot and Stehlé in 2007, solves the exact Euclidean shortest vector problem in polynomial space and time. In the classi…
SVP Is NP-Hard for Some Rank-2 Cyclotomic Modules
Jiaqi Liu, Yansong Feng, Yanbin Pan
Let range over primes congruent to modulo . Let be a primitive th root of unity, and put , with ring of integers $\mathcal{O}_K=\mathbb{Z}[ζ_…
CVP Is NP-Complete for Principal Cyclotomic Ideals
Jiaqi Liu, Yansong Feng, Yanbin Pan
We prove that exact Euclidean decision-CVP is -complete on the coefficient lattices of nonzero principal ideals in the power-of-two cyclotomic rings $R_d:=\mathbb{Z}[y…
Subset Balancing and Generalized Subset Sum via Lattices
Yiming Gao, Yansong Feng, Honggang Hu +1
We study the Subset Balancing problem: given and a coefficient set , find a nonzero vector such that . The st…
On Factoring and Power Divisor Problems via Rank-3 Lattices and the Second Vector
Yiming Gao, Yansong Feng, Honggang Hu +1
We propose a deterministic algorithm based on Coppersmith's method that employs a rank-3 lattice to address factoring-related problems. An interesting aspect of our approach is tha…
Embedding Integer Lattices as Ideals into Polynomial Rings
Yihang Cheng, Yansong Feng, Yanbin Pan
Many lattice-based crypstosystems employ ideal lattices for high efficiency. However, the additional algebraic structure of ideal lattices usually makes us worry about the security…