ACAC Seminar Abstract

ACAC Seminar Abstract

ACAC Seminars

ACAC Seminar Abstract

Efficient Public Key Encryption Based on Ideal Lattices

Speaker: Ron Steinfeld
Date, Time: Fri, 20 Nov 2009 15:00

We describe a public key encryption scheme with security provably based on the worst case hardness of the approximate Shortest Vector Problem in some structured lattices, called ideal lattices. Under the assumption that the latter problem is exponentially hard to solve even with a quantum computer, our scheme achieves quasi-optimal asymptotic performance: secret/public key lengths are quasi-linear in the security parameter, and encryption/decryption times are quasilinear in the message length.

Our construction adapts the trapdoor one-way function of Gentry et al (STOC'08), 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'99) to structured ideal lattices, and a re-interpretation of Regev's quantum reduction between the Bounded Distance Decoding problem and sampling short lattice vectors.

Back to the top of this page