HiveBrain v1.2.0
Get Started
← Back to all entries
patternMinor

Are there deterministic and/or non-interactive zero-knowledge proofs?

Submitted by: @import:stackexchange-cs··
0
Viewed 0 times
knowledgeinteractivenonaredeterministicandtherezeroproofs

Problem

The Wikipedia page on zero-knowledge proof says


Zero-knowledge proofs are not proofs in the mathematical sense of the term because there is some small probability, the soundness error, that a cheating prover will be able to convince the verifier of a false statement. In other words, zero-knowledge proofs are probabilistic "proofs" rather than deterministic proofs. However, there are techniques to decrease the soundness error to negligibly small values.

Is it possible to prove that no zero-knowledge proof can be deterministic? What about non-interactive?

Solution

Goldreich and Oren, in their paper Definitions and properties of zero-knowledge proof systems, show that if the verifier is deterministic then interactive proofs trivialize to RP, whereas if the prover is deterministic then interactive proofs trivialize to BPP. See Section 4 of their paper.

Blum, de Santis, Micali and Persiano constructed noninteractive zero-knowledge proofs in their classic work Noninteractive zero-knowledge. The two parties do have to agree on a random key beforehand. Noninteractive zero-knowledge proofs have found many applications, for example to cryptocurrencies. See Wikipedia for many references.

Context

StackExchange Computer Science Q#97367, answer score: 3

Revisions (0)

No revisions yet.