## 3 The Proposed Solution
### Building Blocks  
The proposed system uses the following primitives as building blocks:  
Let \(\mathbb{G}_{1}=\langle g\rangle,\mathbb{G}_{2}=\langle g\rangle\) and \(\mathbb{G}_{T}\) be groups of prime order \(p\). A bilinear map \(e:\mathbb{G}_{1}\times\mathbb{G}_{2}\rightarrow\mathbb{G}_{T}\) is an efficiently computable map which satisfies the following conditions:  
1. Bilinear: For all \((u,\hat{v})\in\mathbb{G}_{1}\times\mathbb{G}_{2}\) and all \(a,b\in\mathbb{Z}_{p}\) that \(e(au,b\hat{v})=e(u,\hat{v})^{ab}\).
2. Non-degenerate: \(e(g,\hat{g})\
eq 1\)  
All or Nothing Public Key Encryption with Equality Tests (AoN-PKEET)  
AoN-PKEET schemes ([52; 53; 54; 55]) allow entities to perform equality tests between cipher texts without knowing the secret key or the randomness used to encrypt. An additional trapdoor information is provided. While one can tell if two ciphertexts correspond to the same plaintext, no additional information is leaked. Thus, an AoN-PKEET Encryption scheme (\(KeyGen\), \(AEnc\), \(Dec\), \(Aut,Com\)) is an at least IND-CPA secure public key encryption scheme which is compatible with efficient zero-knowledge proofs. In our system we will employ the practical ElGamal based AoN-PKEET of [56], whose security relies on the (S)XDH assumption. Encryption is performed in \(\mathbb{G}_{1}\). The private key is an element \(\xi\in_{R}\mathbb{Z}_{p}\) and the corresponding public key is \(h=g^{\xi}\). We will describe the AoN encryption (\(AEnc\)) and the additional algorithms \(Aut\) and \(Com\). In both cases appropriate NIZKP can be provided. We refer to [56] for more details.  
* \(AEnc(h,r,m)\to C:\) On input the public encryption key, a random \(r\in_{R}\mathbb{Z}_{p}\) and a message \(m\), it outputs the encryption \(C=(K_{1},K_{2})=(g^{r},mh^{r})\).
* \(Aut(\xi)\to tk:\) On input the secret key, it returns the trapdoor information \(tk=(\hat{\rho},\hat{\phi}=\hat{\phi}^{\xi})\in\mathbb{G}_{2}^{2}\) for \(\hat{\rho}\in_{R}\mathbb{G}_{2}\), allowing equality tests for ciphertexts.
* \(Com(C,C^{\prime},tk)\rightarrow\{0|1\}:\) On input two ciphertexts \(C=(K_{1},K_{2})=(g^{a},mh^{a})\) and \(C^{\prime}=(K_{1}^{\prime},K_{2}^{\prime})=(g^{a^{\prime}},m^{\prime}h^{a^{ \prime}})\) and the trapdoor \(tk=(\hat{\rho},\hat{\phi}=\hat{\rho}^{\xi})\), it outputs \(1,\,\,if\,\,e(K_{2},\hat{\rho})\cdot e(K_{1},\hat{\phi})^{-1}=e(K_{2}^{\prime },\hat{\rho})\cdot e(K_{1}^{\prime},\hat{\phi})^{-1}\) holds and \(0\) otherwise. If the output is \(1\) then \(m=m^{\prime}\).  
Non Interactive Zero Knowldge Proofs (NIZKP)  
NIZKP are essentially protocols used by a prover, in order to prove knowledge of some information to a verifier, without revealing anything about the information itself. In our protocol, a custom NIZKP is used by vehicles to prove knowledge of the nonce chosen for credential generation, during registration. In addition, in the communication protocol, the NIZKP of [56] may be used, to force the SA to honest protocol execution. This however will imply an additional computational cost.  
Partially Blind Digital Signature Scheme  
Partially blind signatures are a special type of blind signatures consisting of two messages: a message to be blinded and a non-blinded messages having a predefined structure. We utilize the Partially Blind Signature scheme of [57], which is based on Schnorr Signatures. Essentially, the message consists of two parts: \(\mathcal{M}=\{m,m^{\prime}\}\). Here \(m\) is the actual message that will be blinded using a random \(b\) as a blinding factor: \(\overline{m}=H(m|b)\). The part \(m^{\prime}\) is a cleartext, non-blinded message whose form is mutually predefined.