Summary: 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 \(\Sigma \)-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 M. Yung and Y. Zhao [Advances in cryptology – EUROCRYPT 2007, Lect. Notes Comput. Sci. 4515, 129–147 (2007; Zbl 1141.94382)].
For the entire collection see [Zbl 1239.94002].