Cryptology ePrint Archive: Report 2009/285

Efficient Public Key Encryption Based on Ideal Lattices

Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa

Abstract: The potential high efficiency of public-key encryption based on structured lattices was first indicated by the NTRU cryptosystem, which was proposed about 10 years ago. Unfortunately, the security of NTRU is only heuristic. Thus, it remained an important research challenge to construct an efficient encryption scheme based on structured lattices which admits a proof of security relative to a well established cryptographic assumption. We make progress in addressing the above challenge. We show how to construct a CPA-secure public-key encryption scheme with security provably based on the worst case hardness of the approximate Shortest Vector Problem in structured ideal lattices. Under the assumption that the latter is exponentially hard to solve even with a quantum computer, our scheme resists any subexponential attack and offers (quasi-)optimal asymptotic performance: if $n$ is the security parameter, both keys are of bit-length $\softO(n)$ and the amortized costs of both encryption and decryption are $\softO(1)$ per message bit. Our construction adapts the trapdoor one-way function of Gentry, Peikert and Vaikuntanathan (STOC 2008), based on the Learning With Errors problem, to structured lattices. Our main technical tools are an adaptation of Ajtai's trapdoor key generation algorithm (ICALP 1999) to structured ideal lattices, and a re-interpretation of Regev's quantum reduction between the Closest Vector Problem and sampling short lattice vectors. We think these techniques are very likely to find further applications in the future.

Category / Keywords: public-key cryptography / Public-Key Encryption, Lattices, Provable Security, Post-Quantum Cryptography

Date: received 16 Jun 2009

Contact author: damien stehle at gmail com

Available formats: PDF | BibTeX Citation

Version: 20090616:201707 (All versions of this report)

Discussion forum: Show discussion | Start new discussion