# Two-Level-Composite-Hashing Facilitating Highly Efficient Anonymous IoT and D2D Authentication
## 3 The Proposed Schemes
### The Initialization Phase and Two-Level Composite Hashing
#### 3.1.1 Two-Level Composite Hashing  
Figure 1 shows the proposed 2 LCH. The level-1 seed and pseudonyms are used for the D2S authentications, and the level-2 seed and pseudonyms will be used in the S-assisted-once-a-while D2S2D authentication and in the direct D2D authentication. Figure 1a shows \(D_{i}\)'s level-1 seed and pseudonyms; \(D_{i}\) repetitively applies \(h_{1}()\) on its seed \(N_{i}\) to update \(N_{i}\), and each active \(N_{i}\) is applied \(h_{2}()\) to have the active pseudonym \(h_{2}(N_{i})\). Figure 1b shows \(D_{i}\)'s level-2 seed and pseudonyms for \(D_{i}-D_{\overline{i}}\) D2D authentication, where \(D_{\overline{i}}\) is \(D_{i}\)'s communicating partner in the authentication. Assume \(PN_{i,k}\) is \(D_{i}\)' active pseudonym, then \(D_{i}\)'s level-2 seed is set as \(N_{i,\overline{i}}=h_{1}(PN_{i,k},D_{i},K_{i})\) for the \(D_{i}-D_{\overline{i}}\) D2D authentication. Like the level-1 operation, \(h_{1}()\) is repetitively applied on \(N_{i,\overline{i}}\) to update its values, and \(h_{2}()\) is applied on the active \(N_{i,\overline{i}}\) to have the active pseudonym \(h_{2}\Big{(}N_{i,\overline{i}}\Big{)}\) for the \(D_{i}-D_{\overline{i}}\) D2D authentication. Likewise, Figure 1c shows that for \(D_{i}\)'s \(D_{\overline{i}}-D_{i}\) D2D authentication. Figure 2 sorts out the algorithms for the entities. \begin{table}
\begin{tabular}{l l} \hline \hline _D; S._ & **Device; Server.** \\ \hline \(h_{1}()\), \(h_{2}()\) & Two cryptographic hashing functions. _Mac_(): message authentication code function, which could be implemented, using HMAC [42]. \\ \hline \(D_{i}\), \(D_{\overline{i}}\), \(K_{i}\) & \(D_{i}\): ith device; \(D_{\overline{i}}\): ith device; \(K_{i}\): the secret key shared between \(D_{i}\) and S. \\ \hline \(N_{i}\) & \(N_{i}:\)\(D_{i}\)’s level-1 seed (a random value) for generating the chain of seed values. Each seed value is used to generate the corresponding level-1 pseudonym \(PN_{i,k}\). \\ \hline \(h_{1}i^{\prime}(N_{i})\) & \(h_{1}i^{\prime}(N_{i})=h_{1}(h_{1}(\ldots h_{1}(N_{i})))\) means \(h_{1}\) being applied j times. \\ \hline \(PN_{i,0}\), \(PN_{i,0}\) denotes \(D_{i}\)s level \(-1\) pseudonym \(PN_{i,0}=h_{2}(N_{i})\). \(PN_{i,k}=\) \\ \(PN_{i,k}\) & \(h_{2}\Big{(}h_{1}i^{k}(N_{i})\Big{)}\) denotes the \(k\)th _pseudonym_ successor \(PN_{i,0}\) \\ \hline \(PV\), \(PV_{i}\) & \(PV:\)_Pseudonym Vector; \(PV_{i}=\big{\{}PN_{i,0},PN_{i,1},\)\(\ldots,PN_{i,k},\ldots,PN_{i,w1}\big{\}}\) is the level-1 pseudonym vectors_ \\ pre-calculated by S for \(D_{i}\). \\ \hline \(w_{1}\), \(w_{2}\) & \(w_{1}\), \(w_{2}\) : two values respectively specify the window sizes of the precalculated level-1 and level-2 pseudonym vectors. \\ \hline \(N_{i,\overline{i}}\) & \(N_{i,\overline{i}}=h_{1}(PN_{i,k},D_{i},K_{i})\) is the first seed for the level-2 pseudonym chain of \(D_{i}\), where \(D_{i}\) is the \(D_{i}-D_{\overline{i}}\) D2D authentication initiator, \(D_{\overline{i}}\) is the responder, and \(PN_{i,k}\) is the matched pseudonym in the level-1 pseudonym vectors. \\ \hline \(PN_{i,\overline{i}}\), \(PN_{i,\overline{i}}=h_{2}\Big{(}h_{1}^{\prime}\Big{(}N_{i,\overline{i}}\Big{)} \Big{)}\) for j 0, where \(N_{i,\overline{i}}\) is \(D_{i}\) s current active seed for level-2 \(D_{i}-D_{\overline{i}}\) D2D authentication. \\ \hline \(PV_{i,\overline{i}}\), \(PV_{i,i}\) & \(PV_{i,\overline{i}}\)\(\big{\{}PN_{i,\overline{i}},0,\)\(PN_{i,\overline{i}},1,\)\(\ldots,PN_{i,\overline{i}},w_{2}\big{\}}\) is the precalculated level-2 pseudonym vectors for identifying \(D_{i}\) by \(D_{\overline{i}}\). Likewise, \(PV_{i,\overline{i}}\) denotes that vector for \(D_{i}\) to identify \(D_{\overline{i}}\). \\ \hline \(Enc_{K_{i}}()\) & Encryption using the key \(K_{i}\). \\ \hline \(G_{ECC}\), P, q & \(G_{ECC}\) is a cyclic multiplicative group of an order q, where the Computational Diffie–Hellman Problem (CDHP) is hard; P is a generator of \(G_{ECC}\). Here, we let \(G_{ECC}\) be a group in the elliptic curve setting for the short key size. \\ \hline \hline \end{tabular}
\end{table}