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
-
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},
url = {https://eprint.iacr.org/2007/451}
}
