I adopt the following presentation style here: I illustrate a solution to an unstated problem. The nature of the problem may then be evident. Several introductions on the web try to present the problem first which sounds hopelessly vague or complex I think. A concrete solution may help some. It helped me.

Here is a different concrete example of a ZKP (Zero Knowledge Proof) presented in this style which you may find easier if you know a little number theory.

Dieter Gollmann told me of the following scheme.

Suppose that I want to be able to prove to you that I know the solution to some difficult puzzle without revealing the solution. The puzzle definer chooses and publishes the puzzle, and tells me the solution. (Perhaps people who know the solution get to pass thru a gate.)

The definer starts with some symmetric relation (graph) on 100 elements numbered from 0 to 99. Each element is related to 4 other elements. The standard way of representing the relation is a sorted list of 200 unordered pairs of element numbers. Each pair lists the smaller element number first. Each element appears just 4 times in the list. The definer then renumbers the elements with a random secret permutation Pω. He publishes the two lists, X and Y, of 200 pairs each, one before the renumbering and the resorted one after. The definer tells me the secret Pω.

You do not know the permutation but the protocol convinces you that I know a permutation, Pω, that produces the second list from the first.

This is the transaction: I choose yet another permutation Pi and send you the resulting sorted list of pairs. After you have seen that list you choose a bit xi and demand that I reveal one of two permutations

if xi=1
I must reveal Pi which leads from X to the list I sent you,
if xi=0
I must reveal Pi−1Pω which leads from Y to the list I sent you.
I can easily comply with either demand with my knowledge of Pω. You can easily verify the result. If I were required to comply with both demands, you could readily compute the secret Pω = Pi(Pi−1Pω).

If I didn’t know Pω I would only a 1/2 chance of satisfying your demand. To convince you we must perform the transaction n times until you are convinced that 2−n is too small for mere luck.

Ramifications

To deploy this scheme you must be aware of known algorithms to find isomorphisms. For instance distinctive features such as cycles just 5 elements long can help to identify elements to be related in seeking the secret permutation. The standard relations can be carefully chosen to avoid these attacks but only with knowledge of the attacks. This is like RSA depending on absence of factoring algorithms. In crypto the best you can hope for, is to take absence of evidence of an algorithm to be evidence of absence. (Except, perhaps, for onetime pad).

There is a version of a MITM attack to be avoided where the challengee has recourse to someone who does know the secret and is motivated to prove it to the MITM and may not know the nefarious role of the MITM. There are several ways to guard against this problem, none of them entirely trivial.

There are offline versions of these protocols where the challenger’s role is automated by a public algorithm that the challengee knows but where the challengee must produce the Pi’s before learning the xi’s. Perhaps the xi’s are from the secure hash of the lists produced by the Pi’s, i.e. the isomorphism. This results in a document that proves that someone knows the permutation and is thus non constructive evidence of isomorphism.