# A Low-Overhead Message Authentication and Secure Message Dissemination Scheme for VANETs
## 3 Proposed Approach
### Proposed Method
This prevents discovering the real identity of the vehicle and prevents attackers from linking messages from the same vehicle using multiple pseudonyms. During registration, a vehicle is assigned a set of pseudonyms and associated certificates. Vehicles can use any of the pseudonym-changing strategies presented in the literature [21, 25] to change pseudonyms. Therefore, the privacy of vehicles is preserved. **Communication and Computation Overhead:** In our scheme, if the density of vehicles present in an \(RSU\)'s region is low, it does not select \(GLs\). If the density of vehicles in its region is high, then the \(RSU\) selects \(GLs\) from the vehicles to help the \(RSU\) with authenticating messages. The \(GLs\) are responsible for authenticating, aggregating, and forwarding messages received from vehicles from its sub-region. Thus, an \(RSU\) only needs to authenticate and process messages that come from the \(GLs\). Therefore, the communication and computation overhead for an \(RSU\) is reduced. Note that an \(RSU\) sends messages to vehicles in its region through \(GLs\); vehicles only need to authenticate messages received from its \(GL\) if the density of vehicles is high, and not from other vehicles, so the communication and computation overhead is low for the vehicles as well. Figure 2 shows a comparison of the total communication cost of our scheme and that of the SEMA scheme [26], in terms of the number of messages exchanged between an \(RSU\) and the vehicles in its region. For the purpose of comparison, vehicle density within the region of an \(RSU\) is assumed to be high when the number of vehicles in its region is 1000 or more, and the average number of messages exchanged between a vehicle \(v\) and

is 2; otherwise, we assume that the density is low. Figure 2 shows the average number of messages exchanged between an \(RSU\) and vehicles in its region with this assumption; if the number of vehicles is less than 1000 in its region, the \(RSU\) authenticates and processes messages received from all vehicles within its region; if there are more than 1000 vehicles in its region, the \(RSU\) needs to authenticate messages that comes from the \(GL\)s only. As a result, in our scheme, the communication cost is lower on the \(RSU\) side. For example, if there are only 400 vehicles present in the region of an \(RSU\), the \(RSU\) will authenticate the same number of messages (which is \(400*2=800\) messages) in our scheme and in the SEMA scheme [26]. For comparison purposes, to compute the number of \(GL\)s needed in an \(RSU\)'s region, we assume that a predefined threshold is 100 for each \(GL\); i.e., if there are 1000 vehicles, the number of \(GL\)s needed is (\(\lceil(1000/100)\rceil=10\)) and the number of messages exchanged between the \(GL\)s and the \(RSU\) would be (\(\lceil(1000/100)\rceil*2=20\)) under our scheme, whereas under SEMA [26], the number of messages exchanged would be (\(1000*2=2000\)). Therefore, the total communication cost increases significantly with the increase of the number of vehicles under SEMA [26]. On the contrary, under our scheme, the communication cost is significantly lower. This is primarily because message collection overhead is shared by selected vehicles (GLs) in the RSU's region. We analyzed the computation overhead associated with encryption and authentication using a Toshiba computer with an Intel i3 quad-core processor with 2.50-GHZ clock frequency and 6 gigabytes of memory, running Windows 8.1 operating system. The public key cryptography-based signature and encryption scheme are based on RSA (Rivest-Shamir-Adleman) cryptography. Following are some notations used for presenting our results: time for computing RSA-based signatures (\(T_{sign}\)); time for signature verification (\(T_{verify}\)); time for encrypting a message using a public key (\(T_{EPU}\)); time for decrypting the message using a private key (\(T_{DPR}\)); time for encrypting a message using a symmetric key (\(T_{EK}\)); time for decrypting a message using a symmetric key (\(T_{DK}\)).