Existing authentication protocols to secure vehicular ad hoc networks (VANETs) raise challenges such as certificate distribution and revocation, avoidance of computation and communication bottlenecks, and reduction of the strong reliance on tamper-proof devices. This paper efficiently copes with these challenges with a decentralized group-authentication protocol in the sense that the group is maintained by each roadside unit (RSU) rather than by a centralized authority, as in most existing protocols that are employing group signatures. In our proposal, we employ each RSU to maintain and manage an on-the-fly group within its communication range. Vehicles entering the group can anonymously broadcast vehicle-to-vehicle (V2V) messages, which can be instantly verified by the vehicles in the same group (and neighboring groups). Later, if the message is found to be false, a third party can be invoked to disclose the identity of the message originator. Our protocol efficiently exploits the specific features of vehicular mobility, physical road limitations, and properly distributed RSUs. Our design leads to a robust VANET since, if some RSUs occasionally collapse, only the vehicles that are driving in those collapsed areas will be affected. Due to the numerous RSUs sharing the load to maintain the system, performance does not significantly degrade when more vehicles join the VANET; hence, the system is scalable.

Existing secure and privacy-preserving vehicular communication protocols in vehicular ad hoc networks face the challenges of being fast and not depending on ideal tamper-proof devices (TPDs) embedded in vehicles. To address these challenges, we propose a vehicular authentication protocol referred to as distributedaggregate privacy-preserving authentication. The proposed protocol is based on our new multiple trusted authority one-time identity-based aggregate signature technique. With this technique a vehicle can verify many messages simultaneously and their signatures can be compressed into a single one that greatly reduces the storage space needed by a vehicle or a data collector (e.g., the traffic management authority). Instead of ideal TPDs, our protocol only requires realistic TPDs and hence is more practical.

Public-key encryption with keyword search (PEKS) is a versatile tool. It allows a third party knowing the search trapdoor of a keyword to search encrypted documents containing that keyword without decrypting the documents or knowing the keyword. However, it is shown that the keyword will be compromised by a malicious third party under a keyword guess attack (KGA) if the keyword space is in a polynomial size. We address this problem with a keyword privacy enhanced variant of PEKS referred to as public-key encryption with fuzzy keyword search (PEFKS). In PEFKS, each keyword corresponds to an exact keyword search trapdoor and a fuzzy keyword search trapdoor. Two or more keywords share the same fuzzy keyword trapdoor. To search encrypted documents containing a specific keyword, only the fuzzy keyword search trapdoor is provided to the third party, i.e., the searcher. Thus, in PEFKS, a malicious searcher can no longer learn the exact keyword to be searched even if the keyword space is small. We propose a universal transformation which converts any anonymous identity-based encryption (IBE) scheme into a secure PEFKS scheme. Following the generic construction, we instantiate the first PEFKS scheme proven to be secure under KGA in the case that the keyword space is in a polynomial size.