Impossibility and Feasibility Results for Zero Knowledge with Public Keys
Joël Alwen, 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].
BibTeX Citation
@inproceedings{AlPeVi05,
author = {Joël Alwen and Giuseppe Persiano and Ivan Visconti},
title = {Impossibility and Feasibility Results for Zero Knowledge with Public Keys},
editor = {Victor Shoup},
booktitle = {Advances in Cryptology --- CRYPTO 2005},
pages = {135-151},
series = {Lecture Notes in Computer Science},
volume = {3621},
year = {2005},
month = {8},
publisher = {Springer-Verlag},
}