# A Novel Dual Authenticated Encryption Scheme Suitable for Social Networking Services
## 4 Security Proof
### Security Proofs
Since our initial assumption gives the adversary \(\mathcal{A}\) the probability \(\varepsilon\) to break the proposed DAE scheme, we have  
\[\varepsilon=\mid\,\)Pr[\(\lambda^{\prime}=\lambda\)] \(-\)1/2 \(\mid\)  
\(\leq(1/2)\)Pr[\(-\)PS] \(=(1/2)\)(Pr[\(H_{3}\)O* \(\vee\) ADecrypt_ERR]) \(\leq(1/2)\)(Pr[\(H_{3}\)O* \(\)] \(+\) Pr[ADecrypt_ERR]) \(=(1/2)\)(Pr[\(H_{3}\)O* \(]\)\(+\) \(\frac{q_{ADecrypt}}{2^{k}})\)  
which means that  
\[\Pr[H_{3}\)O*] \(\geq\) 2\(\varepsilon\) \(-\)\(\frac{q_{ADecrypt}}{2^{k}}\).  
Then, the success probability of the algorithm \(\mathcal{B}\) can be represented as \(\varepsilon^{\prime}\geq\)(\(\frac{1}{q_{h_{3}}}\))(2\(\varepsilon\)\(-\)\(\frac{q_{ADecrypt}}{2^{k}}\)) and the running time is \(t^{\prime}\approx t+t_{\lambda}\). As we know that BDHP is polynomial-time intractable, the simulation result of this game is clearly a contradiction, which indicates that our initial assumption is wrong. Therefore, we conclude that the proposed DAE scheme is secure in the IND-CCA2 security notion.  
Q.E.D.  
**Theorem 2. (Proof of Unforgeability)**_In the EF-CMA security notion, the proposed DAE scheme is said to be (\(t\), \(\varepsilon\))-secure if no probabilistic polynomial-time bounded adversary having a non-negligible advantage \(\varepsilon\geq\) 10(\(q_{AEncrypt}+1\))(\(q_{AEncrypt}+q_{h1}\))/2\({}^{k}\) breaks ECDLP within the time \(t^{\prime}\leq\) 120686\(q_{h_{1}}\)t/\(\varepsilon\)._  
**Proof:** Let \(\mathcal{A}\) be a probabilistic polynomial-time adversary who can asks oracles as those stated in Definition 2 and \(h_{i}\) oracles (for \(i\) = 1, 2 and 3). Let \(q_{O}\) be the maximum times that \(\mathcal{A}\) is allowed to query for each oracle \(O\). It is assumed that in the security notion of EF-CMA, the adversary \(\mathcal{A}\) has a non-negligible advantage \(\varepsilon\) to break the proposed DAE scheme within the time \(t\). By using the techniques of oracle replay attack and Forking Lemma [36], we will create a (\(t^{\prime}\), \(\varepsilon\))-algorithm \(\mathcal{B}\) which utilizes the advantage of \(\mathcal{A}\) to break an ECDLP instance of (\(P\), \(xP\)). The goal of the algorithm \(\mathcal{B}\) is to compute \(x\). When \(\mathcal{A}\) submits an oracle query, \(\mathcal{B}\) also acts as a challenger to make response.  
**Setup:** By initializing the Setup algorithm, the challenger \(\mathcal{B}\) returns the system's public parameters \(\textit{params}=\{G_{1},\,G_{2},\,q,\,P,\,e\}\) along with a prepared random tape consisting of random bits to the adversary \(\mathcal{A}\) who also selects a target sender \(U_{a}\) and two participants \(U_{b}\) and \(U_{c}\) in the simulated three-party communication environment. Then, \(\mathcal{B}\) initiates two rounds of the proposed DAE scheme with \(\mathcal{A}\) on the same system parameters.  
**Phase 1:** The interactions between the adversary \(\mathcal{A}\) and the algorithm \(\mathcal{B}\) are described below. For all hash oracles, \(\mathcal{B}\) behaves as those in Theorem 1.  
_Keygen query:_ When \(\mathcal{A}\) submits a fresh Keygen oracle on the index \(i\) = \(a\), \(\mathcal{B}\) directly returns (\(xP\), \(\textit{Cert}_{a}\)). Otherwise, \(\mathcal{B}\) submits a Keygen(\(i\)) oracle to get (\(x_{i}\), \(Y_{i}\), \(\textit{Cert}_{i}\)) and then responds with (\(Y_{i}\), \(\textit{Cert}_{i}\)).  
_AEncrypt query:_ When \(\mathcal{A}\) submits a fresh AEncrypt oracle on \((m,\,Y_{i},\,Y_{j},\,Y_{k})\) where \(i\
otin a,\,\mathcal{B}\) responds with \(\delta\gets AEncrypt(m,\,Y_{i},\,Y_{j},\,Y_{k})\). In case that \(i=a,\,\mathcal{B}\) first chooses \(\sigma,\,v_{1}\in_{R}Z_{q}^{*}\) and then responds with \(\delta=(R,\,\sigma,\,r)\) where \(R=\sigma P+v_{1}(xP)\) and \(r=m\oplus h_{2}(R,\,\sigma,\,h_{3}(e(x_{k}R,\,Y_{j})))\). For consistency, a record of \((m,\,R,\,v_{1})\) is also added into the list of \(h_{1}\) oracle.  
**Forgery:** At the end of this game, \(\mathcal{A}\) outputs a forged ciphertext \(\delta=(R,\,\sigma,\,r)\) with respect to \((m,\,Y_{a},\,Y_{b},\,Y_{c})\).  
**Analysis of the game:** As mentioned before, the algorithm \(\mathcal{B}\) will initiate two rounds of the proposed DAE scheme with the adversary \(\mathcal{A}\) on the same parameters and random tape. By utilizing the same random tape in the second round, we can expect that the adversary \(\mathcal{A}\) always chooses identical random bits as those used in the first round. However, in the second round, we will replace the oracle response of \(h_{1}(m,\,R)\) with a new value, say \(v_{1}\)*. If the final forgery \(\delta^{*}=(R,\,\sigma^{*},\,r^{*})\) in relation to \((m,\,Y_{a},\,Y_{b},\,Y_{c})\) is also valid and \(h_{1}(m,\,R)=v_{1}\)*, the algorithm \(\mathcal{B}\) can learn two equalities:  
\[\sigma=t-xv_{1},\]  
\[\sigma^{*}=t-xv_{1}\textsuperscript{*}.\]  
Combining and further deriving the above equalities, we can compute  
\[x\,\,=\frac{\sigma-\sigma*}{v_{1}*-v_{1}}\]  
and solve the ECDLP instance.