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

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?

4 Answers
4

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.

At the very core of Zero Knowledge proof systems, lies the fact that proofs are published by asking the party to prove the correctness of its knowledge, via any one of many methods to verify a solution.

Since knowing the question in advance allows a party to forge another proof, the only way to get a reliable proof is via asking a random question out of a pre-determined set of questions, multiple times enough so that the chances of a cheat to pass through are practically impossible.

The probabilistic behaviour becomes inevitable from the fact that any question asked at random can be predicted with a non-zero probability, since it comes from a pre-determined set of questions. If the question to be asked was not from a set of pre-determined questions, current Zero Knowledge proofs would be deterministic.

Here's a deterministic zero-knowledge proof of sorts, if there are any logic gaps please let me know!:
This zero knowledge proof involves proving you have a solution to three-colouring a map.
The common zero knowledge proof for this scenario (Hats & Crayons for example)involves the Prover tries to convince the Verifier that you have found a solution by only showing pairs of countries chosen by the Verifier, then repeatedly recolouring the entire map to allow the Verifier to check another pair. After a huge number of checks, the Verifier is satisfied that it is highly unlikely that the Prover does not really have a genuine solution, and considers the proof good enough to have confidence in it.

However, here is a set up for an deterministic zero knowledge proof:
You set out the huge blank uncoloured map on, say, a warehouse floor.

The Prover presents the Verifier with a set of cards and explains that each card has the label of a particular country of the map on one side and the other side is blue, red, or yellow. There are also three extra cards which are blank on the label side and have one of each colour on the flip side. The Verifier can examine the label side of the labelled cards to ensure there are no duplicates or country omissions, but is not allowed to check that all the cards have one of the three colours on the back (if the Verifier was allowed to do this, he would get some information about the overall proportion of the three colours: unlikely to be useful information, but knowledge all the same, zero knowledge is a requirement).

The Prover then places the cards on the corresponding countries label-side up and allows the Verifier to check that each card is placed on its correct country. The Prover also allows the Verifier to check the three extra cards have no labels, and contain the set of extra colours on their flip side.

The Prover then allows the Verifier to choose either 2 countries sharing a border (or 3 countries which each share a border with the other two).

Once chosen, the Prover takes the chosen 2 cards, adds one of the extra cards (if the Verifier has only chosen 2 countries, if not this step is skipped) taking care to add the extra card with the one colour not already present on the colour-side of the Verifier's chosen cards (he does not, of course, show the banker which colour he has added to the chosen 2). The Prover then thoroughly shuffles these three cards (which, remember are either two chosen by the Verifier plus an extra chosen by the Prover, or three chosen by the Verifier) and presents them to the Verifier colour-side up. The Verifier will always see three cards showing one of each of the colours. This proves to the Verifier that the 2 or 3 countries he picked do indeed have different colours (and these colours are from the allowed set of three colours).

Once checked, the Prover then shuffles the three cards again and places the labelled cards back on their countries (again, label side up). The Verifier is therefore satisfied that the Prover has reset the map as it was before.

This process repeats, enabling the Verifier to check that every single pair of connected countries have different coloured cards. With each verification cycle the Verifier will always only ever see three cards with the three allowed different colours, gaining no knowledge of what particular colour is on any particular country.

Not only is the Verifier able to check (very quickly) that there are no flaws in the solution, they also can see that the cards are not being changed with each verification cycle, so no room for the Prover to just be getting lucky each time.

As soon all the pairs (or trios) are checked once (the Verifier is allowed to check each pair more than once, does not need to), the Verifier is absolutely sure the solution is correct. But with each cycle, the Verifier has only ever seen the exact same answer: three different coloured cards (always showing the three chosen colours).

The Verifier has checked with absolute certainty that the solution is not flawed, but he has gained absolutely no useable knowledge about which colours go where, as he has only ever seen sets of the three chosen colours over and over again.

And to illustrate that the Verifier truly has zero knowledge after full verification of a true solution, if the Prover were to somehow be able to cheat by substituting colour cards during verification cycles, he would still only ever show the same three colours with each cycle.

The absence of re-setting the map takes away the possibility of the Prover just being lucky, while the addition of the blank extra cards does not allow the Verifier to gain any useful information, hence a non-probabilistic zero-knowledge proof.

In reality, there is no point in this distinction, because, even a conventional proof is probabilistic since there will always be a small probability that a cheating prover found the right solution by chance.

If fact, the only difference, is that in conventional methods, the prover must prove he finds the right solution once, with a very small probability of success, while in zero knowledge, the probability of success is much larger, but you need to repeat the process a large number of times, in order to get the same level of security as in conventional proofs.

Thanks for contributing an answer to Computer Science Stack Exchange!

But avoid …

Use MathJax to format equations. MathJax reference.

To learn more, see our tips on writing great answers.

Required, but never shown

Required, but never shown

By clicking "Post Your Answer", you agree to our terms of service, privacy policy and cookie policy