# A More Efficient Conditional Private Preservation Scheme in Vehicular Ad Hoc Networks
## 6 Security Analysis
### Provable Security  
**1. Private Key Security.** The TA use master key to allocate initial private keys to OBUs or RSUs during the registration stage. The security of private key is based on the \(q\)-\(SDH\)[27] hardness assumption. Even through several OBUs and RSUs are compromised, deducing the private keys of other OBUS and RSUs from the compromised private key is still computationally not feasible. It is still computationally not feasible to deduce other OBUs and RSUs\({}^{\prime}\) private keys from the compromised private keys.  
**Lemma 1**.: _If the \(q\)-SDH assumption holds in \((G_{1},G_{2})\), then this scheme is secure against existential forgery under a chosen message attack._  
Proof of Lemma 1.: Assume \(A\) is a forger that \((t,q_{S},\varepsilon)\)-breaks the scheme and \(B\) is an attacker which solves the \(q\)-\(SDH\) problem in time \(t^{\prime}\) with advantage \(\varepsilon\) by interacting with \(A\). \((g_{1},g_{2},A_{1},...,A_{q})\) is an instance of the \(q\)-\(SDH\) problem, where \(A_{i}=g_{2}^{(x^{i})}\in G_{2}\) for \(i=1,...,q\) and for some unknown \(x\in Z_{p}^{*}\). For convenience, we set \(A_{0}=g_{2}\). Algorithm \(B\)'s goal is to produce a pair \((c,g_{1}^{\frac{1}{q+\varepsilon}})\) for some \(c\in Z_{p}^{*}\). It does so as follows:  
**Query:** Algorithm \(A\) chooses a list of random pseudo-id \(PID_{1},PID_{2},...,PID_{q_{s}}\in Z_{p}^{*}\), and requests for private key of \(PID_{i}\), where \(q_{s}<q\). We may assume that \(q_{s}=q-1\).  
**Response:**\(B\) must response with \(TA\)'s public key and \(PID_{i}\)'s private keys. Let \(f(y)\) be the polynomial \(f(y)=\prod_{i=1}^{q-1}(y+h(PID_{i}))\). Expand \(f(y)\) and write \(f(y)=\sum_{i=0}^{q-1}\alpha_{i}y^{i}\) where \(\alpha_{0},...,\alpha_{q-1}\in Z_{p}\). Compute:  
\[P_{2}^{\prime}\leftarrow\prod_{i=0}^{q-1}(A_{i})^{\alpha_{i}}=g_{2}^{f(x)}\quad and \quad K_{TA}\leftarrow\prod_{i=1}^{q}(A_{i})^{\alpha_{i-1}}=g_{2}^{xf(x)}=(g_{2 }^{\prime})^{x} \tag{5}\]  
Also, let \(P_{1}^{\prime}=\psi(P_{2}^{\prime})\). The public key given to \(A\) is \((P_{1}^{\prime},P_{2}^{\prime},K_{TA})\). Next, algorithm \(B\) will generate private keys \(k_{i}\) for each \(PID_{i}\) where \(i=1,2,...,q-1\). To do so, let \(f_{i}(y)\) be the polynomial \(f_{i}(y)=f(y)/(y+h(PID_{i}))=\prod_{j=1,j\
eq i}^{q-1}(y+h(PID_{j}))\). We expand and write \(f_{i}(y)=\sum_{j=0}^{q-2}\beta_{j}y^{i}\). Compute  
\[S_{i}\leftarrow\prod_{j=0}^{q-2}A_{j}^{\beta_{j}}=g_{2}^{f_{i}(x)}=(g_{2}^{ \prime})^{\frac{1}{q+h(PID_{i})}}\in G_{2} \tag{6}\]  
Observe that \(k_{i}=\psi(S_{i})\in G_{1}\) is a valid private key of \(PID_{i}\) under the public key \((P_{1}^{\prime},P_{2}^{\prime},K_{TA})\). Algorithm \(B\) gives the \(q-1\) private keys \(k_{1},...,k_{q-1}\) to \(A\).  
**Output:** Algorithm \(A\) returns a forgery \((PID_{*},k_{*})\) such that \(k_{*}\in G_{1}\) is a valid private key for \(PID_{*}\) and \(PID_{*}\
otin PID_{1},...,PID_{q-1}\). In other words, \(e(k_{*},K_{TA}\cdot(g_{2}^{\prime})^{h(PID_{*})})=e(g_{1}^{\prime},g_{2}^{ \prime})\). Since \(K_{TA}=(g_{2}^{\prime})^{x}\), we have that \(e(k_{*},(g_{2}^{\prime})^{(x+h(PID_{*}))})=e(g_{1}^{\prime},g_{2}^{\prime})\) and therefore \[k_{*}=(g_{1}^{\prime})^{\frac{1}{\pi+k(PID_{*})}}=g_{1}^{\frac{f(y)}{\pi+h(PID_{*})}} \tag{7}\]  
Using long division, we expand the polynomial \(f\) as \(f(y)=\gamma(y)(y+h(PID_{*}))+\gamma_{-1}\) for some polynomial \(\gamma(y)=\sum_{i=0}^{q-2}\gamma_{i}y^{i}\) and some \(\gamma_{-1}\in Z_{p}\). Then, computing as  
\[f(y)/(y+h(PID_{*}))=\frac{\gamma_{-1}}{y+h(PID_{*})}+\sum_{i=0}^{q-2}\gamma_{i }y^{i} \tag{8}\]  
Note that \(\gamma_{-1}\
eq 0\), since \(f(y)=\prod_{i=1}^{q-1}(y+h(PID_{i}))\) and \(PID_{*}\
otin PID_{1},...,PID_{q-1}\), as thus \((y+h(PID_{*}))\) does not divide \(f(y)\). Then, algorithm \(B\) computes  
\[\omega\leftarrow(k_{*}\cdot\prod_{i=0}^{q-2}\psi(A_{i})^{-\gamma_{i}})^{1/ \gamma_{-1}}=g_{1}^{\frac{1}{\pi+h(PID_{*})}} \tag{9}\]  
and returns \((h(PID_{*}),\omega)\) as the solution to the \(q-SDH\) instance.