**Precise Time and Space Simulatable Zero-Knowledge**

*Ning Ding and Dawu Gu*

**Abstract: **Traditionally, the definition of zero-knowledge states that an
interactive proof of $x\in L$ provides zero (additional) knowledge
if the view of any \emph{polynomial-time} verifier can be
reconstructed by a \emph{polynomial-time} simulator. Since this
definition only requires that the worst-case running-time of the
verifier and simulator are polynomials, zero-knowledge becomes a
worst-case notion.

In STOC'06, Micali and Pass proposed a new notion of precise zero-knowledge, which captures the idea that the view of any verifier in every interaction can be reconstructed in (almost) the same time (i.e., the view can be ``indistinguishably reconstructed''). This is the strongest notion among the known works towards precislization of the definition of zero-knowledge.

However, as we know, there are two kinds of computational resources (i.e. time and space) that every algorithm consumes in computation. Although the view of a verifier in the interaction of a precise zero-knowledge protocol can be reconstructed in almost the same time, the simulator may run in very large space while at the same time the verifier only runs in very small space. In this case it is still doubtful to take indifference for the verifier to take part in the interaction or to run the simulator. Thus the notion of precise zero-knowledge may be still insufficient. This shows that precislization of the definition of zero-knowledge needs further investigation.

In this paper, we propose a new notion of precise time and space simulatable zero-knowledge (PTSSZK), which captures the idea that the view of any verifier in each interaction can be reconstructed \emph{not only} in the same time, \emph{but also} in the same space. We construct the first PTSSZK proofs and arguments with simultaneous linear time and linear space precisions for all languages in $\NP$. Our protocols do not use noticeably more rounds than the known precise zero-knowledge protocols, and the probability analysis of the successful extraction of the new simulation strategy may be of independent interests.

**Category / Keywords: **foundations / Zero-Knowledge, Precise Zero-Knowledge, Proofs of Knowledge, Interactive Proofs and Arguments

**Publication Info: **manuscript, not published

**Date: **received 3 Sep 2009

**Contact author: **cs dingning at gmail com

**Available format(s): **PDF | BibTeX Citation

**Version: **20090904:054716 (All versions of this report)

**Discussion forum: **Show discussion | Start new discussion

[ Cryptology ePrint archive ]