[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},
}