Paper 2012/506

Succinct Malleable NIZKs and an Application to Compact Shuffles

Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, and Sarah Meiklejohn


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, Lysyanskaya, 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. Despite these initial steps, a number of natural problems remained: (1) their construction of controlled-malleable proofs relies on the inherent malleability of Groth-Sahai proofs and is thus not based on generic primitives; (2) the classes of allowable transformations they can support are somewhat restrictive. In this paper, we address these issues by providing a generic construction of controlled-malleable proofs using succinct non-interactive arguments of knowledge, or SNARGs for short. Our construction can support very general classes of transformations, as we no longer rely on the transformations that Groth-Sahai proofs can support.

Note: Updated recursive extraction proof and definition of adaptive knowledge extraction.

Available format(s)
Publication info
Published elsewhere. TCC 2013
malleabilitygeneric constructions
Contact author(s)
smeiklej @ cs ucsd edu
2013-03-03: last of 2 revisions
2012-09-03: received
See all versions
Short URL
Creative Commons Attribution


      author = {Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn},
      title = {Succinct Malleable NIZKs and an Application to Compact Shuffles},
      howpublished = {Cryptology ePrint Archive, Paper 2012/506},
      year = {2012},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.