International Association for Cryptologic Research

International Association
for Cryptologic Research

IACR News item: 30 June 2015

Hao Chen
ePrint Report ePrint Report
Many cryptographic schemes have been established based on the hardness of lattice problems. For the asymptotic efficiency, ideal lattices

in the ring of cyclotomic integers are suggested to be used in most such schemes. On the other hand in computational algebraic number theory one of the main problem

is called principle ideal problem (PIP). Its goal is to find a generators of any principle ideal in the ring of algebraic integers in any number field. In this paper we establish a polynomial time reduction from approximate shortest lattice vector problem for principle ideal lattices to their PIP\'s in many cyclotomic integer rings. Combining with the polynomial time quantum algorithm for PIP of arbitrary number fields, this implies that some approximate SVP problem for principle ideal lattices within a polynomial factor in some cyclotomic integer rings can be solved by polynomial time quantum algorithm.

Expand

Additional news items may be found on the IACR news page.