The graph-nonisomorphism interactive protocol

For two graphs $G_0,G_1$ on the same labelled vertex set $\{1,\dots ,n\}$, the verifier chooses $b$ uniformly from $\{0,1\}$. It independently samples a permutation $\pi$ by the following bounded procedure. Put $k=\lceil {\log }_2(n!)\rceil$ (with $k=0$ when $n!=1$). Up to four times, draw exactly $k$ fresh fair bits as an integer $t\in [0,2^k)$; on the first draw with $t<n!$, unrank $t$ in the factorial number system to obtain $\pi$. If all four draws fail, use the identity permutation. It sends $H=\pi (G_b)$, receives a bit $b^{\mathrm{\prime }}$ from the prover, and accepts iff $b^{\mathrm{\prime }}=b$. Factoradic unranking, the factorial arithmetic, the four draws, and graph relabeling take polynomial time and use at most $4k+1$ random bits.

Each draw succeeds with probability $n!\mathrm{/}{2}^k>1\mathrm{/}2$ (or $1$ when $k=0$). Conditional on at least one success, $\pi$ is exactly uniform on the $n!$ permutations; the fallback has probability $\epsilon <1\mathrm{/}16$ (zero when $n!$ is a power of two). This is a one-round instance of Interactive-proof transcripts, rounds, and prover strategies.