Paper 2014/339

Public-Coin Concurrent Zero-Knowledge in Logarithmic Rounds

Yi Deng

Abstract

We construct $O(\log^{1+\epsilon} n)$-round \emph{public-coin} concurrent zero knowledge arguments for NP from standard (against any polynomial-time adversary) collision-resistant hash functions for arbitrarily small constant $\epsilon$. Our construction is \emph{straight-line simulatable}. This is the first public-coin concurrent zero knowledge protocol based on standard/long-studied assumption that (almost) achieves the best known round-complexity of its private-coin counterpart [Prabhakaran et al., FOCS 02]. Previously, such public-coin constructions require either polynomial number of rounds [Goyal, STOC 13], newly-introduced assumptions [Chung et al., FOCS 13], or stronger model [Canetti et al., TCC 13]. This result has strong consequences: it yields the first (almost) logarithmic round simultaneously resettable arguments for NP and the first (almost) logarithmic round concurrent multi-party computation in the single input setting. These results significantly improve over the polynomial round-complexity of the best known protocols based on standard assumptions in both cases. Our technical contribution is two-fold. First, we introduce a simulation strategy called \emph{clearance} that yields a simulation tree of very \emph{special combinatorial structure} and enables us to instantiate Barak's protocol [Barak, FOCS 01] using the recent Ben-Sasson et al.'s quasi-linear construction of PCP system [Ben-Sasson et al., STOC 13] to obtain logarithmic round-complexity; secondly, we show how to modify Barak's protocol such that the soundness of overall construction does not rely on the (implicit/explicit) proof of knowledge property of the underlying universal argument/PCP system, which in turn allows us to benefit from progress on short PCP system of more general types \emph{without assuming stronger/superpolynomial hardness}.