Constant-Round Coin-Tossing with a Man in the Middle or Realizing the Shared Random String Model

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 onlysecure under stronger setup assumptions. An example of 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).