## 4 Security Analysis of the Proposed Protocol
### Formal Security Proof
#### 4.1.2 Security Proof  
In this section, we set up a total of eight games to simulate the semantic security of the adversary's ability to break the session key from different perspectives. Among these simulated games, the only difference is that the latter game provides more information to the adversary; the former and latter games are indistinguishable to the adversary. In each game, the simulator responds to queries from the adversary, who, in turn, obtains different information to increase their advantage of interfering with semantic security. Finally, based on the advantage of the adversary in each game, the total advantage of the adversary in interfering with the semantic security of the session key can be quantified. **Theorem 1**. : _Let \(\mathbf{P}\) be the proposed protocol, \(|\mathcal{D}|\) be the space of password, and \(n\) be the system's security parameter. Then, PPT adversary \(\mathcal{A}\) breaks \(\mathbf{P}\) with a negligible advantage \(Adv_{\mathcal{A}}^{\mathbf{P},\mathcal{D}}\) by making a series of queries, including \(q_{e}\) execute query, \(q_{s}\) send query, \(q_{h}\) hash query, and \(q_{p}\) PUF query, where \(Adv_{\mathcal{A}}^{\mathbf{P},\mathcal{D}}\) encounters the following._  
\[Adv_{\mathcal{A}}^{\mathbf{P},\mathcal{D}}\leq\frac{q_{h}^{2}+6q_{s}}{2^{l_{1}}}+ \frac{\left(q_{s}+q_{e}\right)^{2}}{p}+\frac{q_{p}^{2}+2q_{p}}{2^{l_{2}}}+2 \bigg{(}C^{{}^{\prime}}q_{send}^{{}^{\prime}}+Adv_{\mathcal{A}}^{SSA}(n)\bigg{)}\]  
Proof. : We now demonstrate and prove that the adversary's advantage in breaking the semantic security of the session key is factually negligible due to the involvement of \(\mathbf{Game_{1}}\) with \(\mathbf{Game_{5}}\). \(Succ_{i}\) is set to be the event during which \(\mathcal{A}\) guesses \(b\) in the test query of \(Game_{k}\) successfully, where \(k=1,2,\cdots,8\). \(\mathbf{Game_{1}}\): This game simulates a real attack by a random oracle. Bit \(b\) is then randomly chosen at the beginning of this game. Thus, we obtain the following:  
\[Adv_{\mathcal{A}}^{\mathbf{P},\mathcal{D}}=2\text{Pr}[Succ_{1}]-1 \tag{1}\]  
\(\mathbf{Game_{2}}\): This game shapes hash list \(\Omega_{b}\). For example, \(\mathcal{A}\) initiates a hash query \(h(\gamma)\) and hash oracle \(\Theta_{h}\) takes \(\gamma\) to retrieve \(\Omega_{h}\). If there is a retrieved hash value, \(h(\gamma)\), in \(\Omega_{h}\), \(\Theta_{h}\) responds to the hash value. Otherwise, a random string \(\psi\) will be sent to \(\mathcal{A}\); meanwhile, \((\gamma,\psi)\) is stored in \(\Omega_{h}\). Using the known list in this game, \(\mathcal{A}\) performs a test query to distinguish the real session key and the random string. Factually, given \(SK=h(h(r_{u}\parallel T_{1})\parallel r_{s}\parallel h(V_{i}\parallel ED_{i }))\), only secret values including \(U_{i}\)'s \(r_{u},V_{i}\), and \(MS_{j}\)'s \(r_{s}\) essentially comprise \(SK\). Hence, \(\mathcal{A}\) has no way of computing \(SK\) and cannot distinguish whether \(b=0\) or \(b=1\) other than making guesses. Thus, compared to \(\mathbf{Game_{1}}\), \(\mathcal{A}\)'s chance of winning this game does not empower \(\mathcal{A}\)'s advantage. \[\Pr[Succ_{2}]=\Pr[Succ_{1}] \tag{2}\]  
\(\mathbf{Game_{3}}\): In this game, the active attack is modeled based on \(\mathbf{Game_{2}}\). \(\mathcal{A}\) can execute the send query and hash query to try to persuade a participant to accept a forged message. Thus, \(\mathcal{A}\)'s advantage may be enhanced by finding the collision that generates a valid message compared with \(\mathbf{Game_{1/2}}\). That is, if the following collisions occur, this game is aborted:  
1. A collision can be found in the hash values or PUF's outputs, and the probability is \(\frac{q_{R}^{2}}{2^{l_{1}+1}}\) or \(\frac{q_{R}^{2}}{2^{l_{2}+1}}\), where \(l_{1}\) and \(l_{2}\) denote the length of output by the hash function and PUF, respectively. 2. Another collision that can be found is relative to the choice of random numbers \(r_{u},r_{g},\text{ and }r_{s}\), where the probability is \(\frac{(q_{g}+q_{e})^{2}}{2p}\).