## 5 A Novel Signature Scheme  
This section further develops and extends the concepts introduced in our previous work [41], providing a means for trustworthy V2V communications in offline contexts. In SCMS, a vehicle's PCs allow other vehicles to be confident that the messages originate from that vehicle and have not been altered. Similarly, the RSU could supply vehicles with certificates with up-to-date reputation, but this creates a double challenge: (1) linking the reputation certificate to PCs without breaking pseudonymity; and (2) the reuse of the reputation certificate itself compromises privacy. An alternative approach would be that the RS regularly updates and signs the RV for each PC. However, this in turn poses a scalability issue as there are typically as many as 100,000 such PCs for each vehicle [42]. In this section, we introduce a unique two-step signature scheme that addresses this privacy/scalability compromise. Many variations in regular signature schemes exist, to name a few: ring signatures [43], group signatures [44], delegatable signatures [45], blind signatures [46], or proxy signatures [47]. Unfortunately, to the best of our knowledge, no existing variation addresses the specific challenge at hand. We thus introduce a new construction, the Pre-Signature scheme, which we succinctly describe below. Although motivated by the specific needs highlighted above, the scheme may be of independent interest and is introduced in a generic context. A Pre-Signature scheme involves three parties: an Issuer \(I\), a Prover \(P\), and a Verifier \(V\). The Issuer \(I\) is considered honest. The Prover \(P\) and the Verifier \(V\) may behave maliciously. We assume familiarity with certain concepts such as _cryptographic hardness_. These are taken with the usual definitions; see e.g., [48]. **Definition 1**. : _A Pre-Signature scheme \(\mathcal{PS}\) consists of the following five algorithms:_  
* \((pk,sk)=\mathrm{keygen}(\ell)\)_:_ \(I\) _generates a public/private key pair with a security parameter (the security parameter_ \(\ell\) _is a variable determining the level of security in a cryptographic system. Increasing_ \(\ell\) _increases resistance against attacks, at the expense of increased computational and communication costs. In the specific context of the RSA-based implementation of the  
Figure 6: DENM Message Handling. scheme introduced below, \(\ell\) relates to the size of the RSA modulus.) \(\ell\), then keeps sk secret and distributes pk;
* \((k,\{(b_{i},v_{i})\}_{i=1}^{n})=\mathrm{register}(P,n)\): 1 registers a prover \(P\) by generating a hidden key \(k\), and a set of \(n\) (blinding key, verification code) pairs. 1 keeps \(k\) secret and sends the send of blinding keys and associated verification codes \(S_{P}\coloneqq\{(b_{i},v_{i})\}_{i=1}^{n}\) to \(P\), and the verification codes on their own \(\{v_{i}\}_{i=1}^{n}\) to \(V\);
* \(\sigma=\mathrm{pre-sign}(m,P)\): 1 pre-signs a message \(m\) and sends it to \(P\);
* \(\bar{\sigma}=\mathrm{complete}(\sigma,b)\): \(P\) chooses a blinding key \(b\) and completes a Pre-Signature \(\sigma\), then sends the resulting completed signature \(\bar{\sigma}\) it to \(V\). In practice, the completed signature is also accompanied with an indicator for the verification code \(v\) corresponding to the chosen blinding key \(b\);
* \(\mathrm{verify}(\bar{\sigma},m,v)\): \(V\) verifies completed signature \(\bar{\sigma}\) of message \(m\) using the associated verification code \(v\). Figure 7 depicts the operations and interactions between the three parties in a Pre-Signature scheme.