Is there a zero knowledge protocol for knottedness, similar to the GMW protocol for graph non-isomorphism?

Question

In the very easy-to-read [1], Kuperberg shows that, conditioned on the Generalized Riemann Hypothesis, knottedness is in $\mathsf{NP}$. As I understand the proof, given a knot-diagram of a knot $K$, the certificate is both a prime $p$ and a solution mod $p$ to a set of polynomial equations $S=0$ specifying a noncommutative representation of $\pi_1$ onto $SU(2)$ - that is, one $2\times 2$ matrix $M_i$ over $\mathbb{Z}/p$ for each generator $i$ of the knot group $\pi_1(S^3\setminus K)$ such that the generators don't all commute and satisfy the relations of the knot group.

Kuperberg's proof relies on the GRH only to show that the size (bit-complexity) of $p$ is polynomial in the number of generators of $\pi_1$. His proof is a combination of the algebraic topology results of [2] along with the number theory of [3]. He states in passing that because, modulo GRH, [3] puts problems involving showing the existence of solutions to systems of polynomial equations over $\mathbb{C}$ in the Arthur-Merlin complexity class, that also puts knottedness in $\mathsf{AM}$ as well.

Studying up on [1] and [3], I suspect that the $\mathsf{AM}$ protocol that Kuperberg has in mind entails finding a prime $p$ such that not only $S=0$ modulo $p$, but also, for some random hash $H$ onto a codomain of an appropriately large size, $H(p)=0$. This shows that there are a lot of primes $p$ such that $S=0$ mod $p$ (Kuperberg's $\mathsf{NP}$ certificate only needs one prime $p$.)

Such a protocol from [3] is based on the same universal hashing used in [4], which gives a public coin protocol for Graph Non Isomorphism based on hashing a random permutation of one of the two given adjacency matrices.

However, as addressed in a question from a sister site, it's not immediately clear how to convert the results of [3] into a interactive protocol, wherein, in order to convince the verifier, the prover is not allowed to see the random choices made by the verifier.

Is there a way for a (polynomially bounded) verifier to secretly flip a coin and present a (non-polynomially bounded) prover with one of two knot diagrams such that if only one of the diagrams represents the unknot whereas the other knot diagram is not the unknot, the prover can answer which coin was flipped correctly 100% of the time, but if both knot diagrams are of the unknot, the prover only has a 50% chance of answering correctly?

It is worth noting that [1] also mentions another withdrawn attempt at an interactive proof of knottedness. The withdrawn attempt also relied on keeping the verifier's choices hidden from the prover's; instead of presenting knot diagrams, the withdrawn attempt presented random triangulations of either a double of $S^3$ or of $S^3\setminus T(K_1)$ for some tubular neighborhood $T$ of the test knot $K_1$.

---

References

[1] Greg Kuperberg. Knottedness is in $\mathsf{NP}$, modulo GRH, 2011.

[2] Peter Kronheimer and Tomasz Mrowka. Dehn surgery, the Fundamental Group and $SU(2)$, 2004.

[3] Pascal Koiran. Hilbert’s Nullstellensatz is in the Polynomial Hierarchy, 1996

[4] Shafi Goldwasser and Michael Sipser. Private Coins versus Public Coins in Interactive Proof Systems, 1986.

Answer 1

I believe the answer is yes, such a zero-knowledge proof of knottedness to distinguish the unknot exists, by combining the results of [5], [6], and [7].

The standard Graph Non Isomorphism zero-knowledge protocol of [5] - that is, the GMW protocol - randomly permutes vertices of one of the given graphs.

Accordingly, a zero-knowledge proof of knottedness would be very similar, by randomly applying grid moves to grid diagrams, by walking along the Markov-chain of [6]. The recent results of [7] enable the verifier to stay polynomially bounded.

In more detail, given a grid diagram $G$ of dimension $\bar{D}$ of a given knot, [6] provides a way to generate a quantum state of all grid diagrams equivalent to the given knot, that can be reached from the given knot by increasing the dimension no more than a security parameter $\alpha=2\bar{D}$ in size. [6] achieves this by applying a finite Markov chain that acts on $G$.

Borrowing from [5] and [6], given a test knot $K$ as a grid diagram $G$ of grid dimension $\bar{D}$, a zero-knowledge protocol for a prover to show a verifier that $K$ is knotted may entail:

1. The verifier flipping a coin $i\in\{0,1\}$

2. The verifier flipping $n\in O(\mathrm{poly}\:\bar{D})$ more coins, and using the $n$ coins as random choices for Cromwell moves - cyclic permutations, transpositions, stabilizations, and destabilizations - of the test knot $K$ if $i=0$ to generate a new grid diagram $G_0$, or of the unknot if $i=1$, to generate a new grid diagram $G_1$, while keeping the grid dimension less than $\alpha$

3. The verifier presenting $G_i$ to the prover,

4. The prover deducing $i$

The Markov chain in [6] is doubly stochastic (the sum of the elements in each row and column is $1$), hence, the limiting distribution is uniformly distributed over all grid diagrams reachable from $G_i$ without increasing the dimension more than $\alpha$. Because the limiting distribution is uniform, if the test knot is really the unknot, then the prover won't know whether $i=0$ or $i=1$ because she will be shown two knots randomly drawn from all grid diagrams equivalent to the unknot; hence the protocol is sound.

The security choice $\alpha=2\bar{D}$ in [6] may be arbitrary; the authors of [6] actually generate a gaussian distribution, centered at $\bar{D}$, and $2\bar{D}$ is convenient. However, [7] shows that all unknots can be untied without increasing the crossing number $c$ to more than $(7c)^2$- hence, $\alpha$ may need to be closer to quadratic in $\bar{D}$.

[6] also left open whether the the mixing time of the Markov chain was really polynomial; indeed, the security of their quantum money depends on rapid mixing time of most knots of a given Alexander polynomial. Otherwise, the verifier may have to perform a superpolynomial amount of Cromwell moves of $G_i$ in step 2 above. However, [7] shows that, at least for the unknot, there is a sequence of $(236c)^{11}$ moves that converts the unknot to the trivial diagram. Hence at least the diameter $\Delta$ of the Markov graph is polynomial, because there's a polynomial bound on the number of Reidemeister (Cromwell) moves needed to unknot.

What's unknown is whether the results of [6] and [7] could be applied to show that two arbitrary knots are not equivalent. I suspect so... the security of [6] depends on it.

What's also unknown is how to convert the above to a public-coin protocol, similar to [4]. To answer this, we may need to know more about the statistics of random grid diagrams to know how large of a set to hash onto.

A lot of the above was implicit in the work of [8], which generalized the Markov-chain of [6] by defining "component mixers" applicable to any partition of a set.

---

[5] Olded Goldreich, Silvio Micali, and Avi Wigderson. Proofs that Yield Nothing But Their Validity or All Languages in NP Have Zero-Knowledge Proof Systems, 1985.

[6] Edward Farhi, David Gosset, Avinatan Hassidim, Andrew Lutomirski, and Peter Shor. Quantum Money from Knots, 2010.

[7] Marc Lackenby. A Polynomial Upper Bound on Reidemeister Moves, 2014.

[8] Andrew Lutomirski. Component Mixers and a Hardness Result for Counterfeiting Quantum Money, 2011.