Date Added: Sep 2012
Depending on the application, malleability in cryptography can be viewed as either a flaw or - especially if sufficiently understood and restricted - a feature. In this vein, Chase, Kohlweiss, Lysyan-skaya, and Meiklejohn recently defined malleable zero-knowledge proofs, and showed how to control the set of allowable transformations on proofs. As an application, they construct the first compact verifiable shuffle, in which one such controlled-malleable proof suffices to prove the correctness of an entire multi-step shuffle. In this paper, the authors address these open problems by providing a generic construction of controlled-malleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short.