Rafail Ostrovsky - Publications

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

Michele Ciampi, Rafail Ostrovsky, Luisa Siniscalchi, Ivan Visconti


In this work we start from the following two results in the state -of-the art:


4- round nn-maleable aero 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 provier to know the instance and the witness already at the 2nd round.


4 round multi-party coin tossing (MPCT): Garg et al.in Eurocrypto 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 NMZK from OWFs; moreover ΠNMZK is also delayed-input many-many synchronous NMZK argument.

2. a 4-round MPCt protocol ΠMPCT from one-to-oneOWFs;Π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 intrest

comment: TCC (1) 2017: 711-742

Fetch PDF file of the paper

Back to Publications List