Paper 2015/1223

Chosen-Ciphertext Security from Subset Sum

Sebastian Faust, Daniel Masny, and Daniele Venturi


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

Available format(s)
Publication info
A minor revision of an IACR publication in PKC 2016
public-key cryptographychosen-ciphertext securitysubset sum
Contact author(s)
Sebastian Faust @ ruhr-uni-bochum de
Daniel Masny @ ruhr-uni-bochum de
venturi @ di uniroma1 it
2016-06-08: revised
2015-12-23: received
See all versions
Short URL
Creative Commons Attribution


      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},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.