## 4 Security Proofs
### Secure Authenticated Key Exchange  
First, we introduce a new query, \(\mathit{Test}(\Pi^{u}_{MS_{i},V_{j}})\). An adversary \(E\) can ask \(\mathit{Test}(\Pi^{u}_{MS_{i},V_{j}})\) query after \(\Pi^{u}_{MS_{i},V_{j}}\) has established a session key \(r_{3}\) with another oracle \(\Pi^{v}_{V_{j},MS_{j}}\). To answer this query, the oracle flips a fair coin \(b^{\prime}\leftarrow\{0,1\}\) and then returns \(r_{k}=r_{3}\) if \(b^{\prime}=0\) and \(r_{k}\in_{R}\{0,1\}^{l}\) if \(b^{\prime}=1\). In the following, we define an experiment which was also introduced in [15,21]. **Definition 12**. : _Let \(k\in\mathbb{N}\) be a security parameter. In this experiment, the adversary \(E\) will try to guess that the returned value \(r_{k}\) from \(\mathit{Test}(\Pi^{u}_{MS_{i},V_{j}})\) query is a random string or the real session key._  
\[ \begin{array}{ll}&\mathit{Experiment}\;Exp^{GoodGuess}_{E}(k)\\ &\text{- }b^{\prime\prime}\leftarrow\mathit{E}^{Execute,Send,Keval,Corrupt}(r_{k}= \mathit{Test}(\Pi^{u}_{MS_{i},V_{j}}))\\ &\mathit{If}\;the\;followings\;\mathit{are\;true},\;\mathit{return}\;1\text{; else return}\;0.\\ &\mathit{1.}\;b^{\prime}=b^{\prime\prime}\\ &\mathit{2.}\;E\;\mathit{has\;never\;submitted}\;\mathit{Reveal}(\Pi^{u}_{MS_{i},V_{ j}})\;\mathit{and}\\ &\mathit{Corrupt}(V_{j})\;\mathit{queries}.\end{array} \]  
_We define the advantage of \(E\) is \(Adv^{GoodGuess}_{E}(k)=\mathit{Pr}[Exp^{GoodGuess}_{E}(k)=1]-\frac{1}{2}\)._  
**Definition 13**. : _A protocol \(P=(\Pi,\mathcal{G})\) is a secure authenticated key exchange protocol if_  
1. \(P\) _is a secure mutual authentication protocol;_
2. _Both oracles_ \(\Pi^{u}_{MS_{i},V_{j}}\) _and_ \(\Pi^{v}_{V_{j},MS_{i}}\) _always accept and hold the same session key_ \(r_{3}\) _if_ \(E\) _is a benign adversary; and_
3. _For any adversary_ \(E\)_,_ \(Adv^{GoodGuess}_{E}(k)\) _is negligible._  
**Theorem 6**. : _The authentication protocol of Section 3.4 is a secure authenticated key exchange protocol if the encryption \(E_{\mathit{pky}}\) is semantic secure._Proof. : We have shown that the proposed scheme satisfies the first and second conditions of Definition 13. We consider the third condition and assume that \(E\) is an adversary who has probability \((\epsilon+\frac{1}{2})\) in outputting \(b^{\prime\prime}\) such that \(b^{\prime}=b^{\prime\prime}\) where \(\epsilon\) is non-negligible. The proof model is depicted as Figure 14.  
\(\mathcal{S}\) is a simulator who will simulate the communication environment for \(E\). \(\mathcal{S}\) first randomly selects four strings, \((\bar{r}_{1},\bar{r}_{2},\bar{r}_{3},\bar{r}_{3}^{\prime})\), and prepares \(m_{0}=(\bar{r}_{1},\bar{r}_{2},\bar{r}_{3})\) and \(m_{1}=(\bar{r},\bar{r}_{2},\bar{r}_{3}^{\prime})\). \(\mathcal{S}\) then sends \((m_{0},m_{1})\) to \(\mathcal{C}\) and obtains \(\pi=E_{pk}(m_{b})\) from \(\mathcal{C}\) where \(b\in_{\mathcal{R}}\{0,1\}\). Assume that there are \(q_{1}\) entities \(MS_{i}\)'s and \(q_{2}\) entities \(V_{j}^{\prime}\)'s. \(E\) is allowed to submit \(Execute(\Pi_{MS_{i}V_{j}^{\prime}}^{u},\Pi_{V_{j}^{\prime}MS_{i}}^{v})\) queries at most \(q_{3}\) times where \(q_{1}\), \(q_{2}\), and \(q_{3}\) are polynomials of security parameter \(k\). \(\mathcal{S}\) guesses two numbers \(\lambda\) and \(\bar{r}^{\prime}\) where \(E\) will return the guess bit \(b^{\prime\prime}\) after making \(Test(\Pi_{MS_{i}V_{j}^{\prime}}^{u})\) which is corresponding to the \(\lambda\)th \(Execute(\Pi_{MS_{i}V_{j}^{\prime}}^{u},\Pi_{V_{j}^{\prime}MS_{i}}^{v})\) query. Then, \(\mathcal{S}\) initializes \(i_{guess}=0\) and generates all public/private key pairs \((pk_{V_{j}},sk_{V_{j}})\) for all entities \(V_{j}\)'s except the entity \(V_{j}\) whose public key will be set as \(pk\) received from \(\mathcal{C}\) in Definition 7.