Delayed-Input Non-Malleable Zero Knowledge and Multi-Party Coin Tossing in Four Rounds
In this work we start from the following two results in the state-of-the art:
- PDF / 1,031,182 Bytes
- 32 Pages / 439.37 x 666.142 pts Page_size
- 44 Downloads / 145 Views
DIEM, University of Salerno, Fisciano, Italy {mciampi,lsiniscalchi,visconti}@unisa.it 2 UCLA, Los Angeles, USA [email protected]
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 Π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.
1
Introduction
Non-malleable zero-knowledge (NMZK) and secure multi-party computation (MPC) are fundamental primitives in Cryptography. In this work we will study these two primitives and for the case of MPC we will focus on the coin-tossing functionality that is among the most studied functionalities. c International Association for Cryptologic Research 2017 Y. Kalai and L. Reyzin (Eds.): TCC 2017, Part I, LNCS 10677, pp. 711–742, 2017. https://doi.org/10.1007/978-3-319-70500-2_24
712
M. Ciampi et al.
NMZK. The first construction of NMZK was given by Dolev et al. in [15]. Later on, Barak in [2] showed the first constant-round construction. An improved construction was then given by Pass and Rosen in [35,36]. The work of Goyal et al. [23] obtained the first round-optimal construction requiring only 4 rounds and one-way functions (OWFs). Their construction requires the instance and the witness to be known already when the prover plays his first round. Their definition is the standard one-one definition where the adversary opens two sessions, one with a prover and one with a verifier. The fact that the instance and the witness need to be known already at the second round is an important limitation when NMZK is used as subprotocol to prove statements about another subprotocol played in parallel. Moreover the one-one security is an important limitation when NMZK is used in a multi-party scenario where several of such argument systems are played in parallel. The above two limitations clearly raise the following natural and interesting open questions: Open Ques
Data Loading...
