Paper 2007/451

Precise Concurrent Zero Knowledge

Omkant Pandey, Rafael Pass, Amit Sahai, Wei-Lung Dustin Tseng, and Muthuramakrishnan Venkitasubramaniam

Abstract

\emph{Precise zero knowledge} introduced by Micali and Pass (STOC'06) guarantees that the view of any verifier $V$ can be simulated in time closely related to the \emph{actual} (as opposed to worst-case) time spent by $V$ in the generated view. We provide the first constructions of precise concurrent zero-knowledge protocols. Our constructions have essentially optimal precision; consequently this improves also upon the previously tightest non-precise concurrent zero-knowledge protocols by Kilian and Petrank (STOC'01) and Prabhakaran, Rosen and Sahai (FOCS'02) whose simulators have a quadratic worst-case overhead. Additionally, we achieve a statistically-precise concurrent zero-knowledge property---which requires simulation of unbounded verifiers participating in an unbounded number of concurrent executions; as such we obtain the first (even non-precise) concurrent zero-knowledge protocols which handle verifiers participating in a super-polynomial number of concurrent executions.

Metadata
Available format(s)
PDF
Category
Foundations
Publication info
Published elsewhere. Full version of a paper appearing at Eurocrypt 2008.
Keywords
Concurrent Zero KnowledgePrecise Simulation
Contact author(s)
omkant @ cs ucla edu
History
2008-02-01: last of 2 revisions
2007-12-05: received
See all versions
Short URL
https://ia.cr/2007/451
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2007/451,
      author = {Omkant Pandey and Rafael Pass and Amit Sahai and Wei-Lung Dustin Tseng and Muthuramakrishnan Venkitasubramaniam},
      title = {Precise Concurrent Zero Knowledge},
      howpublished = {Cryptology ePrint Archive, Paper 2007/451},
      year = {2007},
      note = {\url{https://eprint.iacr.org/2007/451}},
      url = {https://eprint.iacr.org/2007/451}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.