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 format(s): PDF | BibTeX Citation Note: 1/16: Added missing acknowledgments. Version: 20120117:052956 (All versions of this report) Discussion forum: Show discussion | Start new discussion