# Improved Chaff-Based CMIX for Solving Location Privacy Issues in VANETs
## 5 Our Improved Chaff-Based CMIX Scheme
### Setup  
Let \(\mathbb{G}_{1}\), \(\mathbb{G}_{2}\) be cyclic groups of prime order \(q\), and \(g_{1},g_{2}\) be generators of \(\mathbb{G}_{1}\), \(\mathbb{G}_{2}\), respectively. Let also \(H_{1},H_{2},H_{3}\), \(H_{4}\) be hash functions where  
\[H_{1}:\{0,1\}^{*}\rightarrow\mathbb{G}_{1},\] \[H_{2}:\mathbb{G}_{2}\rightarrow\mathbb{K},\] \[H_{3}:\{0,1\}^{*}\rightarrow\{0,1\}^{\ell},\] \[H_{4}:\{0,1\}^{*}\rightarrow\mathbb{Z}_{q}^{*}\]  
\(\mathbb{K}\) is a keyspace, and \(\ell\) is a security parameter while \(\mathbb{Z}_{q}^{*}\) is the multiplicate group (which is a list of integers modulo \(q\) and are co-prime with \(q\)). Let also \(RSU_{i}\) and \(VID_{j}\) be the long-term identities of the \(i\)-th \(RSUi\) and the \(j\)-th vehicle, respectively. Furthermore, denote \(PS_{VID_{j}}\) for the pseudo-identity of the \(j\)-th vehicle. Let \((pk_{LTCA},sk_{LTCA})\) be a public and private key pair, and \(msk_{LTCA}\) be the master secret key of \(LTCA\). During the setup of \(RSUi\) and vehicle, \(LTCA\) first chooses \(x,y,z\in_{R}\mathbb{Z}_{q}^{*}\) and computes \(X=\mathbb{Z}_{1}^{x}\), \(Y=\mathbb{Z}_{1}^{y}\) and \(Z=\mathbb{Z}_{1}^{z}\). \(LTCA\) maintains a public list \(List_{pub}\) and a private list \(List_{priv}\) for \(PCA\) and \(RSUi\). As we describe below, \(RSUi\) is going to maintain \(List_{pub}\) for mutual authentication, while \(PCA\) is going to maintain \(List_{priv}\) for tracking the authentication details of registered vehicles. Next, we describe the setup of the \(RSUi\) and vehicles:  
* **RSU setup:**\(LTCA\) generates \(sk_{RSUi_{l}}\) from \((msk_{LTCA},RSUi_{l})\) in \(\mathbb{K}\) and sends it to \(RSUi\). \(LTCA\) also generates \(Cert_{RSUi_{l}}=Sign_{sk_{LTCA}}(pk_{RSUi_{l}})\), where \(pk_{RSUi}\) is the public key with respect to \(sk_{RSUi}\). \(RSUi\) then computes \(R_{i}=g_{1}^{r_{i}}\) and \(E_{i}=g_{2}^{e}\), where \(r_{i},e_{i}\in_{R}\mathbb{Z}_{q}^{*}\), and stores the tuple \((PP_{i},R_{i},E_{i})\) for later to securely communicate with the vehicles entering the mix-zone. * **Vehicle Setup:** Whenever a vehicle \(VID_{j}\) enters a new \(LTCA\) region, \(LTCA\) first generates \(sk_{VID_{j}}\) from \((msk_{LTCA},VID_{j})\) in \(\mathbb{K}\) and sends it to \(VID_{j}\). \(LTCA\) also generates \(Cert_{VID_{j}}=Sign_{sk_{LTCA}}(pk_{VID_{j}})\), where \(pk_{VID_{j}}\) is the public key with respect to \(sk_{VID_{j}}\). \(VID_{j}\) stores \(((pk_{VID_{j}},sk_{VID_{j}}),Cert_{VID_{j}})\). \(LTCA\) also incorporates the tuple \(\{(Cert_{VID_{j}},H_{j},A_{j},r_{j},P_{j},T_{j})\) into \(List_{priv}\) in \(PCA\) and \(\{A_{j},P_{j},T_{j}\}\) into List \(List_{pub}\) that is accessible for \(RSUi\), and when \(Tj\) expires in each, \(PCA\) forces the vehicles to refresh their authentication keys. The \(LTCA\) also loads existing \(RSUi\)' certificates to the vehicle. Next, 1. \(VID_{j}\) picks \(a_{j}^{\prime}\in_{R}\mathbb{Z}_{q}^{*}\) and then computes its authentication key \(a_{j}=H_{4}(a_{j}^{\prime},t_{j})\), where \(t_{i}\) is the timestamp. 2. \(VID_{j}\) computes \(H_{j}=H_{1}(Cert_{VID_{j}},a_{j})\), \(A_{j}=g_{1}^{a_{j}}\), and sends \((M,Sign_{VID_{j}}(M)\), \(Cert_{VID_{j}})\) to \(LTCA\), where \(M=(Cert_{VID_{j}},H_{j},A_{j})\). The authentication key \(a_{j}\) is saved in \(VID_{j}\). 3. \(LTCA\) generates a challenge \(R_{j}=g_{1}^{r_{j}}\) and a dynamic password \(P_{j}=A_{j}^{r_{j}}\), where \(r_{j}\in_{R}\mathbb{Z}_{q}^{*}\). The challenge \(R_{j}\) is sent to \(VID_{j}\), which stores it locally. 4. \(LTCA\) maintains the tuple \(\{Cert_{VID_{j}},H_{j},A_{j},r_{j},P_{j},T_{j}\}\), where \(T_{j}\) is the expiration date. * **PCA Setup:**\(LTCA\) generates \(sk_{PCA}\) from \((msk_{LTCA},PCA)\) in \(\mathbb{K}\) and sends it to \(PCA\). \(LTCA\) also generates \(Cert_{PCA}=Sign_{sk_{LTCA}}(pk_{PCA})\), where \(pk_{PCA}\) is the public key with respect to \(sk_{PCA}\). In addition, \(LTCA\) sends \(x,y,z,\in_{R}\mathbb{Z}_{q}^{*}\) and \(List_{priv}\) to \(PCA\).