TY - GEN
T1 - Efficient public key encryption based on ideal lattices
AU - Stehlé, Damien
AU - Steinfeld, Ron
AU - Tanaka, Keisuke
AU - Xagawa, Keita
PY - 2009
Y1 - 2009
N2 - 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 and the amortized costs of both encryption and decryption are 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.
AB - 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 and the amortized costs of both encryption and decryption are 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.
UR - http://www.scopus.com/inward/record.url?scp=72449142727&partnerID=8YFLogxK
U2 - 10.1007/978-3-642-10366-7_36
DO - 10.1007/978-3-642-10366-7_36
M3 - Conference proceeding contribution
AN - SCOPUS:72449142727
SN - 3642103650
SN - 9783642103650
VL - 5912 LNCS
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 617
EP - 635
BT - Advances in Cryptology - ASIACRYPT 2009 - 15th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
A2 - Matsui, Mitsuru
T2 - 15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009
Y2 - 6 December 2009 through 10 December 2009
ER -