Impossibility and Feasibility Results for Zero Knowledge with Public Keys
Joel Alwen and Giuseppe Persiano and Ivan Visconti
In this paper, we continue the study of the round complexity of black-box zero knowledge in the bare public-key (BPK, for short) model previously started by Micali and Reyzin in [MR01a]. Specifically we show the impossibility of 3-round concurrent (and thus resettable) black-box zero- knowledge argument systems with sequential soundness for non-trivial languages. In light of the previous state-of-the-art, our result completes the analysis of the round complexity of black-box zero knowledge in the BPK model with respect to the notions of soundness and black-box zero knowledge.
Further we give sufficient conditions for the existence of a 3-round reset- table zero-knowledge proof (in contrast to argument) system with concur- rent soundness for NP in the upperbounded public-key model introduced in [MR01b].