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 cryptographychosen-ciphertext securitysubset 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
Creative Commons Attribution
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},
      note = {\url{https://eprint.iacr.org/2015/1223}},
      url = {https://eprint.iacr.org/2015/1223}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.