Constant-Round Coin-Tossing With a Man in the Middle
or
Realizing the Shared Random String Model
Boaz Barak
Abstract
We present the first constant-round non-malleable
commitment scheme and the first constant-round
non-malleable zero-knowledge argument system, as defined by Dolev,
Dwork and Naor. Previous constructions either used a non-constant
number of rounds, or were only secure under stronger setup
assumptions. An example for such an assumption is the shared
random string model where we assume all parties have access to a
reference string that was chosen uniformly at random by a trusted
dealer.
We obtain these results by defining an adequate notion of
non-malleable coin-tossing, and presenting a
constant-round protocol that satisfies it. This protocol
allows us to transform protocols that are non-malleable in (a
modified notion of) the shared random string model into
protocols that are non-malleable in the plain model
(without any trusted dealer or setup assumptions). Observing that
known constructions of a non-interactive non-malleable
zero-knowledge argument systems in the shared random string model
(De Santis et. al., 2001) are in fact non-malleable in the
modified model, and combining them with our coin-tossing protocol we
obtain the results mentioned above.
The techniques we use are different from those used in previous
constructions of non-malleable protocols. In particular our
protocol uses diagonalization and a non-black-box proof of
security (in a sense similar to Barak's zero-knowledge argument).
Versions
- Revised version 12/2003 (to appear soon)
-
Extended abstract appeared in FOCS 2002
- Version from July 2002
[postscript]
Powerpoint XP presentation
home | research | links | cv | pictures
|