## Appendix  
We define an experiment as follows. **Definition A1** (The Experiment of Hash Querying). : _Let \(k\in\mathcal{N}\) be a security parameter and \(\Pi^{u}_{MS_{i}V_{j}}\) and \(\Pi^{v}_{V_{j},MS_{i}}\) are two oracles who play the roles of \(MS_{i}\) and \(V_{j}\) in Section 3.4, respectively. There exists an attacker \(\mathcal{A}_{HQ}\) who can perform \(Execute(\Pi^{u}_{MS_{i}V_{j}},\Pi^{v}_{V_{j},MS_{i}})\) queries at most \(q_{HQ}\) times and observe all communication flows which are \((\alpha_{\lambda},\theta_{1_{\lambda}},T_{\lambda},\theta_{2_{\lambda}})\), \((r_{1_{\lambda}},r_{4_{\lambda}})\), and \(r_{5_{\lambda}}\) where \(\lambda=\{1,\ldots,q_{HQ}\}\) \begin{table}
\begin{tabular}{l l l l} \hline \hline
**Mobile Device** & **CPU** & **Memory** & **Execution Time** \\ \hline Mac iphone 3G & Samsung S5L8900 620 MHz & 128 MB & \\ HTC magic & Qualcomm MSM 7201A 528 MHz & 192 MB & E: 3 ms, D: 21 ms \\ Noika N95 & Dual ARM 11 332 MHz & 128 MB & \\ Sony Ericsson X1 & Qualcomm MSM 7200 528 MHz & 256 MB & \\ \hline \hline \end{tabular}  
* E: encrypting 256 bits of data; D: decrypting 256 bit of data.  
\end{table} 
Table 4: Some popular mobile devices. \begin{table}
\begin{tabular}{l c c c} \hline \hline
**RSA Operation** & **Iterations** & **Total Time** & **Milliseconds/Operation** \\ \hline
1024 Encryption & 41,051 & 30 s & 0.73 \\
1024 Decryption & 1,084 & 30 s & 27 \\
2048 Encryption & 13,912 & 30 s & 2 \\
2048 Decryption & 164 & 30 s & 183 \\
1024 Signature & 1,086 & 30 s & 27 \\
1024 Verification & 43,061 & 30 s & 0.69 \\
2048 Signature & 165 & 30 s & 181 \\
2048 Verification & 14,187 & 30 s & 2 \\ \hline \hline \end{tabular}
\end{table} 
Table 3: The benchmark of Crypto++. \(\mathcal{A}_{HQ}\) can submit Reveal\((T_{\lambda})\) to get \(m_{\lambda}\) and perform the Reveal\((r_{5_{\lambda}})\) query to obtain \((r_{2_{\lambda}}||r_{4_{\lambda}})\) where \(r_{5_{\lambda}}=F_{3}(r_{2_{\lambda}}||r_{4_{\lambda}})\oplus m_{\lambda}\). Consider the following experiment:  
\[ \begin{array}{l}\text{Experiment }Exp_{\mathcal{A}_{HQ}}^{HQ}(k)\\ \text{- }(\hat{r},\hat{\lambda})\leftarrow\mathcal{A}_{HQ}^{Exectate, Reveal}(\text{all communication flows})\\ \text{If the followings are true, return 1; else return 0.}\\ \text{1. }\mathcal{A}_{HQ}\text{ has never submitted Reveal}(r_{5_{\hat{\lambda}}})\text{ query.}\\ \text{2. }r_{5_{\hat{\lambda}}}=F_{3}(\hat{r})\oplus m_{\hat{\lambda}}\\ \text{3. }\hat{\lambda}\in\{1,\ldots,q_{HQ}\}.\end{array} \]  
We define the advantage of \(\mathcal{A}_{HQ}\) as \(Adv_{\mathcal{A}_{HQ}}^{HQ}(k)=Pr[Exp_{\mathcal{A}_{HQ}}^{HQ}(k)=1]\). Theorem A1: _If the advantage \(Adv_{\mathcal{A}_{HQ}}^{HQ}(k)\) is non-negligible, \(Adv_{\mathcal{F}}^{IND-CCA}(k)\) is also non-negligible._  
Proof: The proof model is shown in Figure A1. We will design a simulator \(\mathcal{S}_{HQ}\) who can simulate the experiment of Definition A1. First, \(\mathcal{S}_{HQ}\) randomly chooses four different strings, \((\bar{r}_{1},\bar{r}_{2},\bar{r}_{2}^{\prime},\bar{r}_{3})\), and sets \(m_{0}=(\bar{r}_{1},\bar{r}_{2},\bar{r}_{3})\) and \(m_{1}=(\bar{r}_{1},\bar{r}_{2}^{\prime},\bar{r}_{3})\). \(\mathcal{S}_{HQ}\) then sends \((m_{0},m_{1})\) to the challenger \(\mathcal{C}\), which was defined in Definition 7, and gets \(pk\) and \(\pi=E_{pk}(m_{b})\) where \(b\in_{R}\{0,1\}\). Then \(\mathcal{S}_{HQ}\) creates \(q_{1}\) mobile users \(MS_{i}\)'s and \(q_{2}\) entities \(V_{j}\)'s and guesses two integers \(j^{\prime}\) and \(\lambda^{\prime}\) where \(1\leq j^{\prime}\leq q_{2}\) and \(1\leq\lambda^{\prime}\leq q_{HQ}\), i.e., \(\mathcal{S}_{HQ}\) guesses that \(\mathcal{A}_{HQ}\) will output \((\hat{r},\hat{\lambda})\) where \(\lambda^{\prime}=\hat{\lambda}\) and \(V_{j^{\prime}}\) will be involved in the \(\lambda^{\prime}\)th \(Execute(\Pi_{MS_{i},V_{j}}^{u},\Pi_{V_{j^{\prime}},MS_{i}}^{v})\) query. \(\mathcal{S}\) also generates public/private key pairs for \(V_{j}\) where \(j=\{1,\ldots,q_{2}\}\) and \(j\
eq j^{\prime}\). The public key of \(V_{j^{\prime}}\) will be set as \(pk\).