International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Paper: Precise Concurrent Zero Knowledge

Authors:
Omkant Pandey
Rafael Pass
Amit Sahai
Wei-Lung Dustin Tseng
Muthuramakrishnan Venkitasubramaniam
Download:
URL: http://eprint.iacr.org/2007/451
Search ePrint
Search Google
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.
BibTeX
@misc{eprint-2007-13731,
  title={Precise Concurrent Zero Knowledge},
  booktitle={IACR Eprint archive},
  keywords={foundations / Concurrent Zero Knowledge, Precise Simulation},
  url={http://eprint.iacr.org/2007/451},
  note={Not yet published. omkant@cs.ucla.edu 13851 received 4 Dec 2007},
  author={Omkant Pandey and Rafael Pass and Amit Sahai and Wei-Lung Dustin Tseng and Muthuramakrishnan Venkitasubramaniam},
  year=2007
}