Succinct Malleable NIZKs and an Application to Compact Shuffles

Melissa Chase, Markulf Kohlweiss, Anna Lysyanskaya, Sarah Meiklejohn

Research output: Chapter in Book/Report/Conference proceedingConference contribution


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.
Original languageEnglish
Title of host publicationTheory of Cryptography - 10th Theory of Cryptography Conference, TCC 2013, Tokyo, Japan, March 3-6, 2013. Proceedings
Number of pages20
ISBN (Electronic)978-3-642-36594-2
Publication statusE-pub ahead of print - 2013
Event10th Theory of Cryptography Conference - Tokyo, Japan
Duration: 3 Mar 20136 Mar 2013


Conference10th Theory of Cryptography Conference
Abbreviated titleTCC2013
Internet address


Dive into the research topics of 'Succinct Malleable NIZKs and an Application to Compact Shuffles'. Together they form a unique fingerprint.

Cite this