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

Chosen-ciphertext security from subset sum / Faust, Sebastian; Masny, Daniel; Venturi, Daniele. - STAMPA. - 9614:(2016), pp. 35-46. ((Intervento presentato al convegno 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2016 tenutosi a Taipei, TW nel 6th-9th March, 2016 [10.1007/978-3-662-49384-7_2].

Chosen-ciphertext security from subset sum

Venturi, Daniele
2016

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).
Public-Key ryptography (PKC 2016) 19th IACR International Conference on Practice and Theory in Public-Key: Proceedings Part 1.
Berlin; Heidelberg
Springer Verlag
9783662493830
978-3-662-49384
Faust, Sebastian; Masny, Daniel; Venturi, Daniele
Chosen-ciphertext security from subset sum / Faust, Sebastian; Masny, Daniel; Venturi, Daniele. - STAMPA. - 9614:(2016), pp. 35-46. ((Intervento presentato al convegno 19th IACR International Conference on Practice and Theory in Public-Key Cryptography, PKC 2016 tenutosi a Taipei, TW nel 6th-9th March, 2016 [10.1007/978-3-662-49384-7_2].
File in questo prodotto:
File Dimensione Formato  
1223(1).pdf

embargo fino al 31/12/2017

Descrizione: Full version
Tipologia: Post-print referato (Refereed author’s manuscript)
Licenza: Tutti i diritti riservati (All rights reserved)
Dimensione 344.38 kB
Formato Adobe PDF
344.38 kB Adobe PDF Visualizza/Apri

I documenti in IRIS sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione

Utilizza questo identificativo per citare o creare un link a questo documento: https://hdl.handle.net/11572/156040
Citazioni
  • ???jsp.display-item.citation.pmc??? ND
  • Scopus 4
  • ???jsp.display-item.citation.isi??? 3
social impact