Non-Interactivity and Graph Non-Isomorphism

• Not all interactive protocols can be converted to non-interactive protocols
  • Schnorr’s Protocol
  • What prevents grinding?
  • Why can’t all interactive protocols be converted to non-interactive protocols (via Arthur-Merlin Game)?
• Graph Non-Isomorphism
  • Solution 1
  • Solution 2
  • Last Solution

This is a supplement to Zero Knowledge Proofs - Lecture 1.

Not all interactive protocols can be converted to non-interactive protocols

In the lecture, the professor claimed that not all interactive protocols can be converted to non-interactive protocols, and the reason given in the slide was that IP = AM sometimes requires a super-polynomial prover, and in the case of Fiat-Shamir transformation, the prover needs to be computationally bounded, and therefore cannot invert H.

However, why is this the case? Let’s use Schnorr’s Protocol as a case study to explain it.

Schnorr’s Protocol

Goal: Prover convinces Verifier that they know $x$ such that $h = g^x$ where $g$ is a generator of a group.

$$\newcommand{\work}[2]{#1 & & #2\\} \newcommand{\varprover}{\text{Prover}} \newcommand{\varverifier}{\text{Verifier}} \newcommand{\alicework}[1]{#1 & &\\[-5pt]} \newcommand{\samplezqs}[1]{#1\sampleSymb\zqs} \newcommand{\varr}{r} \newcommand{\sampleSymb}{ {\; \xleftarrow{\$} \;} } \newcommand{\zqs}{\mathbb{Z}_q^\ast} \newcommand{\varu}{u} \newcommand{\varg}{g} \newcommand{\alicebob}[3]{#1 & \ra{#2} & #3\\[-5pt]} \newcommand{\ra}[1]{\vphantom{}\smash{\xrightarrow{\hspace{1cm}#1\hspace{1cm}}}} \newcommand{\bobwork}[1]{ & & #1\\[-5pt]} \newcommand{\schnorrvalidate}{\mathsf{schnorr}\_\mathsf{validate}} \newcommand{\varh}{h} \newcommand{\bobseparator}{&&-------\\} \newcommand{\sample}[1]{#1\sampleSymb\zq} \newcommand{\varc}{c} \newcommand{\bobalice}[3]{#1 & \la{#2} & #3\\[-5pt]} \newcommand{\la}[1]{\vphantom{}\smash{\xleftarrow{\hspace{1cm}#1\hspace{1cm}}}} \newcommand{\varx}{x} \newcommand{\varz}{z} \newcommand{\equalQ}{\overset{?}{=}} \newcommand{\zq}{\mathbb{Z}_\varq} \newcommand{\varq}{q} \begin{array}{c} \work{\varprover}{\varverifier} \alicework{\samplezqs{\varr}}\\ \alicework{\varu = \varg^\varr} \alicebob{}{\varu}{} \bobwork{\sample{\varc}} \bobalice{}{\varc}{} \alicework{\varz = \varr + \varx\cdot \varc} \alicebob{}{\varz}{} \bobwork{\varg^{\varz} \equalQ \varu \cdot \varh^\varc } \end{array}$$

• Thanks ZKDocs - Schnorr’s identification protocol and Lecture 5: Proofs of Knowledge, Schnorr’s protocol, NIZK for providing the code and the graph.

The completeness of the above protocol is easy to see. For soundness, instead of proving statistical soundness, we can prove special soundness.

Just a sidenote, to convert this Schnorr’s Protocol to an non-interactive version, ZKDocs provides a case where incorrect input is used in Fiat-Shamir transformation, which causes the protocol to be insecure. It’s worth noting that the case they discussed is a bit different from what I have shown above. It’s about generating a valid triple ($X=g^x \pmod q$, $c = \text{Hash(input)}$, $z$) for any X of prover’s choice ¹, which means there is no fixed $X$ shared by both parties at the beginning. If you are interested, feel free to read the linked article and the paper.

What prevents grinding?

Now, let’s get back to the protocol that I described above. Suppose we want to turn it into an non-interactive version. The obvious thing we can do is to let $c = \text{Hash(u)}$ and then use it to generate $z = r + x * c$.

Now, you might be thinking: what prevents a malicious prover from grinding? In other words, since the variable $c$ is just a coin ², the malicious prover can just sampled 2 $r$ and it’s very likely that one of the $\text{Hash}(u) = \text{Hash}(g^r)$ it gets is $0$, which means it can then return $z = r$ directly. From the perspective of the verifier, this is a correct proof.

The answer to that problem is also very simple: c is not a coin, but a random value drawn from a field. If this is the case, the challenge space $C$ (the field where the “coin” c is chosen from) will be pretty large. As a result, the probability of finding the collision that I described above will be $\frac{1}{\|C\|}$ ³.

• If you treat $c$ as a $c$-bit number, then the probability will be $\frac{1}{\|2^c\|}$.

Why can’t all interactive protocols be converted to non-interactive protocols (via Arthur-Merlin Game)?

By the analysis above, we know that the probability of successfully grinding is $\frac{1}{2^c}$. If the prover is computationally bounded, this is fine. However, if it’s not the case, we are in trouble.

This is exactly why not all interactive protocols can be converted to non-interactive protocols as IP = AM transformation sometimes requires extra super-polynomial powers from Merlin (the prover).

Graph Non-Isomorphism

In the lecture, the professor shows an interactive proof of graph non-isomorphism. However, this proof is not ZK because a malicious verifier can use a completely new graph (not derived from either $G_0$ or $G_1$) and ask prover to show whether it is isomorphism to $G_0$ or $G_1$. Therefore, it can obtain extra information that cannot be simulated.

The way to solve this problem is briefly discussed: the verifier first prove to the prover that the graph it sends (let’s call it $G$) is indeed isomorphic to one of the $G_0$ and $G_1$ (can be both).

• But it is indeed very tricky to do so if you think about this carefully. How can you prove this without revealing which graph is isomorphic to $G$?

The remaining part of this article will analyze this amazing blog to see how we can prove this in a PZK (perfect zero knowledge) way.

Solution 1

Send the two graphs $\pi_0(G_0), \pi_1(G_1)$. The verifier then sends back an integer, pointing to one of these two graphs, and the prover responds by providing the permutation from $G$ to this graph. Note that if at least one of the graphs is isomorphic to $G$, the prover can do so with at least probability 1/2.

This does not work because a simulator $S$, given access to verifier $V$, cannot simulate this because

• It runs in PPT (probabilistic polynomial time), so it cannot using $\pi_0(G_0), \pi_1(G_1)$ (where $\pi_0, \pi_1$ are random permutations), generating a random number $r$, checking if it is able to find a permutation between $G_r$ and $G$.
• At the same time, it does not know which graph $G$ is isomorphic to, so it pre-prepare a permutation $\pi$ and generate messages like $\pi(G), \pi_1(G_1)$ and $\pi_0(G_0), \pi(G)$.

Solution 2

The prover sends back $\pi(G), \pi_0(G_0), \pi_1(G_1)$ in a random order. The verifier then randomly points to one of the three graphs, and asks the prover to show that this graph is isomorphic to $G$.

For the same reason, this method doesn’t work either. Given the length of the article, I’ll skip to the last solution.

Last Solution

The last solution is a very interesting construction.

1. Prover responds by sending two scrambled and permuted ordered copies of $G$, $G_0$, $G_1$ to the Verifier, with an additional restriction that second scrambling of the three graphs is either a right shift, or a left shift of the original three graphs.
   • In other words, it sends:
     • $$\pi(H), \pi_0(H_0), \pi_1(H_1)$$
     • $$\pi_0'(H_0), \pi_1'(H_1), \pi'(H)$$
   • or:
     • $$\pi(H), \pi_0(H_0), \pi_1(H_1)$$
     • $$\pi_1'(H_1), \pi'(H), \pi_0'(H_0)$$
   • where $H, H_0, H_1$ is some random permutation (ordering) of $G, G_0, G_1$
2. The Verifier now responds with either a 0, or a 1, one option to continue with the proof, and the other to verify that the two permuted copies indeed satisfy the requirements.
3. If the Verifier sent a 0, the Prover reveals the two permutations, and we go back to step 2. If the Verifier sent a 1, we continue to prove that at least one of the graphs is isomorphic to $G$, by choosing one of the columns, and showing that both of the graphs in that column are isomorphic to $G$ by sending back the permutations.

This solution works and achieve PZK because:

• H0, H1, H2 is a permutation of $G_0$, $G_1$, $G_2$ (they are $G_0$, $G_1$, $G_2$ in random order) -> this ensures that the correct column that the prover will pick can be any of the three columns.
  • Suppose no permutation is used, and only left and right shifts are used. Then, the probability of a column being selected is 1:1:0 (G isomorphic to $G_0$) or 1:0:1 (to $G_1$) or 1:1:1 (to $G_0$ and $G_1$) depending on which graph $G$ is isomorphic to.

    • Isomorphic to $G_0$

      $$\mathbf{G}, G_0, G_1$$ $$\mathbf{G_0}, G_1, G$$
      • or
      $$G, \mathbf{G_0}, G_1$$ $$G_1, \mathbf{G}, G_0$$

    • Isomorphic to $G_1$

      $$G, G_0, \mathbf{G_1}$$ $$G_0, G_1, \mathbf{G}$$
      • or
      $$\mathbf{G}, G_0, G_1$$ $$\mathbf{G_1}, G, G_0$$

    • So, without permutation, we can know some additional information based on which column is selected.

• Left Shift or Right Shift: it’s important to have them as well. This ensures that no matter the permutation, the distance between the $G$ and $G_0$/$G_1$ (the graph $G$ is isomorphic to) is always 1. If the distance is not always the same, after randomly selecting the column in the simulator, we cannot construct the other two columns randomly because we must fix the position of the graph that $G$ is isomorphic to match distance = 1.
  • For example, given this permutation $G_x$, $G$, $G_y$. Suppose $G_1$ is isomorphic to $G$. If we only allow left shift, we can only choose $G_y$ as the position for $G_1$.
    • But, in reality, the simulator doesn’t know which graph $G$ is isomorphic to.
    • So, after selecting the column randomly, it cannot proceed.