[FMV16] Chosen-Ciphertext Security from Subset Sum

Authors: Sebastian Faust, Daniel Masny, Daniele Venturi | Venue: PKC 2016 | Source

Abstract

We construct a public-key encryption (PKE) scheme whose security is polynomial-time equivalent to the hardness of the Subset Sum problem. Our scheme achieves the standard notion of indistinguishability against chosen-ciphertext attacks (IND-CCA) and can be used to encrypt messages of arbitrary polynomial length, improving upon a previous construction by Lyubashevsky, Palacio, and Segev (TCC 2010) which achieved only the weaker notion of semantic security (IND-CPA) and whose concrete security decreases with the length of the message being encrypted.

At the core of our construction is a trapdoor technique which originates in the work of Micciancio and Peikert (Eurocrypt 2012).

BibTeX

@Inproceedings{PKC:FauMasVen16,
  author = {Sebastian Faust and Daniel Masny and Daniele Venturi},
  title = {Chosen-Ciphertext Security from Subset Sum},
  pages = {35--46},
  editor = {Chen-Mou Cheng and Kai-Min Chung and Giuseppe Persiano and Bo-Yin Yang},
  booktitle = {PKC~2016: 19th International Conference on Theory and Practice of Public Key Cryptography, Part~I},
  volume = {9614},
  series = {Lecture Notes in Computer Science},
  address = {Taipei, Taiwan},
  month = {mar~6--9},
  publisher = {Springer Berlin Heidelberg, Germany},
  year = {2016},
  doi = {10.1007/978-3-662-49384-7_2},
}