Reference Request: soundness in a ZKP achieved by walking along a doubly-stochastic Markov chain?

Question

Consider the following variant of a zero-knowledge proof that two graphs, $G_1$ and $G_2$, given by adjacency matrices $M_1$ and $M_2$, respectively, are not isomorphic.

Here Peggy the prover wants to show Vicky the verifier that $G_1 \not\cong G_2$, where both $G_1$ and $G_2$ have $n$ vertices.

1. Peggy and Vicky agree on a small number, say $r$, of generators $\pi_1,\pi_2,\cdots,\pi_r$ of the symmetric group $S_n$ on the $n$ vertices

2. Vicky (secretly) tosses a fair coin $i\in \{0,1\}$ to determine to which graph $G_i$ she will permute the vertices

3. Vicky (secretly) chooses $t$ random numbers $g_1,g_2,\cdots,g_t\in[r]$, and applies the (concatenated) permutation $\pi_{g_1}\pi_{g_2}\dots\pi_{g_t}$ to the vertices $M_i$, to generate a new matrix, $M_3$

4. Vicky presents $M_3$ to Peggy

5. Peggy must deduce $i$ from $M_3$, that is, she must deduce which of the graphs $G_1$, $G_2$ Vicky chose in step 1

A difference between a standard graph non-isomorphism protocol and the present protocol is in step 3. That is, conventionally in step 3, Vicky just randomly chooses any old element $\pi\in S_n$ to apply to the graph $G_i$, but in the above protocol in step 3, Vicky walks along the Cayley graph of $S_n$ with generators $\langle\pi_1,\pi_2,\cdots,\pi_r\rangle$ a total of $t$ times.

Notice that because each step of the Markov chain is, by definition, an invertible permutation of the configuration space (the configuration space being the set of all adjacency matrices equivalent to $M_i$), such a walk is a doubly-stochastic Markov chain, meaning each column (resp. row) of the transition matrix sums to $1$. Thus, after the selected adjacency matrix $M_i$ is properly mixed, the matrix that Vicky will present to Peggy is uniformly distributed over all matrices isomorphic to $G_i$. Accordingly, if $G_1\cong G_2$, then Peggy would not have better than even chance of deducing $i$, because she will just be given two random matrices isomorphic to $G_i$; hence, the protocol is sound.

A key concern is that we need to make sure that the matrices are properly mixed, that is, that the number of steps $t$ along the Cayley graph is large enough to mix the given graphs to the limiting distribution. I believe, although I can't prove it for now, that for most generating sets $\{\pi_1,\pi_2,\cdots,\pi_r\}$ of the symmetric group $S_n$, $t$ is probably $O(\log n)$.

But, now to generalize, given any two elements chosen from any discrete configuration space, not just adjacency matrices representing graphs, I think we have a sound zero-knowledge protocol to show that the two elements are not in the same equivalence class, as long as we can construct a fast-mixing doubly-stochastic Markov chain to walk through the configuration space.

Has such an approach to zero-knowledge proofs using doubly-stochastic Markov chains been studied before?

As one example, we may apply such a protocol to some problems in discrete robot motion non-equivalence, rather than adjacency matrices of graphs. That is, we can have a sound zero-knowledge protocol that a discrete robot in a particular position cannot be converted to another position, using a fixed set of invertible generators. Rather than deciding only one element of the symmetric group $S_n$, Vicky must choose a particular path along a Markov chain, where each state is an element of the configuration space and each transition is given by one of the generators of the robot. After mixing, the test element of the configuration space will be chosen uniformly from all elements of the configuration space in the same equivalence class as the given robot configuration.

Answer 1

This seems to be explicit or at least implicit in Lutomirski's 2011 "Component mixers and a hardness result for counterfeiting quantum money" - arXiv

Lutomirski formally defines component mixers as a family $\{M_i\}$ of one-to-one maps between elements of a set $S$ partitioned into $\{S_1,S_2,\cdots,S_c\}$.

He gives a number of example $S$'s, such as the set of all graphs on $n$ vertices, where each partition $S_1,S_2,\cdots,S_c$ corresponds to different isomorphism classes of graphs. Each element $g\in S$ is a given graph on $n$ vertices, and is a member of only one partition $S_g$. "Mixing" means to randomly draw another element $g'$ from the same $S_g$.

He notes that for many sets $S$ one can mix easily enough, with permutations or straight-line-programs. Otherwise, he comments that:

"In general, given a Markov chain over $S$ that does not mix between components but mixes rapidly over each component, each step of which consists of choosing uniform random sample from a set of invertible rules and applying that rule, then iterating that Markov chain to amplify its spectral gap will give a component mixer."

Lutomirski goes on to provide a $\mathsf{coAM}$ protocol for determining whether the number of components (partitions) is greater than $1$.