Paper 2017/931

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

Michele Ciampi and Rafail Ostrovsky and Luisa Siniscalchi and Ivan Visconti

Abstract

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.