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 standard 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 P_{i} and send you the resulting sorted list of pairs.
After you have seen that list you choose a bit x_{i} and demand that I reveal one of two permutations

- if x
_{i}=1 - I must reveal P
_{i}which leads from X to the list I sent you, - if x
_{i}=0 -
I must reveal P
_{i}^{−1}P_{ω}which leads from Y to the list I sent you.

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.

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 P_{i}’s before learning the x_{i}’s.
Perhaps the x_{i}’s are from the secure hash of the lists produced by the P_{i}’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.