Paper 2017/931

Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, and Ivan Visconti


In this work we start from the following two results in the state-of-the art: 1) 4-round non-malleable zero knowledge (NMZK): Goyal et al. in FOCS 2014 showed the first 4-round one-one NMZK argument from one-way functions (OWFs). Their construction requires the prover to know the instance and the witness already at the 2nd round. 2) 4-round multi-party coin tossing (MPCT): Garg et al. in Eurocrypt 2016 showed the first 4-round protocol for MPCT. Their result crucially relies on 3-round 3-robust parallel non-malleable commitments. So far there is no candidate construction for such a commitment scheme under standard polynomial-time hardness assumptions. We improve the state-of-the art on NMZK and MPCT by presenting the following two results: 1) a delayed-input 4-round one-many NMZK argument $\Pi_{nmzk}$ from OWFs; moreover $\Pi_{nmzk}$ is also a delayed-input many-many synchronous NMZK argument. 2) a 4-round MPCT protocol $\Pi_{mpcf}$ from one-to-one OWFs; $\Pi_{mpcf}$ uses $\Pi_{nmzk}$ as subprotocol and exploits the special properties (e.g., delayed input, many-many synchronous) of $\Pi_{nmzk}$. $\Pi_{mpcf}$ makes use of a special proof of knowledge that offers additional security guarantees when played in parallel with other protocols. The new technique behind such a proof of knowledge is an additional contribution of this work and is of independent interest.

Note: A preliminary version of this work was submitted to Crypto 2017 and the coin-tossing protocols also required ZAPs. This is the full version of the paper appeared in TCC 2017 that however includes a protocol from the Crypto 2017 submission. See the "Acknowledgements" section for further explanations.

Available format(s)
Publication info
A minor revision of an IACR publication in TCC 2017
delayed-input protocolsnon-malleable zero knowledgemulti-party coin tossinground-optimal protocols
Contact author(s)
luisa siniscalchi88 @ gmail com
2018-10-22: last of 2 revisions
2017-09-25: received
See all versions
Short URL
Creative Commons Attribution


      author = {Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Ivan Visconti},
      title = {Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds},
      howpublished = {Cryptology ePrint Archive, Paper 2017/931},
      year = {2017},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.