On Round-Optimal Zero Knowledge in the Bare Public-Key Model

In this paper we revisit previous work in the

BPK

model and point out subtle problems concerning security proofs of concurrent and resettable zero knowledge (

$\mathsf{c}{\mathcal{ZK}}$

and

${\mathsf{r}{\mathcal{ZK}}}$

, for short). Our analysis shows that the

${\mathsf c}{\mathcal{ZK}}$

and

${\mathsf{r}}{\mathcal{ZK}}$

simulations proposed for previous (in particular

all

round-optimal) protocols are distinguishable from real executions. Therefore some of the questions about achieving round optimal

${\mathsf{c}}{\mathcal{ZK}}$

and

${\mathsf{r}\mathcal{ZK}}$

in the

BPK

model are still open. We then show our main protocol,

$\Pi_{\mathsf{c}{\mathcal{ZK}}}$

, that is a round-optimal concurrently sound

$\mathsf{c}\mathcal{ZK}$

argument of knowledge (

AoK

, for short) for

NP

under standard complexity-theoretic assumptions. Next, using complexity leveraging arguments, we show a protocol

$\Pi_{\mathsf{r}\mathcal{ZK}}$

that is round-optimal and concurrently sound

${\mathsf{r}}{\mathcal{ZK}}$

for

NP

. Finally we show that

${\Pi_{\mathsf{c}\mathcal{ZK}}}$

and

$\Pi_{{\mathsf{r}}{\mathcal{ZK}}}$

can be instantiated efficiently through transformations based on number-theoretic assumptions. Indeed, starting from any language admitting a perfect Σ-protocol, they produce concurrently sound protocols

${\bar \Pi_{\mathsf{c}\mathcal{ZK}}}$

and

$\bar \Pi_{\mathsf{r}\mathcal{ZK}}$

, where

${\bar \Pi_{\mathsf{c}\mathcal{ZK}}}$

is a round-optimal

$\mathsf{c}\mathcal{ZK}\mathsf{AoK}$

, and

${\bar \Pi}_{{\mathsf{r}{\mathcal{ZK}}}}$

is a 5-round

${\mathsf{r}}{\mathcal{ZK}}$

argument. The

${\mathsf{r}}{\mathcal{ZK}}$

protocols are mainly inherited from the ones of Yung and Zhao [31].