Non-Malleability from Malleability: Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure Encryption from Homomorphic Signatures

Abstract : Verifiability is central to building protocols and systems with integrity. Initially, efficient methods employed the Fiat-Shamir heuristics. Since 2008, the Groth-Sahai techniques have been the most efficient in constructing non-interactive witness indistinguishable and zero-knowledge proofs for algebraic relations in the standard model. For the important task of proving membership in linear subspaces, Jutla and Roy (Asiacrypt 2013) gave significantly more efficient proofs in the quasi-adaptive setting (QA-NIZK). For membership of the row space of a $t \times n$ matrix, their QA-NIZK proofs save $\Omega(t)$ group elements compared to Groth-Sahai. Here, we give QA-NIZK proofs made of a {\it constant} number group elements -- regardless of the number of equations or the number of variables -- and additionally prove them {\it unbounded} simulation-sound. Unlike previous unbounded simulation-sound Groth-Sahai-based proofs, our construction does not involve quadratic pairing product equations and does not rely on a chosen-ciphertext-secure encryption scheme. Instead, we build on structure-preserving signatures with homomorphic properties. We apply our methods to design new and improved CCA2-secure encryption schemes. In particular, we build the first efficient threshold CCA-secure keyed-homomorphic encryption scheme ({\it i.e.}, where homomorphic operations can only be carried out using a dedicated evaluation key) with publicly verifiable ciphertexts.
Type de document :
Communication dans un congrès
P. Nguyen and E. Oswald. Eurocrypt 2014, May 2014, Copenhagen, Denmark. 2014
Liste complète des métadonnées

Littérature citée [55 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-00983147
Contributeur : Benoit Libert <>
Soumis le : jeudi 24 avril 2014 - 19:21:49
Dernière modification le : samedi 21 avril 2018 - 01:27:23
Document(s) archivé(s) le : jeudi 24 juillet 2014 - 11:55:56

Fichier

sim-sound-full-version.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

  • HAL Id : hal-00983147, version 1

Collections

Citation

Benoît Libert, Thomas Peters, Marc Joye, Moti Yung. Non-Malleability from Malleability: Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure Encryption from Homomorphic Signatures. P. Nguyen and E. Oswald. Eurocrypt 2014, May 2014, Copenhagen, Denmark. 2014. 〈hal-00983147〉

Partager

Métriques

Consultations de la notice

326

Téléchargements de fichiers

316