Paper 2009/285

Efficient Public Key Encryption Based on Ideal Lattices

Damien Stehlé, Ron Steinfeld, Keisuke Tanaka, and 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.