Suppose that Peggy claims to know an isomorphism between graphs G and H. In practice this means that she has constructed the graphs herself (for large graphs), or at least was provided the isomorphism by someone who did. Knowing this isomorphism might be Peggy's way of proving her identity if it has been published previously that she is the person who knows the isomorphism of G and H. Obviously, just showing the isomorphism directly allows any observer to pretend he is Peggy, so that is no good.

Here is what Peggy does to prove she knows the isomorphism:

1. Peggy randomly permutes G to produce another isomorphic graph I. Since Peggy knows the isomorphism between G and H, it is easy for her to simultaneously find the isomorphism between H and I.
2. Peggy gives I to Victor.
3. Victor may ask Peggy to prove either (a) that I and G are isomorphic, or (b) that I and H are isomorphic. But Victor may not ask for both proofs (were he to obtain both, he would have the isomorphism proof of G and H himself).
4. Peggy provides the proof requested by Victor.