# Two-Level-Composite-Hashing Facilitating Highly Efficient Anonymous IoT and D2D Authentication
## 3 The Proposed Schemes
### The S-Assist D2D Anonymous Authentication
#### 3.3.1 The S-Assist-Always D2S2D Anonymous Authentication  
This version needs only the first level of device's seed-pseudonym structure (specified in Figure 1a). Figure 4 shows the flow, where \(D_{i}\) and \(D_{\overline{i}}\) are the two devices executing the mutual anonymous authentication. Basically, this is an anonymous version of the classic challenge-and-response authentication among three entities (two devices and one server) where the server helps to distribute a temporary secret key \(K_{tmp,i,\overline{i}}\) to both \(D_{i}\) and \(D_{\overline{i}}\) so that they can authenticate each other. The details are described as follows.  
Step 1. \(D_{i}\to S\): \(PN,ID_{S},X\), \(Req\)  
\(D_{i}\) executes PN_Seed_Update(\(N_{i}\)) to generate the pseudonym \(PN\) and updates \(N_{i}\); \(D_{i}\) also calculates \(Req=Enc_{K_{i}}(D_{i},PN)\) for \(S\) to decrypt the request to derive the identity \(D_{\overline{i}}\).  
Step 2. \(S\to D_{\overline{i}^{*}}\): \(ID_{S},PN_{\overline{i}^{*}\overline{k}},PN,R1,E_{2},Res2,E_{3}\), \(Res3\)  
\(S\) first launches PV_Update(\(PN\), \(Req\)) to identify the device, gets the secret key \(K_{i}\), and decrypts/validates \(Req\). If the verification succeeds, then it updates \(PV_{i}=\{PN_{i,k+1},\ldots,\)\(PN_{i,k+1+w}\}\).  
\(S\) then chooses a random challenge \(R1\), computes the temporary secret key \(K_{tmp,i,\overline{i}}=h_{1}(^{*}Server^{\prime},\ ID_{S},PN,D_{\overline{i}},K_{i},R1)\) for \(D_{i}\) and \(D_{\overline{i}}\), and prepares the encryption \(E_{2}=Enc_{K_{\overline{i}}}\left(D_{i},K_{tmp,i,\overline{i}},X\right)\) and \(Res2=Mac(K_{\overline{i}},E_{2},R1)\) for \(D_{\overline{i}}\).  
\(S\) locates \(D_{i}^{*}s\) active \(PN\) (say \(PN_{\overline{i}\overline{k}}\)), updates \(D_{i}^{*}s\) level-1 pseudonym vectors, and prepares \(E_{3}=Enc_{K_{i}}\left(D_{\overline{i}^{*}K_{tmp,i,\overline{i}}}\right)\) and \(Res3=Mac(K_{i},PN,PN_{\overline{i}\overline{k}},ID_{S},E_{3},R1)\). It finally sends the data in Step 2 to \(D_{\overline{i}}\).  
Figure 3: \(D_{i}\)’s level-1 D2S authentication flow.  
Step 3. \(D_{\vec{i}}\to D_{i}\): \(ID_{S}\), \(PN\), \(PN_{\vec{i},\vec{k}}\), \(R1\), \(E_{3}\), \(Res3\), \(Res4\), \(Y\)  
\(D_{\vec{i}}\) decrypts \(E_{2}\), and gets \(K_{tmp,j,\vec{i}}\) and \(X\). It validates \(Res2\); if the validation succeeds, then it updates \(D_{\vec{i}}\)\(s\) seed and pseudonym vectors. It chooses a random challenge \(y\in_{R}Z_{q}^{*}\), and computes \(Y=yP\). It then prepares \(Res4=Mac\Big{(}K_{tmp,j,\vec{i}},E_{3},PN,Y\Big{)}\), and computes the session key \(K_{esss}=h_{1}(^{*}D2D^{*},ID_{S},PN,PN_{\vec{i},\vec{k}},K_{tmp,j,\vec{i}}, xyP)\), and sends the data specified in Step 3 to \(D_{i}\).  
Step 4. \(D_{i}\to D_{\vec{i}}\) : \(Res5\)  
\(D_{i}\) decrypts \(E_{3}\), gets \(D_{\vec{i}}\) and \(K_{tmp,j,\vec{i}}\), computes its own \(K_{tmp,j,\vec{i}}\), and verifies the received one. It further verifies \(Res3\) and \(Res4\). If the verifications succeed, it accepts the session, computes the session key \(K_{esss}\), and sends the response \(Res5=Mac\Big{(}K_{tmp,j,\vec{i}},Y\Big{)}\).  
Step 5. \(D_{\vec{i}}\): Verify the received \(Res5\). If it succeeds, then it accepts the session key \(K_{esss}\).