# Improved Chaff-Based CMIX for Solving Location Privacy Issues in VANETs
## 5 Our Improved Chaff-Based CMIX Scheme
### Privacy Preservation: Pseudo-Identity Generation and Updating Authentication Key
#### 5.3.2 Unlinkability through Updating Authentication Key  
In order to provide unlinkability, the system must update the authentication key and the ACF regularly. Assume that the tuple \((Cert_{VID_{j}},H_{j},A_{j},r_{j},P_{j},T_{j})\) has expired based on the expiration date \(T_{j}\). Here below, to update the authentication key, \(PCA\) and the vehicle \(VID_{j}\) run the protocol.  
1. \(PCA\) 1. First generates a pseudo-identity \(PS_{j}=(A_{j},H_{j}A_{j}^{x},A_{j}^{y+\theta_{2}})\) for vehicle \(VID_{j}\), where \(\theta=H_{4}(A_{j},H_{j}A_{j}^{x})\).  
* Computes \(\hat{R}_{j}=g_{1}^{\hat{r}_{j}},R_{j}^{*}=g_{1}^{\hat{r}_{j}^{\hat{r}_{j}^{\hat{r} _{j}^{\hat{r}_{j}}}}},E_{j}=g_{2}^{\hat{r}_{j}}\), where \(\hat{r}_{j},r_{j}^{*},e_{j}\in_{R}\mathbb{Z}_{q}^{*}\). \(\hat{R}_{j}\) is used for the targeted vehicle \(VID_{j}\), \(R_{j}^{*}\) is used for \(VID_{j}\), and \(E_{j}\) is used to generate a shared key.
* Computes a signature \(Sign_{PCA}(M_{PCA})\), where \(sk_{PCA}=\) generated from \((msk_{PCA}\), \(PS_{j})\) and \(M_{PCA}=(PS_{j},\hat{R}_{j},R_{j}^{*},\hat{t}_{j})\), and \(\hat{t}_{j}\) is a timestamp.
* Broadcasts \(\mathcal{B}^{\prime}=(M_{PCA},Sign_{PCA}(M_{PCA}),\)\(Cert_{PCA})\).
* \(VID_{j}\) 1. Receives \(\mathcal{B}^{\prime}\). 2. Validates the signature \(Sign_{PCA}(M_{PCA})\) using \(pk_{PCA}\). 3. Checks the freshness of the timestamp \(\hat{t}_{j}\). 4. Checks if \(PS_{j}\stackrel{{?}}{{=}}(g_{1}^{a_{j}},H_{1}(Cert_{VID_{j}},a_{j} )X^{a_{j}})\), \(Y^{a_{j}}Z^{aa})\), where \(\theta=H_{4}(g_{1}^{a_{j}},H_{1}\)\((Cert_{VID_{j}},a_{j})X^{a_{j}})\) with \(a_{j}\) being the authentication key. Note that only the \(VID_{j}\) that holds \(a_{j}\) can compute this pseudo-identity.
* Updates the authentication key by computing \(a_{j}^{*}=H_{4}(a_{j},t_{j}),A_{j}^{*}=g_{1}^{a_{j}^{\hat{r}_{j}^{\hat{r}_{j}^ {\hat{r}_{j}}}}},H_{j}^{*}=H_{1}(Cert_{VID_{j}},a_{j}^{*})\), \(F=g_{2}^{f},K^{\prime}=H_{2}(E^{f})\) and \(\hat{P}_{j}=\hat{R}^{a_{j}}\), where \(a_{j}^{*},f\in_{R}\mathbb{Z}_{q}^{*}\).
* Sends \(C_{j}=Enc_{K}(M_{PCA},\)\(Sign_{VID_{j}}(M_{PCA}),\)\(Cert_{VID_{j}}),F,t_{j})\), where \(M_{PCA}=(A_{j}^{*},\hat{P}_{j},H_{j}^{*},H_{3}(Cert_{PCA},A_{j}^{*},\hat{P}_{j},t_ {j}))\) to \(PCA\).
* _PCA_ 1. First decrypts \(C_{j}\) and obtains \(M_{PCA}^{\prime},Sign_{VID_{j}}(M_{PCA}^{\prime}),\)\(Cert_{VID_{j}}),F,t_{j}\), where \(M_{PCA}^{\prime}=(A^{\prime},\hat{P}_{j}^{\prime},\hat{H}_{j}^{*},H_{PCA}^{\prime})\). 2. Validates \(Sign_{VID_{j}}(M_{PCA}^{\prime})\). 3. Aborts if \(H_{PCA}^{\prime}\
eq H_{3}(Cert_{PCA},A^{\prime},\hat{P}_{j}^{\hat{r}_{j}},t_{j})\). 4. Computes \(P_{j}^{\prime}=A_{j}^{\hat{r}_{j}^{\hat{r}_{j}}}\) and aborts if \(\hat{P}_{j}^{\hat{r}}\
eq P_{j}^{\prime}\). 5. Computes \(P_{j}^{\prime}=(A^{\prime})^{\hat{r}_{j}^{\hat{r}_{j}^{\hat{r}_{j}}}}\) and updates \(\{Cert_{VID_{j}},A_{j},H_{j},r_{j},P_{j},\hat{T}_{j}\}\) with \(\{Cert_{VID_{j}},\)\(A_{j}^{*},\hat{H}_{j}^{*},r_{j}^{*},P_{j}^{*},T_{j}^{*}\}\) in \(List_{piv}\), where the expiration time is \(T_{j}^{*}\). 6. The tuple \(\{A_{j},\hat{P}_{j},T_{j}\}\) is updated with \(\{A_{j}^{*},P_{j}^{*},T_{j}^{*}\}\) in \(List_{pub}\). 7. Computes \(\overline{R_{j}}=g_{1}^{\overline{\hat{r}_{j}}},\overline{P_{j}}=(A^{\prime}) ^{\overline{\hat{r}_{j}}}\), where \(\overline{r_{j}}\in_{R}\mathbb{Z}_{q}^{*}\), 8. Broadcasts \((\overline{M}_{PCA},\)\(\overline{t_{PCA}},\)\(\underline{Sign_{PCA}}(\overline{M}_{PCA}),\)\(Cert_{PCA})\), where \(\overline{t_{PCA}}\) is a timestamp and \(\overline{M}_{PCA}=(PS_{A},\overline{P_{j}},\overline{R_{j}})\).
* \(VID_{j}\) receives and checks the validity of the message. If the signature \(Sign_{PCA}(\overline{M}_{PCA})\) is valid and the timestamp \(\overline{t}\) is fresh, then it computes \(\overline{P}_{j}^{\prime}=\overline{R}^{a_{j}^{\hat{r}_{j}}}\). 5. \(VID_{j}\) aborts if \(\overline{P_{j}}\
eq\overline{P_{j}}^{\prime}\). Otherwise, the current authentication key \(a_{j}\) and challenge \(R_{j}\) are replaced with \(a_{j}^{*}\) and \(R_{j}^{*}\), respectively.