# Authentication Based on Non-Interactive Zero-Knowledge Proofs for the Internet of Things
## 3 Preliminaries  
If a prover P is trying to prove to a verifier V its knowledge of a solution to a difficult problem, it can use a zero-knowledge proof so that [PERSON] is not able to trick [PERSON] and discover the solution or any information that can help it to compute anything faster than before. Thus, what [PERSON] can see thanks to the protocol should be something that it could have computed by itself. A ZKP must fulfil three main properties, usually called completeness, soundness and zero-knowledge. Completeness means that for any valid input, a prover P can always complete the proof successfully; soundness means that no malicious prover P can construct a valid proof system; and zero-knowledge means that no malicious verifier V is able to derive extra knowledge from the interaction.  
This work is based on a non-interactive zero-knowledge proof, which can be formalized as follows. If \(\{0,1\}^{*}\) denotes the set of all strings and \(R\) denotes a witness, for a language \(L\subseteq\{0,1\}^{*}\), a pair of probabilistic Turing machines \((P,V)\), in which \(P\) has probabilistic polynomial time power and \(V\) has deterministic polynomial time power, is said to be a non-interactive zero-knowledge proof system of the language \(L\) if it fulfills the following conditions related to correctness and security against malicious provers and verifiers:  
* Completeness: For any polynomial \(p(\cdot)\) and common input \(x\in L\), \(x\) is accepted by \(V\) with a probability greater than \(1-\epsilon\): \[Pr[V(x,R,P(x,R))=1]\geq 1-\frac{1}{p(|x|)}\] (1)
* Soundness: For any interactive Turing machine \(P^{\prime}\) representing a dishonest prover, any polynomial \(p(\cdot)\) and any common input \(x\in L\) provided by \(P^{\prime}\)\(x\) is accepted by \(V\) with a probability at most \(\epsilon\): \[Pr[V(x,R,P^{\prime}(x,R))=1]<\frac{1}{P(|x|)}\] (2)
* Zero-knowledge: For any \(x\in L\) provided by \(P\), no information is revealed from \(x\) to \(V\) that it could not compute alone before running the protocol, which means that there is a probabilistic polynomial time algorithm \(M\), such that: \[V(x)=x,(R\in 0,1^{c(|x|)},P(x,R))\approx_{c}M(x)_{x\in L}\] (3)  
One of the most important factors of any ZKP is the choice of the mathematical problem that forms its basis. The work [21] showed that, under certain complexity assumptions, on the one hand, any NP problem can be used to define a ZKP, and on the other hand, only problems in BPP (bounded-error probabilistic polynomial time) can be used to describe non-interactive zero-knowledge proofs.  
In this work, the chosen problem is the graph isomorphism problem. An isomorphism between two graphs is a bijection that preserves the adjacency relationship, _i.e._, any two vertices of a graph are adjacent if and only if so are their images in the other graph. The graph isomorphism problem consists of determining whether two graphs are isomorphic or not. This problem has been used in cryptography [22] because an efficient algorithm to solve it in general is yet unknown. In particular, the determination of whether two graphs with the same number \(v\) of vertices and the same number of edges are isomorphic or not involves a brute force attack, because it requires checking whether some of the \(v!\) possible bijections preserve adjacency. In general, the graph isomorphism problem is one of a few problems in computational complexity theory belonging to NP, but not known to belong to a P or to an NP-complete subset [23]. Therefore, its resolution, depending on the size and the type of the involved graphs, can be very difficult. In particular, the graph isomorphism problem has been proven to be in BPP, which opens the door to the definition of NIZKPs based on it.