$\mathsf{GNI}$ Private Coin

In [GMW85], the authors provided the famous interactive proof $\mathsf{IP}$ of Graph Non Isomorphism $\mathsf{GNI}$.

The $\mathsf{GNI}$ protocol entails a verifier Vicky picking a random permutation $\pi$ to permute the edges of one of the two given graphs $G_i$, with $i\in\{0,1\}$, to generate a new graph $\pi(G_i)$, and providing the prover Peggy with, say, an adjacency matrix of $\pi(G_i)$.

Peggy must answer whether $i=0$ or $i=1$. The success of the protocol depended on Vicky keeping $(i, \pi)$ secret from Peggy.

$\mathsf{GNI}$ Public Coin

As is known, in [GS86], the authors showed that, with more work on the prover's part, Merlin can show to Arthur that two graphs are not isomorphic, where Arthur publicly shows all of his coinflips to Arthur.

As I understand it, it came as a bit of a surprise that the private coin protocol $\mathsf{IP}$ is just as powerful as a two-round public coin protocol $\mathsf{AM[2]}$.

I envision the [GS86] protocol as Arthur providing to Merlin some $y$, $H$, and Merlin running through both graphs $G_i$, and through all of the permutations $\pi$ of both graphs, until he finds a permutation of one of the graphs such that the hash of the adjacency matrix is $y$, because there are likely to be more permutations of non isomorphic graphs, and hence there is likely to be a greater chance of finding a preimage.

That is, Merlin looks for a $\pi$ and an $i$ such that $y=H(\pi(G_i))$.

$\mathsf{HN}$ Public Coin

In [Koi96], Koiran provided, assuming the Generalized Riemann Hypothesis, a public coin protocol for Hilbert's Nullstellensatz $\mathsf{HN}$, that shows a system of polynomial equations $S$ is solvable over $\mathbb{C}$. That is, Merlin can show to Arthur that a solution to:

$$f_1[x_1, x_2, \cdots, x_n]=f_2[x_1, x_2, \cdots, x_n]=\cdots=f_m[x_1,x_2,\cdots,x_n]=0$$ exists over $\mathbb{C}^n$.

In the [Koi96] approach, assuming the GRH, there are "many" primes $p$ such that there is a solution to $S$ mod $p$ iff there is a solution to $S$ in $\mathbb{C}^n$. Of course, "many" can be very small, but it is still much larger than the number of primes if $S$ is not solvable in $\mathbb{C}^n$.

The [Koi96] protocol entails Merlin finding a prime $p$ and a solution witness $w=(a_1, a_2, \cdots, a_n)$ such that $S$ is solvable modulo $p$, and further that $H(p)=y$ for some randomly chosen hash $H$ and image $y$.

By appropriately choosing the size of the codomain of $H$ to be small enough to guarantee a high likelihood of a collision when there are many primes $p$, Merlin can find both a prime $p$ and the witness $w$ such that both $w$ is a solution mod $p$ and $H(p)=y$.

Towards an $\mathsf{HN}$ Private Coin

There seems to be a difference between the public coin $\mathsf{GNI}$ protocol and the public coin $\mathsf{HN}$ protocol.

In the $\mathsf{AM}$ protocol for $\mathsf{GNI}$, Merlin can do all of the work that Vicky would have done in the $\mathsf{IP}$ protocol. That is, Merlin just walks through all of the permutations that a private-coin verifier Vicky could have randomly chosen.

For example, in $\mathsf{GNI}$, Vicky can randomly and Merlin can exhaustively easily permute one of the two graphs $G_1$ or $G_2$.

But in [Koi96], it's not clear what a private coin verifier would have been doing in the first place.

Is there a similarly obvious way for Merlin to generate a solution to the system of polynomial equations $S$ modulo some prime $p$, and then leverage that solution to generate many other solutions $S$ modulo other primes $p'$ until he finds a winning solution where $y=H(p')$?


I believe, by analogy to Group Non Membership $\mathsf{GNM}$,a private-coin Hilbert's Nullstellensatz $\mathsf{HN}$ protocol might be a version of Ideal Non Membership $\mathsf{INM}$.

For example, given a finite (matrix) group $G$ of order $|G|$ generated by generators $\langle g_1,g_2,\cdots,g_m\rangle$, Vicky the verifier may ask Peggy the prover to show that the test element $q$ is not in $G$ by flipping a coin $i\in\{1,2\}$ and generating a random word $g^*$ of length $O(\text{log}|G|)$ from either

$$G=G_1=\langle g_1,g_2,\cdots,g_m\rangle$$


$$G_2=\langle g_1,g_2,\cdots,g_m,q\rangle$$

If $q\in G$, then the groups $G_i$ are isomorphic, and $G_1\cup G_2$ is of size $|G|$. However, if $q\notin G$, then $G_1$ and $G_2$ are not isomorphic, and $G_1\cup G_2$ will be at least twice as big. I think the public coin/ approximate counting protocol for $\mathsf{GNM}$ follows similarly to [GS86] follows.

For a public-coin version of $\mathsf{HN}$, a way to reprhase the (weak) Nullstellensatz is to state that the polynomial $1$ is not in the ideal generated by $\langle f_1,f_2,\cdots,f_m \rangle$. Here Vicky the verifier randomly generates a polynomial $f^*$ of degree $O(\text{poly }mn)$ from either $$\langle f_1,f_2,\cdots,f_m\rangle$$

or $$\langle f_1,f_2,\cdots,f_m,1\rangle=\langle 1\rangle$$

Peggy the prover's job is to identify whether $f^*$ was generated from $\langle f_1,f_2,\cdots,f_m\rangle$ or $\langle f_1,f_2,\cdots,f_m,1\rangle$.

Of course, all polynomials are generated by $\langle 1 \rangle$, just as all statements follow from a contradiction. But perhaps, assuming GRH, the "size" of $\langle f_1,f_2,\cdots,f_m\rangle\cup\langle f_1,f_2,\cdots,f_m,1\rangle$ is bigger than the "size" of$\langle f_1,f_2,\cdots,f_m,1\rangle$ by itself, after "randomly" generating the polynomial $f^*$ with only $\text{poly }mn$ coin flips. In other words, GRH may place bounds on how fast the ideal $\langle 1\rangle$ generates members. This may enable Peggy/Merlin the win...



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.