Cryptology ePrint Archive: Report 2007/451
Precise Concurrent Zero Knowledge
Omkant Pandey and Rafael Pass and Amit Sahai and 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.
Category / Keywords: foundations / Concurrent Zero Knowledge, Precise Simulation
Publication Info: Full version of a paper appearing at Eurocrypt 2008.
Date: received 4 Dec 2007, last revised 1 Feb 2008
Contact author: omkant at cs ucla edu
Available format(s): PDF | BibTeX Citation
Version: 20080201:100328 (All versions of this report)
Short URL: ia.cr/2007/451
[ Cryptology ePrint archive ]