# Authentication Based on Non-Interactive Zero-Knowledge Proofs for the Internet of Things
## 4 NIZKP-Based Authentication
If the used hash function, problem and graph are adequate, the probability that \(Cha_{i}=0\) is \(1/2\). Thus, the probability that a legitimate node knows the key \(k_{1}\) is \(1/2\), that it knows the two keys \(k_{1}\) and \(k_{2}\) is \(1/2^{2}\),..., and that it knows the \(n\) keys \(k_{1}\), \(k_{2}\),..., \(k_{n}\) is \(1/2^{n}\). The challenges have been chosen as the known ZKP is based on isomorphic graphs. However, in the NIZKP here proposed, the challenges are defined from the result of a Boolean output of a hash function defined through the least significant bit (LSB) applied on each committed isomorphic graph. Thus, for each challenge, the response is defined as follows:  
* If \(Challenge=0\), the response is the isomorphism. * If \(Challenge=1\), the response is the solution to the problem in the isomorphic graph. The flowchart of the algorithm to be run by the receiver is shown in Figure 2. The pseudocode of the proposed scheme (Algorithm 1) is shown below. Figure 2: Flowchart of the proposed algorithm. ```
//Params: beacon, encrypted message segments //Params:\(t\_\)seg, dimension of beacon segments //Params: solg, solution in the original graph //Return: subkey, contribution to the key function getData (char[] beacon, int seg, char[] solg)
01: var \(seg\)s[]; // / Stores the message segments
02: // Message is divided into \(seg-size\) segments
03: \(seg\)s = beacon.splitByTam(\(seg\));
04: // Isomorphic graph and response
05: // First segment is not encrypted
06: var \(gi\) = getGi(\(seg\)s[0]);
07: var \(res\) = getRes(\(seg\)s[0]);
08: // The challenge is computed
09: var \(cha\) = LSB.hash(\(gi\).getBytes());
10: // Check whether the response is correct
11:if (\(res\)!= response(\(gi\), \(cha\)))
12: return; // If not correct, abort
13:endif
14: // The solution is obtained in \(gi\)
15: var \(sol\) = solve(\(gi\));
16: // \(ki\) is the encryption key of the next segment
17: var \(ki\) = \(\overline{cha}*hash(sol)\oplus cha*hash(sol\oplus solg)\)
18: var \(decryption\);
19: // The following steps are repeated
20:for (int \(i=1;i<seg\_size()-1;i++){
21: // The segment is decrypted with the key \(ki\)
22: \(decryption\) = Crypto.decrypt(\(seg\)s[\(i\)], \(ki\));
23: \(gi\) = getGi(\(decryption\));
24: \(res\) = getRes(\(decryption\));
25: \(cha\) = LSB.hash(\(gi\).getBytes());
26:if (\(res\)!= response(\(gi\), \(cha\)))
27: return;
28:endif
29: \(sol\) = solve(\(gi\));
30: \(ki\) = \(\overline{cha}*hash(sol)\oplus cha*hash(sol\oplus solg)\)
31: }
32: // Decryption of the last segment provides the
33: // contribution to the shared key. 34: return Crypto.decrypt(\(seg\)s[\(seg\)s.size()\(\)], \(ki\)); endfunction
```  
**Algorithm 1** Processing  
The receiver can access the last message segment thanks to the decryption key obtained from the previous segment after running the algorithm. This last segment contains the contribution of the sending node to the potential session key shared with each receiver. The initial graph and a secret key that is a solution to a difficult problem in such a graph are known by all legitimate network users. For example, this solution may be a Hamiltonian cycle because the Hamiltonian cycle problem for arbitrary graphs is considered a difficult problem. The Hamiltonian cycle problem consists of determining whether there is a path in the graph that visits each vertex exactly once. This problem is often considered NP-complete, but there are some particular graphsfor which the problem is polynomial or even linear. Because of this, in this paper, if the Hamiltonian cycle problem is used, the use of non-planar graphs is suggested. A graph is planar if it can be drawn in a plane without graph edges crossing. In order to check in linear time whether a given graph is non-planar, Theorem 1 can be used:  
Theorem 1. For any simple, connected, planar graph with \(v\) vertices and \(e\) edges: If \(v\geq 3\) then \(e\leq 3v-6\). Thus, this theorem can be used to prove that a graph is not planar when the above relationship between \(v\) and \(e\) is not fulfilled.