Paper 2013/691

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

Benoit Libert, Thomas Peters, Marc Joye, and Moti Yung

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. 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 $O(2t)$ 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
NIZK proofssimulation-soundnesschosen-ciphertext securityhomomorphic cryptography
Contact author(s)
benoit libert @ technicolor com
History
2013-10-28: received
Short URL
https://ia.cr/2013/691
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2013/691,
      author = {Benoit Libert and Thomas Peters and Marc Joye and Moti Yung},
      title = {Non-Malleability from Malleability:  Simulation-Sound Quasi-Adaptive NIZK Proofs and CCA2-Secure Encryption from Homomorphic Signatures},
      howpublished = {Cryptology ePrint Archive, Paper 2013/691},
      year = {2013},
      note = {\url{https://eprint.iacr.org/2013/691}},
      url = {https://eprint.iacr.org/2013/691}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.