Cryptology ePrint Archive: Report 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_{MPCT}$ from one-to-one OWFs; $\Pi_{MPCT}$ uses $\Pi_{NMZK}$ as subprotocol and exploits the special properties (e.g., delayed input, many-many synchronous) of $\Pi_{NMZK}$.

Both $\Pi_{NMZK}$ and $\Pi_{MPCT}$ make 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.

Category / Keywords: delayed-input protocols, non-malleable zero knowledge, multi-party coin tossing, round-optimal protocols

Original Publication (with minor differences): IACR-TCC-2017

Date: received 21 Sep 2017, last revised 19 Apr 2018

Contact author: luisa siniscalchi88 at gmail com

Available format(s): PDF | BibTeX Citation

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 TCC 2017 publication and the coin-tossing protocol only requires one-to-one one-way functions. In eprint 2016/621 we presented a four-round delayed-input NMZK argument based on CRHFs.

Version: 20180419:090252 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]