Paper 2015/1223 Original: eprint.iacr.org/2015/1223 ↗
Chosen-Ciphertext Security from Subset Sum
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).
Metadata
- Available format(s)
PDF- Publication info
- Preprint.
- History
- 2016-06-08: last updated
- 2015-12-23: published
- Short URL
- https://ia.cr/2015/1223
- License
- https://creativecommons.org/licenses/by/4.0/
BibTeX
@misc{cryptoeprint:2015/1223,
author = {Sebastian Faust and Daniel Masny and Daniele Venturi},
title = {Chosen-Ciphertext Security from Subset Sum},
howpublished = {Cryptology {ePrint} Archive, Paper 2015/1223},
year = {2015},
url = {https://eprint.iacr.org/2015/1223}
}