2011 | OriginalPaper | Buchkapitel
Precise Time and Space Simulatable Zero-Knowledge
verfasst von : Ning Ding, Dawu Gu
Erschienen in: Provable Security
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
Traditionally, the definition of zero-knowledge states that an interactive proof of
x
∈
L
provides zero (additional) knowledge if the view of any
polynomial-time
verifier can be reconstructed by a
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 resources (i.e. time and space) each 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
not only
in the same time,
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.