# A Low-Overhead Message Authentication and Secure Message Dissemination Scheme for VANETs
## 3 Proposed Approach
### Proposed Method
When a \(GL\) receives the above message \(M^{\prime}_{1}\) from the \(RSU\), it decrypts the message using a symmetric key \(K\) and uses the received \(ts\) to verify the freshness of the message. After that, it verifies the signature of the \(RSU\) and stores \(M_{1}\) as proof of leadership, so it can present it to the vehicles in its sub-region as proof that it is a leader. Algorithm 2 illustrates how an \(RSU\) informs the selected vehicles of their leadership (\(GL\)s). The \(GL\)s are responsible for authenticating, aggregating, and forwarding messages collected from vehicles in its sub-region. Thus, the \(RSU\) only needs to authenticate and process messages that come from \(GL\)s. Therefore, the communication and computation overhead for \(RSU\)s will be reduced. Moreover, when an \(RSU\) needs to send some message to all vehicles in its region or only to vehicles in some sub-regions, it will send that message only to the \(GL\)s in those sub-regions, which, in turn, will send it to all the vehicles in its sub-region. ```
\(RSU\) determines the number of vehicles and their locations in its region:  Based on the density of vehicles in the \(RSU\)'s region,  If Density is high { \(RSU\) selects a set of vehicles as Group Leaders (\(GL\)s);  For each vehicle selected as a \(GL\) {  Computes \(M_{1}=(E(\mbox{``}Leader^{\prime},PU_{GL},ts),PR_{RSU})\);  Encrypts \(M_{1}\) using symmetric key \(K\); // \(K\) is the symmetric key established between \(v\) and  // the \(RSU\) when \(v\) joined \(RSU\)'s region; \(M^{\prime}_{1}=(RSU,PID_{v},E(M_{1},K),SIG_{RSU})\),  where \(SIG_{RSU}=E(H(M_{1}),PR_{RSU})\);  Sends \(M^{\prime}_{1}\) to \(GL\); } else  No \(GL\)s are selected; \(RSU\) authenticates and process messages from all vehicles; } When a \(GL\) receives \(M^{\prime}_{1}\) from \(RSU\):  Decrypts \(M^{\prime}_{1}\) using \(K\);  Verifies the signature using \(PU_{RSU}\);  If verification succeeds{  Stores (\(M_{1}\)) as proof of leadership;}  Else {Discards \(M_{1}\).} ```  
**Algorithm 2**Assigning Group Leaders (\(GL\)s) for selected vehicles by \(RSU\)Next, we describe how a vehicle in a sub-region establishes a connection with its Group Leader and communicates with its Group Leader. **When a vehicle \(v\) enters the sub-region of a \(GL\):** Each \(GL\) periodically broadcasts its public key \(PU_{GL}\) and the proof of leadership received from the \(RSU\), namely, \(E((^{\ast}Leader^{\prime},PU_{GL},ts),PR_{RSU})\). When a vehicle \(v\) enters a sub-region covered by a \(GL\), it retrieves \(PU_{GL}\) from the proof of leadership. Then, \(v\) sends a join request message \(M\) to the \(GL\); \(M\) contains a \(PID_{v}\), \(Cert_{v}\), and timestamp (\(ts\)). Upon receiving \(M\), the \(GL\) checks the freshness of the message using \(ts\). Then, the \(GL\) retrieves the \(PID_{v}\) and public key \(PU_{v}\) of the vehicle from \(Cert_{v}\) and checks the \(CRL\) to determine if the vehicle's certificate has been revoked. After verification, \(GL\) sends an acceptance message and a symmetric key \(K\) to be used for secure communication between the vehicle \(v\) and the \(GL\). The acceptance message \(M_{1}^{\prime}\) contains the certificate of the \(GL\), signed by the DMV (\(Cert_{GL}\)), a \(K\), and a \(ts\), encrypted using the public key \(PU_{v}\) of \(v\) as follows: \(M_{1}^{\prime}=GL,PID_{v},(E(^{\ast}Accept^{\prime\prime},K,ts),PU_{v}),Cert _{GL},SIG_{GL})\)  
Upon receiving the above acceptance message from the \(GL\), \(v\) uses the received \(ts\) to verify the freshness of the message. After that, it verifies the signatures of the \(DMV\) and \(GL\). Note that if \(v\) does not recieve proof of leadership from a \(GL\) (this happens when the \(RSU\) has not determined leaders due to low density of vehicles in its region), after entering an \(RSU\)'s region, \(v\) sends/receives messages to/from the \(RSU\) directly, using an underlying routing protocol. Algorithm 3 illustrates the joining process when \(v\) is in the sub-region of a \(GL\).