**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 format(s): **PDF | BibTeX Citation

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

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

[ Cryptology ePrint archive ]