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

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Abstract / Description of output

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 ΠNMZK from OWFs; moreover ΠNMZK is also a delayed-input many-many synchronous NMZK argument.

2. a 4-round MPCT protocol ΠMPCT from one-to-one OWFs; ΠMPCT uses ΠNMZK as subprotocol and exploits the special properties (e.g., delayed input, many-many synchronous) of ΠNMZK.
Both ΠNMZK and Π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.
Original languageEnglish
Title of host publicationTheory of Cryptography
EditorsYael Kalai, Leonid Reyzin
Place of PublicationCham
PublisherSpringer International Publishing AG
Number of pages32
ISBN (Electronic)978-3-319-70500-2
ISBN (Print)978-3-319-70499-9
Publication statusPublished - 5 Nov 2017
Event15th Theory of Cryptography Conference - The Charles Commons Conference Center, Johns Hopkins University, Baltimore, United States
Duration: 12 Nov 201515 Nov 2017

Publication series

NameLecture Notes in Computer Science
PublisherSpringer, Cham
ISSN (Print)0302-9743
ISSN (Electronic)1611-3349


Conference15th Theory of Cryptography Conference
Abbreviated titleTCC 2017
Country/TerritoryUnited States
Internet address


Dive into the research topics of 'Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds'. Together they form a unique fingerprint.

Cite this