# Information Security and Cryptography Research Group

## Impossibility and Feasibility Results for Zero Knowledge with Public Keys

### Joël Alwen, Giuseppe Persiano, and Ivan Visconti

Advances in Cryptology — CRYPTO 2005, Lecture Notes in Computer Science, Springer-Verlag, vol. 3621, pp. 135-151, Aug 2005.

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},
}