**Polynomial Time Reduction from Approximate Shortest Vector Problem to Principal Ideal Problem for Lattices in Some Cyclotomic Rings**

*Hao Chen*

**Abstract: **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 the principal ideal problem (PIP). Its goal is to find a generator of any principal ideal in the ring of algebraic integers in any number field. In this paper we give a polynomial time reduction from approximate shortest lattice vector problem for principal ideal lattices to their PIP's in cyclotomic integer rings of extension degrees $\phi(n)=2^{k-1}, k=2,3,\ldots$. Thus if a polynomial time quantum algorithm for PIP of arbitrary number fields could be proposed, this would implies that approximate SVP problem for principal ideal lattices within a polynomial factor in this kind cyclotomic integer rings can be solved by a polynomial time quantum algorithm.

**Category / Keywords: **foundations

**Date: **received 28 Jun 2015, last revised 15 Nov 2015

**Contact author: **haochen at hdu edu cn

**Available format(s): **PDF | BibTeX Citation

**Version: **20151115:220003 (All versions of this report)

**Short URL: **ia.cr/2015/639

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]