## 4 Privacy-Preserving Incentive Mechanism
### Route Validation Scheme  
To verify that the vehicle is at a certain checkpoint \(CP\), \(\delta_{CP}\) needs a position proof. Instead of using traditional GPS information (which can be easily tampered with), the position proof is generated by the witness vehicles at checkpoint \(CP\). A reasonable assumption entails the presence of a sufficient number of vehicles in proximity to the checkpoints. Consequently, the approach delineated in this section holds significance under congested conditions, where V2X communication and privacy protection are predominantly required. To protect the privacy of the witness vehicles, threshold cryptographic techniques are used in the route validation scheme. Specifically, the signatures of real witness vehicles are mixed with other fake signatures to protect their pseudonyms from being tracked. The route validation scheme can be divided into three stages: a vehicle needing a position proof initiating a request for route validation, witness vehicles replying to the request, and verifiers validating the position proof. The first stage is as follows. 1. The vehicle that wants to prove that it is at checkpoint \(CP\) (defined as the leader of the route validation scheme \(\mathcal{L}^{V}\)) generates a plaintext _pos_ describing its current position (e.g., \"on xxx link near checkpoint \(CP\) at time yyy\"). 2. \(\mathcal{L}^{V}\) requests the number of witnesses required, \(n_{w}\), from nearby RSUs and calculates the total number of signatures on the position proof as \(n_{p}=\lceil n_{w}/\eta\rceil\), where \(\eta\in(0,\ 1]\) is the privacy protection parameter (for larger \(\eta\), the pseudonyms of witness vehicles are mixed with fewer fake identities, and thus they will receive less privacy protection). That is, there should be at least \(n_{w}\) nearby vehicles that witness \(\mathcal{L}^{V}\)/\(s\) presence at \(CP\) and they should sign on the position proof. Meanwhile, there should be another \(n_{p}-n_{w}\) fake signature on the position proof as well to protect the privacy of these witness vehicles. Otherwise, anyone can learn from the position proof that these vehicles themselves are near \(CP\) at this specific time. Therefore, \(\mathcal{L}^{V}\) needs to generate and include \(n_{p}-n_{w}\) fake signatures in the route validation request such, that the witness vehicles can generate signatures that cannot be distinguished from the fake signatures. 3. \(\mathcal{L}^{V}\) generates \(n_{p}-n_{w}\) fake IDs from the feasible ID set, \(\Omega_{f}=\left\{ID_{1},ID_{2},\ldots,\ ID_{n_{p}-n_{w}}\right\}\) and the corresponding public keys, \(pk_{ID_{j}}=\sum_{i=1}^{m}h_{i}(ID_{j})y_{i}\), \(\forall j\in\{1,\ 2,\ \ldots,\ n_{p}-n_{w}\}\). \(\mathcal{L}^{V}\) generates the fake signatures for the fake vehicles. For \(ID_{i}\in\Omega_{f}\), it selects \(a_{i},\ b_{i}\in\mathbb{Z}_{q}\) and computes: \[A_{i}=a_{i}\cdot P+b_{i}\cdot pk_{ID_{i}},\] (4a) \[\beta_{i}=-b_{i}^{-1}A_{i}[x],\] (4b) \[m_{i}=\alpha_{i}\beta_{i},\] (4c) where \(A_{i}[x]\) is the \(x\) coordinate of point \(A_{i}\). Note that \((A_{i},\ \beta_{i})\) is a valid EC Elgamal signature of \(m_{i}\), because \(m_{i}\cdot P=A_{i}[x]\cdot pk_{ID_{i}}+\beta_{i}\cdot A_{i}\). The fake signatures are created but \(\mathcal{L}^{V}\) has no control over the corresponding \(m_{i}\). 5. \(\mathcal{L}^{V}\) generates \(n_{p}-n_{w}\) different indexes \(\kappa_{i}=H_{3}(A_{i})\in\mathbb{Z}_{q},\ i\in\big{\{}1,\ 2,\ldots,n_{p}-n_{w}\big{\}}\) for further Lagrange polynomial interpolation. 6. \(\mathcal{L}^{V}\) initiates the request of route validation at checkpoint \(\mathcal{C}\) by sending the following message to the nearby vehicles: \(\Big{\{}(ID_{i},\ m_{i},\ \kappa_{i})_{i=1,\ 2,\ \ldots,\ n_{p}-n_{w}},\ pos,\ n_{p},\ n_{w}\Big{\}}\) Upon receiving the route validation request, nearby vehicles that identify \(\mathcal{L}^{V}\) at checkpoint \(\mathcal{C}\) will reply to the request with a signed message back, becoming witness vehicles in \(\mathcal{L}^{V}\)'s position proof.