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

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

Conference

Conference10th Theory of Cryptography Conference
Abbreviated titleTCC2013
CountryJapan
CityTokyo
Period3/03/136/03/13
Internet address

Fingerprint

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

Cite this