# Authentication Based on Non-Interactive Zero-Knowledge Proofs for the Internet of Things
## 4 NIZKP-Based Authentication  
The proposal here described is based on a variant of NIZKP that uses only a single message to verify the knowledge and can be adapted to different levels of security, so that the larger the numberof challenges, the higher the level of safety for the verifier. In particular, the parameters used in the proposal are shown in Table 1.  
In [15], it was shown that the validity of NIZKPs relies on the computational assumption of an ideal cryptographic hash function. Thus, the proposed scheme uses a cryptographic hash function that fulfills such a requirement. In the described scheme, each node broadcasts a message to identify itself as a legitimate network node. The message consists of a number of commitments defined by isomorphic graphs generated from an initial graph known by all legitimate nodes. For instance, that graph may represent the network, so that each node represents a network user. Each commitment of the message, except the first one, is encrypted and can only be decrypted after verifying all of the previous ones. In particular, the message is divided into \(n+1\) segments that are all encrypted with different keys, except the first segment, which is not encrypted (see Figure 1). Thus, a legitimate network user can authenticate itself to join a communication session with another node if this latter node is able to decrypt all of the segments of the message broadcast by the first one, so that it can reach the last segment, which contains the contribution of the sender node to the session key. The encryption key of each segment depends on the previous segment, so that although someone wants to decipher only the last segment, this is impossible, because it would require the decryption of all previous segments. The security level of the scheme depends on the number of segments of the message, which represent different challenges. The greater the number of segments, the more \begin{table}
\begin{tabular}{c l} \hline \hline
**Notation** & **Meaning** \\ \hline \(G\) & Graph known by all legitimate nodes, on which they know how to solve a hard problem \\ \hline \(Sol_{G}\) & Solution to the hard problem in \(G\) \\ \hline \(n\) & Number of challenges \\ \hline \(Cha_{i}\) & \(i\)-th challenge proposed by the verifier \\ \hline \(G_{i}\) & \(i\)-th isomorphic graph used as a commitment \\ \hline \(Iso_{j}\) & Isomorphism between \(G\) and \(G_{i}\) \\ \hline \(Res_{i}\) & \(i\)-th response corresponding to the challenge \(Cha_{i}\) on the graph \(G_{i}\) \\ \hline \(h(\cdot)\) & Cryptographic hash function \\ \hline \(LSB(\cdot)\) & Least significant bit of an input string \\ \hline \(E_{k}(\cdot)\) & Symmetric encryption with key \(k_{i}\) \\ \hline _Subkey_ & Contribution of a node to the session key \\ \hline \hline \end{tabular}
\end{table} 
Table 1: Proposal parameters. Figure 1: Components of sent messages. complex it is to reach the last segment and to obtain the information required for the establishment of the shared key. After the two-way authentication using the same procedure, based on the idea of the Diffie-Hellman scheme, both nodes will know the shared session key, but with both exchanged subkeys. Each segment, except the last one, contains an isomorphic copy of the original graph. A one-way hash function known by all legitimate network nodes is used to define the challenge that the receiver must solve on each isomorphic graph. Moreover, the same hash function is used to define the encryption key for each message segment. The operations that the receiver must perform on the message are:  
1. Process the first segment of the message, which is not encrypted. 2. Compute, using the hash function, the challenge that matches the information included in the segment. 3. Check whether the response corresponds to the challenge and the isomorphic graph. 4. From the challenge, compute the key it has to use to decrypt the next segment. 5. Apply Steps 2 through 4 until the last segment, which once deciphered contains the information needed to establish the shared secret key.