Efficient Public Key Encryption Based on Ideal Lattices
Damien Stehlé, Ron Steinfeld, Keisuke Tanaka and Keita Xagawa
Abstract: We describe public key encryption schemes 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 is exponentially hard to solve
even with a quantum computer, we achieve CPA-security against
subexponential attacks, with (quasi-)optimal asymptotic performance:
if n is the security parameter, both keys are of bit-length O~(n) and
the amortized costs of both encryption and decryption are O~(1) per
message bit. 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) and a
re-interpretation of Regev's quantum reduction between the Bounded
Distance Decoding problem and sampling short lattice vectors.
Download: pdf.
Homepage