Concurrent zero-knowledge: Reducing the need for timing constraints

Abstract

. An interactive proof system (or argument) (P; V ) is concurrent zero-knowledge if whenever the prover engages in polynomially many concurrent executions of (P; V ), with (possibly distinct) colluding polynomial time bounded veriers V1 ; : : : ; V poly(n) , the entire undertaking is zero-knowledge. Dwork, Naor, and Sahai recently showed the existence of a large class of concurrent zero-knowledge arguments, including arguments for all of NP, under a reasonable assumption on the behavior of clocks of nonfaulty processors. In this paper, we continue the study of concurrent zero-knowledge arguments. After observing that, without recourse to timing, the existence of a trusted center considerably simpli- es the design and proof of many concurrent zero-knowledge arguments (again including arguments for all of NP), we design a preprocessing protocol, making use of timing, to simulate the trusted center for the purposes of achieving concurrent zero-knowledge. Once a particular p...