Efficient public key encryption based on ideal lattices

Damien Stehlé*, Ron Steinfeld, Keisuke Tanaka, Keita Xagawa

*Corresponding author for this work

Research output: Chapter in Book/Report/Conference proceedingConference proceeding contribution

105 Citations (Scopus)

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 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.

Original languageEnglish
Title of host publicationAdvances in Cryptology - ASIACRYPT 2009 - 15th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings
EditorsMitsuru Matsui
Pages617-635
Number of pages19
Volume5912 LNCS
DOIs
Publication statusPublished - 2009
Event15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009 - Tokyo, Japan
Duration: 6 Dec 200910 Dec 2009

Publication series

NameLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume5912 LNCS
ISSN (Print)03029743
ISSN (Electronic)16113349

Other

Other15th International Conference on the Theory and Application of Cryptology and Information Security, ASIACRYPT 2009
CountryJapan
CityTokyo
Period6/12/0910/12/09

Fingerprint Dive into the research topics of 'Efficient public key encryption based on ideal lattices'. Together they form a unique fingerprint.

  • Cite this

    Stehlé, D., Steinfeld, R., Tanaka, K., & Xagawa, K. (2009). Efficient public key encryption based on ideal lattices. In M. Matsui (Ed.), Advances in Cryptology - ASIACRYPT 2009 - 15th International Conference on the Theory and Application of Cryptology and Information Security, Proceedings (Vol. 5912 LNCS, pp. 617-635). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 5912 LNCS). https://doi.org/10.1007/978-3-642-10366-7_36