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

Available format(s)
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
NIZK proofssimulation-soundnesschosen-ciphertext securityhomomorphic cryptography
Contact author(s)
benoit libert @ technicolor com
History
Short URL
https://ia.cr/2013/691

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.