Cryptology ePrint Archive: Report 2015/639

Polynomial time reduction from approximate shortest vector problem to the principle ideal porblem for lattices in 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 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. Thus if a polynomial time quantum algorithm for PIP of arbitrary number fields could be proposed, this would implies that approximate SVP problem for principle ideal lattices within a polynomial factor in some cyclotomic integer rings can be solved by polynomial time quantum algorithm.

Category / Keywords: foundations /

Date: received 28 Jun 2015, last revised 1 Jul 2015

Contact author: haochen at hdu edu cn

Available format(s): PDF | BibTeX Citation

Version: 20150701:064537 (All versions of this report)

Short URL: ia.cr/2015/639

Discussion forum: Show discussion | Start new discussion