Cryptology ePrint Archive: Report 2015/1223

Chosen-Ciphertext Security from Subset Sum

Sebastian Faust; Daniel Masny; 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).

Category / Keywords: public-key cryptography, chosen-ciphertext security, subset sum

Original Publication (with minor differences): IACR-PKC-2016

Date: received 21 Dec 2015, last revised 8 Jun 2016

Contact author: Sebastian Faust at ruhr-uni-bochum de, Daniel Masny at ruhr-uni-bochum de, venturi@di uniroma1 it

Available format(s): PDF | BibTeX Citation

Note: different choice of parameters, correction of wrong statements

Version: 20160608:093914 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]