Chosen-Ciphertext Security from Subset Sum

Sebastian Faust; Daniel Masny; Daniele Venturi

Paper 2015/1223

Chosen-Ciphertext Security from Subset Sum

Sebastian Faust, Daniel Masny, and Daniele Venturi

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

Note: different choice of parameters, correction of wrong statements

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in PKC 2016
Keywords: public-key cryptography chosen-ciphertext security subset sum
Contact author(s): Sebastian Faust @ ruhr-uni-bochum de
Daniel Masny @ ruhr-uni-bochum de
venturi @ di uniroma1 it
History: 2016-06-08: revised; 2015-12-23: received; See all versions
Short URL: https://ia.cr/2015/1223
License: CC BY

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