## 5 Zero-Knowledge Protocol  
Our next goal is to employ the theory developed in Section 4 to established the announced ZKP.  
Let us start by generating a graph \(G\) and a random isomorphism \(\phi\), which can be obtained as a random bijection of its vertex set. In this way, we create a second graph \(H\) which is isomorphic to \(G\) with isomorphism \(\phi\). Now, let \(F_{0}\) be the polynomial system resulting from the process of construction shown in Section 4. A solution \(\mathbf{x_{0}}\) for the system \(F_{0}\) is found by setting \(X_{i,k}=1\) if \(u_{i}v_{k}\in M\), and \(X_{i,k}=0\) otherwise. The polynomial set \(F_{0}\) will be public and is used as the public key. The private key will be the pair \((F_{0},\mathbf{x_{1}})\).  
The interaction process starts by generating a second isomorphic graph \(K\), which can be performed by applying a random bijection \(\psi\) on the vertex set of \(H\). Knowing the graph \(H\) and the applied permutation allows one to obtain a second polynomial set \(F_{1}\) and a its corresponding solution \(\mathbf{x_{1}}\). The following diagram (Figure 3) allows visualization of the operation performed.  
Though the pair \((F_{1},\mathbf{x_{1}})\) can be obtained in the same fashion as the pair \((F_{0},\mathbf{x_{0}})\), i.e., by computing the polynomial set related to the corresponding graph isomorphism, a more direct approach consists of directly applying suitable permutations to the subindices \(k\) and \(l\) for the variables obtained from the edges of \(H\) and \(\overline{H}\). In fact, let us define the permutation \(\sigma_{\phi}\) by \(\sigma_{\phi}(i)=k\) if \(\phi(u_{i})=v_{l}\). Then, the edge \(u_{i}u_{j}\in D\) transforms into edge  
\[\phi(u_{i})\phi(u_{j})=v_{\sigma_{\phi}(i)}v_{\sigma_{\phi}(j)}.\]  
Figure 3: Graph composition and resulting systems.  
A similar permutation \(\sigma_{\psi}\), dependent on the action \(\psi\), is obtained by relating edges of graph \(H\) and edges of graph \(K\). The set of polynomials fulfilling condition (3) leads to a direct definition of the set of polynomials corresponding to \(H\) and \(K\) obtained from the public polynomial set as  
\[X_{\sigma_{\psi}(i),\sigma_{\psi}(k)}X_{\sigma_{\psi}(j),\sigma_{\psi}(l)}. \tag{4}\]  
A solution for the system \(F_{1}\) is provided by applying permutations \(\sigma_{\psi},\sigma_{\psi}\) to reorder the entries of the vector \(\mathbf{x_{1}}\) in a similar fashion.  
Observe that applying the permutation \(\sigma_{\psi}\) to the subindices of \(X_{i,k}\) is equivalent to applying an affine transformation \(T\), which might be represented by a matrix with one and only one element with value \(1\) on each column and each row (a permutation matrix) defined by  
\[T(i,j)=\left\{\begin{array}{ll}1&\text{if }j=\sigma_{\psi}(i)\\ 0&\text{otherwise.}\end{array}\right.\]  
A similar transformation \(S\) is related to \(\phi\); this time, it is applied on the right side.  
\[S(i,j)=\left\{\begin{array}{ll}1&\text{If }j=\sigma_{\phi}(i)\\ 0&\text{Otherwise.}\end{array}\right.\]  
Indeed, \(S,T\) can be used to compute the new polynomial (see \(\Psi(F_{1})=S\circ F_{0}\circ T\)) and the new solution to such a system by \(\mathbf{x_{1}}=\Psi(\mathbf{x_{0}})=S\cdot\mathbf{x_{0}}\cdot T\), which consists of matrix multiplications.  
Finally, if instead of using the isomorphism \(\psi:H\to K\) to obtain the second polynomial system, the composition \(\gamma=\psi\circ\phi\) is used, we get a third system, constructed by computing the new set \(X_{i,\sigma_{\gamma}(k)}X_{j,\sigma_{\gamma}(l)}\), which requires a single permutation, and in matrix notation, only the inner affine transformation \(T\). Since both systems rely on the difficulty of computing a graph isomorphism, theoretically, any one of them could be used without losing security in the defined protocol.