Melissa Chase
Microsoft Research

Malleable Proof Systems and Applications

In recent years, malleability for cryptography has changed from being
viewed as an opportunity for attack that must be eliminated, to being
considered a potentially useful feature that can be exploited.  In
this work, we continue to view malleability as a feature and to this
end examine notions of malleability for zero-knowledge proofs.  We
start by defining a basic notion of a malleable proof system, and then
note that there are settings where an all-or-nothing notion of
malleability that either prevents all transformations or allows any
transformation, is difficult to use in many situations.  Thus we
consider ways to meaningfully \emph{control} the malleability of the
proof system as well; this captures the idea that there are many
settings in which we would like to guarantee that only certain types
of transformations can be performed.

As our motivating application, we consider obtaining a shorter proof
for verifiable shuffles. As we will see, our controlled-malleable
proofs allow us for the first time to use one compact proof to prove
the correctness  of an entire multi-step shuffle, rather than
requiring a proof from every authority involved.  As another
application, we generically use controlled-malleable proofs to realize
a strong notion of encryption security.

Finally, we show that using Groth-Sahai proofs, we can efficiently
instantiate our generic constructions from above; this means we can
instantiate our proofs and all their applications using only the DLIN

Joint work with:
Markulf Kohlweiss, Anna Lysyanskaya, and Sarah