Cryptology ePrint Archive: Report 2012/506

Succinct Malleable NIZKs and an Application to Compact Shuffles

Melissa Chase and Markulf Kohlweiss and Anna Lysyanskaya and Sarah Meiklejohn

Abstract: 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.

Category / Keywords: foundations / malleability, generic constructions

Publication Info: TCC 2013

Date: received 1 Sep 2012, last revised 3 Mar 2013

Contact author: smeiklej at cs ucsd edu

Available format(s): PDF | BibTeX Citation

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

Version: 20130303:223712 (All versions of this report)

Short URL: ia.cr/2012/506

Discussion forum: Show discussion | Start new discussion