## 2 Related Work  
Interactive proof systems were presented by [PERSON], [PERSON], and [PERSON] [8] as a novel technique to demonstrate \"knowledge\" efficiently, in the sense that the verification of such knowledge should be performed easily. This method involves an exchange of information between two entities: the _prover_, which is determined to demonstrate the truthiness of a proposition to a second party, and the _verifier_,which in turn must be convinced of the assertion. The parties involved interact in a challenge-response process until the verifier is ready to decide that the prover's assertion is correct, or concludes that the claim is false. Interactive proof systems are said to be _zero-knowledge_ if the verifier is not able to get any extra information from the interaction process, except the correctness of the statement. This kind of proof can be used by entities requiring authentication and identification services: access control or credit card validations, among many others. One of the most typical examples of ZKP systems bases its security in the difficulty of solving the graph isomorphism problem (GI) [9]. The main components of this system are:  
* The public key: two isomorphic graphs \(G\) and \(H\). * The private key: the pair \((G,H)\) together with an isomorphism \(\phi:G\to H\). * The interaction algorithm between [PERSON] (the prover) and [PERSON] (the verifier): 1. [PERSON] starts the interaction by providing a random isomorphic graph \(K\). 2. [PERSON] selects a random bit \(b\in_{R}\{0,1\}\) and sends it to [PERSON]. 3. Considering \(\psi_{0}=\psi\circ\phi,\psi_{1}=\psi\) [PERSON] must send \(\psi_{b}\) accordingly. 4. [PERSON] verifies that \(\psi_{0}(G)=K\) or \(\psi_{1}(H)=K\) depending on the choice of \(b\). The interaction procedure is based on the commutativity of the diagram shown in Figure 1 and the difficulty of constructing \(\psi\circ\phi\) from \(\psi\) alone. The GI problem can be easily solved for the average case with state-of-the-art solvers, such as nauty, Traces [10], saucy [11], and bliss [12], among others. In addition to these results, [PERSON] [7] has proposed a novel technique reducing the complexity of GI to quasi-polynomial time (with a running time of \(2^{O((\log n)^{c})}\)). Nevertheless, efforts to construct difficult instances have been made. Contrary to  
Figure 1: Composition of graphs. what is expected, these cases might not provide suitable cases for cryptographic purposes but lower complexity bounds by solving particular cases with tuned algorithms. [PERSON] [13] generalizes the aforementioned construction by studying other mathematical objects possessing the commutativity property shown in Figure 1. This allows considering transformations with similar behaviour, such as homomorphisms and endomorphisms in group and ring theory. The required characteristics to obtain a resistant protocol are:  
* that transformations \(\phi\) and \(\psi\) are difficult to invert. * The possibility of obtaining \(\psi\circ\phi\) easily from \(\phi\) and \(\psi\). The ZKP system based on GI is compliant with these restrictions, but further problems are introduced with similar characteristics, mainly related to graph theory, such as the subgraph problem or the colorability problem, and problems concerning group and ring endomorphisms, among others. Some of these problems are known to be NP-hard, which provides an advantage over the GI problem, whose membership to the NP-complete group is currently unknown, but expected to be false. Later, [PERSON] [14] introduced the Isomorphism of Polynomials Problem (IP), which relates affine spaces by means of affine transformations. Given two sets of polynomials of the same size, we say that both sets are isomorphic if there are affine transformations that define a bijection from one set into the other.