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. 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 language | English |
|---|---|
| Title of host publication | Theory of Cryptography |
| Editors | Yael Kalai, Leonid Reyzin |
| Place of Publication | Cham |
| Publisher | Springer |
| Pages | 711-742 |
| Number of pages | 32 |
| ISBN (Electronic) | 978-3-319-70500-2 |
| ISBN (Print) | 978-3-319-70499-9 |
| DOIs | |
| Publication status | Published - 5 Nov 2017 |
| Event | 15th Theory of Cryptography Conference - The Charles Commons Conference Center, Johns Hopkins University, Baltimore, United States Duration: 12 Nov 2015 → 15 Nov 2017 https://www.iacr.org/workshops/tcc2017/ |
Publication series
| Name | Lecture Notes in Computer Science |
|---|---|
| Publisher | Springer, Cham |
| Volume | 10677 |
| ISSN (Print) | 0302-9743 |
| ISSN (Electronic) | 1611-3349 |
Conference
| Conference | 15th Theory of Cryptography Conference |
|---|---|
| Abbreviated title | TCC 2017 |
| Country/Territory | United States |
| City | Baltimore |
| Period | 12/11/15 → 15/11/17 |
| Internet address |