Efficient Public-Key Encryption from Ideal Lattices
by Ron Steinfeld
Abstract: 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. We also discuss research directions extending this work.
Ron Steinfeld is an ARC research fellow (ARF) at the Centre for Advanced Computing â€“ Algorithms and Cryptography (ACAC) at Macquarie University. His research interests are in the design and analysis of cryptographic algorithms and protocols, and the formulation and proof of their security properties. He obtained his PhD in computer science from Monash University in 2003, and a BE (Elec. Eng.) (Hons, First Class) and BSc (Math./Phys.) from Monash University in 2000.
For More Information: contact: David Wood. email: email@example.com