Cryptology ePrint Archive: Report 2012/012

Malleable Proof Systems and Applications

Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn

Abstract: Malleability for cryptography is not necessarily an opportunity for attack, but in many cases a potentially useful feature that can be exploited. In this work, we examine notions of malleability for non-interactive zero-knowledge (NIZK) proofs. We start by defining a malleable proof system, and then consider ways to meaningfully control the malleability of the proof system, as in many settings we would like to guarantee that only certain types of transformations can be performed. We also define notions for the cases in which we do not necessarily want a user to know that a proof has been obtained by applying a particular transformation; these are analogous to function/circuit privacy for encryption.

As our motivating application, we consider a shorter proof for verifiable shuffles. Our controlled-malleable proofs allow us for the first time to use one compact proof to prove the correctness of an entire multi-step shuffle. Each authority takes as input a set of encrypted votes and a controlled-malleable NIZK proof that these are a shuffle of the original encrypted votes submitted by the voters; it then permutes and re-randomizes these votes and updates the proof by exploiting its controlled malleability. As another application, we generically use controlled-malleable proofs to realize a strong notion of encryption security.

Finally, we examine malleability in existing proof systems and observe that Groth-Sahai proofs are malleable. We then go beyond this observation by characterizing all the ways in which they are malleable, and use them to efficiently instantiate our generic constructions from above; this means we can instantiate our proofs and all their applications using only the Decision Linear (DLIN) assumption.

Category / Keywords: foundations / zero knowledge, malleability

Publication Info: To appear in Eurocrypt 2012.

Date: received 8 Jan 2012, last revised 16 Jan 2012

Contact author: smeiklej at cs ucsd edu

Available formats: PDF | BibTeX Citation

Note: 1/16: Added missing acknowledgments.

Version: 20120117:052956 (All versions of this report)

Discussion forum: Show discussion | Start new discussion