Concurrent Zero-Knowledge

Cynthia Dwork

IBM Almaden Research Center

When zero-knowledge proofs are executed concurrently both parties can be at risk. The verifier faces malleability issues: the prover with which it is interacting may in fact be using some concurrently running second interaction as an ``oracle'' to help answer the verifier's queries, yielding an invalid ``proof'' (for example, in the case of a proof of knowledge). The prover faces the risk that concurrent executions of the protocol, with one or more verifiers, may leak information and may not be zero-knowledge in toto.

Malleability of interactive proofs was first addressed in 1991. In contrast, concurrency remained essentially unaddressed in the literature until this year, when it experienced an explosion of activity resulting in four papers. This talk explains the difficulties in achieving concurrent zero-knowledge, and describes the state of the art.

Cynthia Dwork, Concurrent Zero-Knowledge

Gates 498, 12/7/1998, 4:15 PM