1
$\begingroup$

Given two graphs $G_1$ and $G_2$, a zero-knowledge interactive protocol for a prover to convince a verifier that $G_1\not\cong G_2$ entails:

  1. The verifier choosing a random $i\in\{1,2\}$
  2. The verifier choosing a random permutation $\pi$
  3. The verifier sending a graph $G_3=\pi(G_i)$ to the prover
  4. The prover sending $j\in\{1,2\}$ to the verifier
  5. The verifier accepting if $i=j$

A public coin Arthur-Merlin protocol for Merlin to prove to Arthur that $G_1\not\cong G_2$ is more involved, and includes Arthur publicly tossing coins to determine a hash function $h$ and a random $y$, and Merlin finding a preimage $x$ of $h$, such that $h(x)=y$. The proof relies on the fact that the number of permutations of a given $d$-vertex graph is known, and hence two non-isomorphic graphs will "generate" a larger set, after a random permutation, than two isomorphic graphs. Accordingly it is easier to find a preimage $x$ of $h$ if the codomain of $h$ is large.

My questions are: can the same ideas be extended to show that two knots $K_1$ and $K_2$ cannot be converted to each other in fewer than $n$ Reidemeister moves, for either protocol?

For example, would the following work as a private coin protocol to show that one knot $K_1$ cannot be easily "untied" to another knot $K_2$ in fewer than $n$ moves?

  1. The verifier chooses a random $i\in\{1,2\}$
  2. The verifier chooses up to $n$ random sequence of Redeimester moves
  3. The verifier sends to the prover a knot diagram $K_3$ which is the knot diagram corresponding to $K_i$ after the random Redeimeister moves have been applied
  4. The prover responds with $j\in\{1,2\}$
  5. The verifier accepts if $i=j$

Similarly, for the public-coin protocol, do we know enough about applying random Reidemeister moves to a knot diagram to know how "big" a set of knot diagrams would be, after $n$ random Reidemeister moves? That would let us know the parameters for the public coin protocol, e.g. the codomain of the hash...


EDIT

Considering @D.W.'s comments, I think it's possible for a protocol to be sound if we were to make the verifier bound to $c_{max}$ the maximum crossing number of the knot diagram presented to the prover in step 3, and if the random moves in step 2 above were doubly-stochastic, meaning that a Markov-chain on the walk of random knot moves has a uniform limiting distribution $\pi$ over all knot diagrams equivalent to $K_i$ for the chosen $i$.

If both $K_1$ and $K_2$ are of the same knot type, as long as $n$ - the number of Reidemeister moves done in step 2 - was large enough so the chain was properly mixed, a prover would not know which $i$ was chosen, because the knot diagram presented to her is randomly chosen from all knot diagrams of crossing number $\le c_{max}$ that are equivalent to $i$.

$\endgroup$
  • 1
    $\begingroup$ I doubt that your protocol works. Let $f$ be a random variable representing the operation of the chosen sequences of Redeimester moves. Are we guaranteed that if $K_1$ is isomorphic to $K_2$, then $f(K_1)$ has the same distribution as $f(K_2)$? That seems like a necessary (but not sufficient) condition. $\endgroup$ – D.W. Aug 6 '17 at 4:51
  • $\begingroup$ @D.W., thanks. I think you are saying that, for GNI of two $d$-vertex graphs, $f$ is an element of $S_d$ chosen uniformly at random. $f$ is independent of $G_1$ or $G_2$. But for knots, $f$ would be an $n$-step random walk along the space of Reidemeister moves starting at one of $K_1$ or $K_2$. The size of the space for $K_1$ may be significantly different than of $K_2$. (Even the private-coin case seems to require the spaces to be roughly the same size, otherwise the prover may be able to choose $j$ judiciously?) $\endgroup$ – Mark S Aug 6 '17 at 14:24
  • $\begingroup$ A necessary condition is that if $K_1$ is equivalent to $K_2$, then the prover has only a $1/2$ chance of giving the correct response. Try proving that this condition holds. (Hint: I think you'll find it hard, as it will lead you to the question mentioned in my first comment. I suspect the answer to that question is "no".) $\endgroup$ – D.W. Aug 6 '17 at 15:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.