# Noninteractive, Anonymously Authenticated, and Traceable Message Transmission for VANETs

Authors: Maged Hamada Ibrahim
Journal: International Journal of Vehicular Technology
 (2009)

---

## Abstract

Unlike sensor and other ad-hoc wireless networks, vehicular
ad-hoc networks (VANETs) are characterized by its
high mobility which allows a very short communication
interval among onboard units (OBUs) and between an
OBU and road-side units (RSUs). This major characterization
motivates the design of communication protocols
that are noninteractive or at least require a very limited
number of rounds between units. The challenging issue
is that such protocols must satisfy a number of security
services that could be complex by their nature.
In secure VANETs protocols, anonymity and traceability
are two important services, yet, achieving a satisfactory
security level for both of them—with acceptable complexity—is not an easy task due to the contradicting requirements: anonymous transmission must not be traceable
by any individual while if a transmission is traceable,
then anonymity is threatened. Existing secure VANETs
protocols for anonymous and traceable transmissions either,
provide unconditional anonymity where traceability
and revocation are impossible, or grant trust to a thirdparty
not to reveal the identity of a unit unless there is a
legal reason. In this paper, we propose the first secure VANET protocol
that allows authenticated transmission among OBUs
and RSUs and at the same time enjoys the following properties.
(i) The transmission among OBUs and RSUs is
noninteractive (i.e., a one-move transmission without any
interactive setup requirements). (ii) The authenticated
transmission between any pair of units is anonymous (i.e.,
no single authority knows any information about the identity
of the communicating OBU). (iii) In serious road
crimes (e.g., hit-and-run, road rage, etc.) and under court
order, an OBU could be traced to its clear identity.
We also show how our protocol could be used to setup
a confidential session between any pair of units without
relying on extensive number of interactive rounds.


---

## Body

## 1. Introduction

Advances in wireless technology have imposed a major impact on the revolution of human's lifestyle by providing a convenient and flexible way to access the internet services and various types of personal communication applications. Recently, technologies built on IEEE 802.11 and IEEE 1609 standards, 5.9 GHz Dedicated Short Range Communications (DSRC) protocols [1–5], are proposed to support advanced vehicle safety applications through effective, reliable, and secure vehicle-to-vehicle (V2V) (also known as Inter-Vehicle Communication (IVC)) and vehicle-to-Infrastructure (V2I) communications, which are also known as Vehicle Safety Communications (VSC) technologies. U.S. Department of Transportation (USDOT) works with seven automotive manufacturers—BMW, DaimlerChrysler, Ford, GM, Nissan, Toyota, and VW—to form the Vehicle Safety Communications Consortium (VSCC) to establish the VSC project to evaluate vehicle safety applications enabled or enhanced by external vehicle communications. For example, if a possible red light violation is detected at an intersection, the potential violator will receive a warning to slow down to avoid unintentional red light violations. Meanwhile, a warning on the running red light event will be given to the other drivers at the intersection thereby minimizing the possibility of collision.


### 1.1. Vehicular Ad-Hoc Networks

Nowadays, car manufactories and telecommunication industries have been gearing up to equip each car with the technology that allows vehicles to communicate with each other as well as with a roadside infrastructure that may be located in some critical sections of the road, such as at every traffic light or any intersection or stop sign, in order to improve the driving experience and make driving safer. For example, Microsoft Corp.'s MSN TV and KVH [6] Industries Inc. have introduced an automotive vehicle Internet access system called TracNet [7], which can bring the Internet service to any in-car video screens. It also turns the entire vehicle into an IEEE 802.11-based WiFi hotspot, so passengers can use their wireless-enabled laptops to go online like they are home or in the office. Furthermore, by using those equipped communication devices, also known as On-Board Units (OBUs), vehicles can communicate with each other as well as with the Roadside units (RSUs) located in the critical points of the road. A self-organized network can be formed by connecting the vehicles and RSUs, which is called Vehicular Ad Hoc Network (VANET), and the RSUs are further connected to the backbone network via the high-speed network connections. An increasing interest has been raised recently on the applications through V2V and V2I communications, aiming to improve driving safety and traffic management while providing drivers and passengers with Internet access. It is estimated that the market for vehicular communications will reach to multibillions dollars by 2012.


### 1.2. Efficiency and Security Issues in VANETs

In a vehicular network, drivers are bound to a single identity to prevent spoofing attacks. For instance, in the congestion avoidance scheme, we would like to prevent one vehicle from claiming to be hundreds in order to create the illusion of a congested road. Strong authentication also provides valuable forensic evidence and allows us to use external mechanisms, such as traditional law enforcement, to deter or prevent attacks on vehicular networks. However, drivers value their privacy and are unlikely to adopt systems that require them to abandon their anonymity. For example, if we try to prevent spoofing in a manner that reveals each vehicle's permanent identity, then we may violate drivers' privacy expectations. Balancing anonymity concerns with traceability needs represents a challenging problem when designing a security protocol. Both of these services are important and it is insecure to design a protocol that allows one service without the other since, if anonymity is a right for a citizen, traceability is a right for the law.Vehicular networks require near real-time responses as well as hard real-time guarantees. While some applications may tolerate some margin in their response times, they will all typically require faster responses than those expected in traditional sensor networks, or even ad hoc networks. However, attempts to meet real-time demands typically make applications vulnerable to Denial of Service (DoS) attacks. For example, on open speed roads, a delay of even seconds can render the message meaningless and could be disastrous.Current plans for vehicular networks rely on the emerging standard for dedicated short-range communications (DSRC), based on an extension to the IEEE 802.11 technology. Yin et al. provide a detailed, low-level evaluation of the performance of a simulated DSRC network and find that while the current DSRC standard provides an acceptable latency, the reliability is still lacking [8]. According to their simulations, on average, only 50%–60% of a vehicle's neighbors will receive a broadcast message. Since vehicles moving with high speed will remain within communications range for only a few seconds, opportunities to retry a broadcast will be limited. On a positive note, DSRC features a high data rate.Many applications use protocols that rely on probabilistic schemes to provide security. However, given the critical life-threatening nature of many proposed vehicular applications, even a small probability of error will be unacceptable. Applications should rely on deterministic schemes or probabilistic schemes with security parameters large enough to make the probability of failure infinitesimally small. Furthermore, for many applications, security must focus on prevention of attacks, rather than detection and recovery. In an ad hoc network, it may suffice to detect an attack and alert the user, leaving recovery and clean-up to the humans. However, in many safety-related vehicular network applications, detection will be insufficient, since by the time the driver can react, the warning may be too late. Instead, security must focus on preventing attacks in the first place, which will require extensive foresight into the types of attacks likely to occur.Traditional sensor networks frequently assume a relatively static network, and even ad hoc networks typically assume limited mobility, often focusing on hand-held PDAs and laptops carried by users. For vehicular networks, mobility is the norm, and it will be measured in miles, not meters, per hour. Also, the mobility patterns of vehicles on the same road will exhibit strong correlations. Each vehicle will have a constantly shifting set of neighbors, many of whom it has never interacted with before and is unlikely to interact with again. The transitory nature of interactions in a vehicular network will restrict the utility of reputation-based schemes. For example, rating other vehicles based on the reliability of their congestion reports is unlikely to prove useful, a specific driver is unlikely to receive multiple reports from the same vehicle. Furthermore,since vehicles may only be within communication range for a matter of seconds, we cannot rely on protocols that require significant interaction between the sender and receiver.


## 1.1. Vehicular Ad-Hoc Networks

Nowadays, car manufactories and telecommunication industries have been gearing up to equip each car with the technology that allows vehicles to communicate with each other as well as with a roadside infrastructure that may be located in some critical sections of the road, such as at every traffic light or any intersection or stop sign, in order to improve the driving experience and make driving safer. For example, Microsoft Corp.'s MSN TV and KVH [6] Industries Inc. have introduced an automotive vehicle Internet access system called TracNet [7], which can bring the Internet service to any in-car video screens. It also turns the entire vehicle into an IEEE 802.11-based WiFi hotspot, so passengers can use their wireless-enabled laptops to go online like they are home or in the office. Furthermore, by using those equipped communication devices, also known as On-Board Units (OBUs), vehicles can communicate with each other as well as with the Roadside units (RSUs) located in the critical points of the road. A self-organized network can be formed by connecting the vehicles and RSUs, which is called Vehicular Ad Hoc Network (VANET), and the RSUs are further connected to the backbone network via the high-speed network connections. An increasing interest has been raised recently on the applications through V2V and V2I communications, aiming to improve driving safety and traffic management while providing drivers and passengers with Internet access. It is estimated that the market for vehicular communications will reach to multibillions dollars by 2012.


## 1.2. Efficiency and Security Issues in VANETs

In a vehicular network, drivers are bound to a single identity to prevent spoofing attacks. For instance, in the congestion avoidance scheme, we would like to prevent one vehicle from claiming to be hundreds in order to create the illusion of a congested road. Strong authentication also provides valuable forensic evidence and allows us to use external mechanisms, such as traditional law enforcement, to deter or prevent attacks on vehicular networks. However, drivers value their privacy and are unlikely to adopt systems that require them to abandon their anonymity. For example, if we try to prevent spoofing in a manner that reveals each vehicle's permanent identity, then we may violate drivers' privacy expectations. Balancing anonymity concerns with traceability needs represents a challenging problem when designing a security protocol. Both of these services are important and it is insecure to design a protocol that allows one service without the other since, if anonymity is a right for a citizen, traceability is a right for the law.Vehicular networks require near real-time responses as well as hard real-time guarantees. While some applications may tolerate some margin in their response times, they will all typically require faster responses than those expected in traditional sensor networks, or even ad hoc networks. However, attempts to meet real-time demands typically make applications vulnerable to Denial of Service (DoS) attacks. For example, on open speed roads, a delay of even seconds can render the message meaningless and could be disastrous.Current plans for vehicular networks rely on the emerging standard for dedicated short-range communications (DSRC), based on an extension to the IEEE 802.11 technology. Yin et al. provide a detailed, low-level evaluation of the performance of a simulated DSRC network and find that while the current DSRC standard provides an acceptable latency, the reliability is still lacking [8]. According to their simulations, on average, only 50%–60% of a vehicle's neighbors will receive a broadcast message. Since vehicles moving with high speed will remain within communications range for only a few seconds, opportunities to retry a broadcast will be limited. On a positive note, DSRC features a high data rate.Many applications use protocols that rely on probabilistic schemes to provide security. However, given the critical life-threatening nature of many proposed vehicular applications, even a small probability of error will be unacceptable. Applications should rely on deterministic schemes or probabilistic schemes with security parameters large enough to make the probability of failure infinitesimally small. Furthermore, for many applications, security must focus on prevention of attacks, rather than detection and recovery. In an ad hoc network, it may suffice to detect an attack and alert the user, leaving recovery and clean-up to the humans. However, in many safety-related vehicular network applications, detection will be insufficient, since by the time the driver can react, the warning may be too late. Instead, security must focus on preventing attacks in the first place, which will require extensive foresight into the types of attacks likely to occur.Traditional sensor networks frequently assume a relatively static network, and even ad hoc networks typically assume limited mobility, often focusing on hand-held PDAs and laptops carried by users. For vehicular networks, mobility is the norm, and it will be measured in miles, not meters, per hour. Also, the mobility patterns of vehicles on the same road will exhibit strong correlations. Each vehicle will have a constantly shifting set of neighbors, many of whom it has never interacted with before and is unlikely to interact with again. The transitory nature of interactions in a vehicular network will restrict the utility of reputation-based schemes. For example, rating other vehicles based on the reliability of their congestion reports is unlikely to prove useful, a specific driver is unlikely to receive multiple reports from the same vehicle. Furthermore,since vehicles may only be within communication range for a matter of seconds, we cannot rely on protocols that require significant interaction between the sender and receiver.


## 2. Previous and Related Work

In the VII system [3, 4, 9, 10], each vehicle is equipped with an OBU which integrates the technologies of wireless communications, micro-sensors, embedded systems, and GPS on vehicles. With the help of the OBUs, vehicles are able to communicate with the RSUs on the road sides, which by their role are connected to the internet. OBUs, RSUs, and the network backbone form an infrastructure integration called VII system.Since OBUs and RSUs need to authenticate each other, several contributions have been given to satisfy this service in the proper way. However, most of these contributions [11–20] rely on a policy that grants trust to the RSU or the security center (also called authentication server) in the network not to trace the identity of a particular OBU (vehicle or driver) without a legal reason. Such policy threatens anonymity and may prevent drivers from joining the service. On the other hand, the recent work of [21] provides unconditional anonymity in the sense that it is impossible to trace the identity of any OBU. The protocol requires four interactive rounds between the OBU and the RSU in order to establish a session key which will be used for all data transmission during the session. The protocol employs the idea of verifiable common encoding to allow the OBU to authenticate an RSU and vice versa which requires a large number of public key encryptions/decryptions almost equal to the number of registered users and hence suffers from high computations and communications complexities. Since anonymity is unconditional, revocation of a particular identity is also impossible. However, the authors in [21] introduced the elegant idea of adaptive anonymity as a complexity-anonymity tradeoff.In our system we will avoid the group signature schemes that rely on the existence of a group authority since, in this case, all users in the group must trust this authority, yet, our work in this paper is inspired by the recent advances in a different version of group signature schemes known as Democratic Group Signatures [22–24] where there is no group authority managing the users in the group.Democratic group signatures (DGS) [22] eliminates the role of a group manager by (i) allowing the group members themselves to initialize and setup the group, (ii) control- ling it over dynamic changes in a collective manner, and (iii) distributing traceability rights to each group individual. In this case, every group member has the individual right to trace and disclose the identity of the signer and hence, anonymity is provided against non-members. The model in [22] requires unlinkability of signatures, that is, the signature verifier cannot distinguish signatures issued by the same group member without this member being traced and disclosed. DGS schemes differ from threshold signature schemes (e.g., [25–30]) in the sense that, in DGS each group member is granted the right to generate a signature on a given message individually; a non-member verifier recognizes the signature as anonymously generated by the group. On the other hand, in threshold signatures, the signature on a given message is generated by the majority of the group (exceeding a certain threshold), yet, no coalition of minority (less than or equals the threshold) can generate the signature. Linkable democratic group signatures (LDGS) [23] realize linkability of signatures issued by the group members in a way that preserves the anonymity of the signer. More precisely, a non-member verifier is able to distinguish signatures issued by the same signer for future reference without being able to trace the identity of this signer. To achieve this property, LDGS actually employs the idea of pseudonym systems. In this scenario, each group member (in addition to his unique identity) will be assigned a unique pseudonym. Given a certain group member, all signed messages generated by this particular member will carry his unique pseudonym. A non-member verifier is able to link signed messages of the same signer via his pseudonym, yet, the verifier gains no information about the signer's identity from this pseudonym. On the other hand, each group member knows the secret tracing trapdoor parameter, by which, he is able to extract the identity of the signer from the signer's unique pseudonym.Onion routing is a technique for anonymous communication over a computer network. Messages are repeatedly encrypted and then sent through several network nodes called onion routers. Each onion router removes a layer of encryption to uncover routing instructions, and sends the message to the next router where this is repeated [31, 32]. This prevents these intermediary nodes from knowing the origin, destination, and contents of the message. The idea of onion routing (OR) is to protect the privacy of the sender and recipient of a message, while also providing protection for message content as it traverses a network. Onion routing accomplishes this according to the principle of Chaum's mix cascades (also known as MixNets) [33]: Messages travel from source to destination via a sequence of proxies (“onion routers”), which reroute messages in an unpredictable path. To prevent an adversary from eavesdropping on message content, messages are encrypted between routers. The advantage of onion routing (and mix cascades in general) is that it is not necessary to trust each cooperating router; if one or more routers are compromised, anonymous communication can still be achieved. This is because each router in an OR network accepts messages, re-encrypts them, and transmits to another onion router. An attacker with the ability to monitor every onion router in a network might be able to trace the path of a message through the network, but an attacker with more limited capabilities will have difficulty even if he controls one or more onion routers on the message's path. Onion routing does not provide perfect sender or receiver anonymity against all possible eavesdroppers that is, it is possible for a local eavesdropper to observe that an individual has sent or received a message. It does provide for a strong degree of unlinkability, in the notion that an eavesdropper cannot easily determine both the sender and receiver of a given message. Even within these confines, onion routing does not provide any absolute guarantee of privacy; rather, it provides a continuum in which the degree of privacy is generally a function of the number of participating routers versus the number of compromised or malicious routers. Onion routing provides protection (anonymity and privacy) against intermediate nodes (routers) but does not provide source and destination anonymity and hence is not suitable for VANET systems, also notice that there is no intermediate nodes between an OBU and an RSU.Ring signatures introduced in [34] and further studied in [35, 36] do not require any group manager to form a group. For signature generation, every user builds a set of public keys that includes his public key and the public keys of other users. A generated signature does not reveal the public key of the signer, but a set of public keys of all possible signers. Therefore, ring signatures cannot be used for a direct communication between a verifier and a signer. Additionally, ring signatures provide unconditional anonymity, that is, no party can reveal the signer identity. Although the LDGS introduced in [23] adds nice properties to DGS, it suffers from a serious weakness: the power to trace and disclose the identity of the signer is in the hands of each member of the group. Such individual traceability violates the anonymity attribute of group signatures, since, in practice, it maybe possible to guarantee the honesty of one authority (group manager) as in GS but it is difficult and almost impossible to guarantee the full honesty of all the group members as in LDGS. Malicious behavior of at least one of the group members violates anonymity and consequently, destroys the main merit of group signatures. Moreover, in LDGS, such traitors are undetectable.The recent contribution in [24] improves the security of the LDGS introduced in [23] to resist traitors members within the group. The tracing trapdoor parameter must not be known to individuals, yet, it could be shared on a threshold basis such that, the identity-pseudonym link of any member is kept secret from the members unless there exists a legal reason (e.g., a dispute). In case of a dispute, the majority of the members join together to recover the identity of the signer (related to a given pseudonym). The protocol is robust against possible malicious behavior of the traitors. The work assumes that there exist minority traitors (at most 1/4 of the members). However, this bound can be improved to 1/3 but with high computation and communication complexities. Our construction in this paper is based on the traitors resistant TR-LDGS introduced in [24].


## 3. Motivations and Contributions

Motivations
We argue that more efforts must be made to balance the issue of anonymity and traceability in a way that gives drivers some confidence in the system they deal with. Existing protocols do not provide the appropriate balance between anonymity and traceability in the sense that they either rely on granting trust to a single authority, or providing unconditional anonymity where traceability and revocation are impossible. Due to the high mobility of VANETs and hence, the short time available for the communication between an OBU and an RSU, it is preferred to design protocols that allow transmission in a noninteractive way (one move transmission). Protocols that require many rounds for the purpose of setting up a secure link between an OBU and an RSU must be avoided.Contributions
Our contribution in this paper is to construct a protocol for secure data transmission in VANETs. We mainly focus on secure OBU-RSU communication. Yet, at the end of the paper, we show how to realize a direct OBU-OBU communication, that is, any two OBUs may communicate directly and securely given any existing RSU in range. In our design we will try our best to make the transmission noninteractive aiming to minimize the time required to transmit a message between an RSU and an OBU. We are able to design a completely noninteractive protocol for authenticated data transmission. For realizing confidentiality service, the transmission from the OBU to the RSU is still noninteractive, however, in order for the RSU to send a first time confidential message to a particular OBU, it requires the OBU to anonymously announce its presence. We balance the contradiction between anonymity and traceability by employing a set ofn tracing authorities that share a tracing trapdoor parameter k among themselves on a threshold basis. Each OBU will communicate using a blinded version of its identity. In order to trace a particular identity, the majority of these authorities must collaborate together to extract the identity from its blinded version. In this context, drivers do not need to put any trust in any of the authorities, yet, their trust is distributed among the n authorities. There is also a security center whose purpose is the registration of the identity of the OBU and then to send this registered identity to all RSUs.


## 4. System Attributes and Outlines

In this section we discuss the merits and the outlines of our proposed protocol.


### 4.1. Security Attributes

Our protocol allows an OBU unit to noninteractively transmit messages to an RSU and vice versa with the following efficiency and security requirements:(i)
Authentication. The RSU is confident that the received message is originated from some OBU in a vehicle that was previously registered with the vehicle security center. On the other hand, the OBU is confident that the received message is originated from some authorized RSU unit.(ii)
Anonymity. From a received message, nobody gains any information about the identity of any particular vehicle. Notice that only OBU anonymity is considered. Our anonymity assumption holds as long as at most t authorities are malicious.(iii)
Traceability. In case of accidents or any severe problems on the road (e.g., hit and run) under court order, the majority of the tracing authorities (with at most t authorities may maliciously behave or even refuse to cooperate) are able to jointly trace the identity of a particular vehicle (OBU). Moreover, the authorities are able to trace the identities of all vehicles passing by a certain area (a particular RSU) in a certain period of time (the estimated time interval within which the accident took place).(iv)
Linkability.
It realizes linkability of signatures issued by the OBUs in a way that preserves their anonymity. More precisely, an RSU is able to distinguish signatures issued by the same OBU for future reference without being able to trace the identity of this OBU.(v)
Nonrepudiation. In case of accidents and under court order, when a vehicle identity is traced and revealed by the authorities from a given blinded-identity associated with a given message, it is not possible to repudiate the accusation.(vi)
Revocation. It must be easy for the security center to revoke the identity of any OBU and to prevent it from participating in the communication with any RSU.(vii)
Robustness. Since we assume that the minority of the tracing authorities could behave maliciously, the protocol should be robust against any malicious behavior during the setup and the tracing protocol.


### 4.2. Assumptions, Model, and Outlines

According to the system global parameters, we assume that each OBU comes with the unique pair(x,id) installed where x is a private key, id=f(x), and f is a suitable one-way function. The OBU could be queried to reveal the identity id while the private key x never leaves the OBU. We also assume that any OBU could behave maliciously. In our work, we assume that an RSU is authorized to create sensitive messages for the safety of the vehicles on te road and hence, we cannot runaway of assuming that any RSU is honest-but-curious, since a malicious RSU may manipulate such information, leading to disasters.We assume the existence of a set ofn authorities, as we shall call them the “tracing authorities” (𝒯𝒜={TA1,…,TAn}), where n>4t for a threshold t≥1. The authorities in the set 𝒯𝒜 are assumed fully connected via private and authenticated channels (please refer to Section 7 for more security analysis on this issue). We assume also the existence of an authority called the security center (SC). The SC is assumed honest-but-curious, that is, it is honest in the sense that it follows the execution steps of the protocol word for word but it is willing to learn any information leaked during execution. We assume that most t tracing authorities could behave maliciously while the majority of them are honest-but-curious. In this sense, we preserve the privacy of the users, since, if at most t authorities collaborate trying to reveal the identity of a particular user, they fail to do so. Only under a valid court order, all honest authorities will obey this order and join to extract the clear identity of the user.TA's Setup
In the setup phase of𝒯𝒜, a random tracing trapdoor parameter k of bit-length κ (where κ is a security parameter) is to be jointly shared among the set 𝒯𝒜 such that each TAi∈𝒯𝒜 holds a share ki of k on a t-degree polynomial. Using secure multiparty computations, the authorities 𝒯𝒜 compute a blinded version bk of k which is publicly known. While bk is publicly known, we emphasize that k is kept secret and never recovered. The 𝒯𝒜 run secure multiparty computations to share the inverse k-1 which will be used to trace an identity whenever required.OBU-SC Interaction (Registeration)
In our secure VANET system, the OBU interacts with the SC only one time and this is during registration. An OBU approaches the SC for registration of its identity as follows: the OBU is queried for its identityid and a proof of correctness of this identity (i.e., a proof that id is on the correct form). The SC forwards the accepted identity to all RSUs. From the published blinded tracing parameter bk, an OBU computes its blinded-identity as bid=bkx. Our protocol ensures that none of the 𝒯𝒜 authorities nor the SC authority has any information about which blinded-identity maps to which identity unless the set of 𝒯𝒜 collaborate. Notice that bid=idk and hence given a blinded-identity, bid the identity could be revealed by computing bidk-1.Tracing an OBU
Under court order when a certain blinded-identitybid is required to be traced to its particular identity id, bid is given as input to the tracing authorities 𝒯𝒜 where they perform secure multiparty computations to extract the identity id from this bid using the shared trapdoor parameter inverse k-1.RSU-SC Communication
The SC communicates with the RSUs in only two situations: (i) After registering a new OBU, the SC sends its blinded identity to all RSUs; (ii) In case an OBU is traced to its clear identity and needs to be revoked, the SC instructs the RSUs to remove the corresponding blinded identity from the setℐ𝒟. Both transmissions are noninteractive and require sending short messages and consequently the overheads are insignificant.OBU-RSU Communication
Now when the OBU is put on the road, the communication with any RSU is as follows (notice that the blinded tracing trapdoor parameterbk is known to all RSUs): for an OBU to send a message m to an RSU, m is hashed and signed using the OBU's private key x. The blinded-identity bid is attached to the message. The OBU also prepares a NIZK proofs of knowledge to prove to the RSU that (i)
the OBU knows the private key used to produce the signature;(ii)
the private key used in the signature is consistent with the private key used inbid;(iii)
thebid attached to the message corresponds to one of the identities held by the RSU without revealing which identity.The message is accepted by the RSU only if the above proofs are accepted.
The transmission of authenticated messages from an RSU to an OBU is trivially done using standard digital signature schemes (since anonymity of the RSU is irrelevant) and hence we do not consider this issue no more in the paper. We only notify that, an RSU always attaches thebid of the OBU to whom the message is dedicated.


## 4.1. Security Attributes

Our protocol allows an OBU unit to noninteractively transmit messages to an RSU and vice versa with the following efficiency and security requirements:(i)
Authentication. The RSU is confident that the received message is originated from some OBU in a vehicle that was previously registered with the vehicle security center. On the other hand, the OBU is confident that the received message is originated from some authorized RSU unit.(ii)
Anonymity. From a received message, nobody gains any information about the identity of any particular vehicle. Notice that only OBU anonymity is considered. Our anonymity assumption holds as long as at most t authorities are malicious.(iii)
Traceability. In case of accidents or any severe problems on the road (e.g., hit and run) under court order, the majority of the tracing authorities (with at most t authorities may maliciously behave or even refuse to cooperate) are able to jointly trace the identity of a particular vehicle (OBU). Moreover, the authorities are able to trace the identities of all vehicles passing by a certain area (a particular RSU) in a certain period of time (the estimated time interval within which the accident took place).(iv)
Linkability.
It realizes linkability of signatures issued by the OBUs in a way that preserves their anonymity. More precisely, an RSU is able to distinguish signatures issued by the same OBU for future reference without being able to trace the identity of this OBU.(v)
Nonrepudiation. In case of accidents and under court order, when a vehicle identity is traced and revealed by the authorities from a given blinded-identity associated with a given message, it is not possible to repudiate the accusation.(vi)
Revocation. It must be easy for the security center to revoke the identity of any OBU and to prevent it from participating in the communication with any RSU.(vii)
Robustness. Since we assume that the minority of the tracing authorities could behave maliciously, the protocol should be robust against any malicious behavior during the setup and the tracing protocol.


## 4.2. Assumptions, Model, and Outlines

According to the system global parameters, we assume that each OBU comes with the unique pair(x,id) installed where x is a private key, id=f(x), and f is a suitable one-way function. The OBU could be queried to reveal the identity id while the private key x never leaves the OBU. We also assume that any OBU could behave maliciously. In our work, we assume that an RSU is authorized to create sensitive messages for the safety of the vehicles on te road and hence, we cannot runaway of assuming that any RSU is honest-but-curious, since a malicious RSU may manipulate such information, leading to disasters.We assume the existence of a set ofn authorities, as we shall call them the “tracing authorities” (𝒯𝒜={TA1,…,TAn}), where n>4t for a threshold t≥1. The authorities in the set 𝒯𝒜 are assumed fully connected via private and authenticated channels (please refer to Section 7 for more security analysis on this issue). We assume also the existence of an authority called the security center (SC). The SC is assumed honest-but-curious, that is, it is honest in the sense that it follows the execution steps of the protocol word for word but it is willing to learn any information leaked during execution. We assume that most t tracing authorities could behave maliciously while the majority of them are honest-but-curious. In this sense, we preserve the privacy of the users, since, if at most t authorities collaborate trying to reveal the identity of a particular user, they fail to do so. Only under a valid court order, all honest authorities will obey this order and join to extract the clear identity of the user.TA's Setup
In the setup phase of𝒯𝒜, a random tracing trapdoor parameter k of bit-length κ (where κ is a security parameter) is to be jointly shared among the set 𝒯𝒜 such that each TAi∈𝒯𝒜 holds a share ki of k on a t-degree polynomial. Using secure multiparty computations, the authorities 𝒯𝒜 compute a blinded version bk of k which is publicly known. While bk is publicly known, we emphasize that k is kept secret and never recovered. The 𝒯𝒜 run secure multiparty computations to share the inverse k-1 which will be used to trace an identity whenever required.OBU-SC Interaction (Registeration)
In our secure VANET system, the OBU interacts with the SC only one time and this is during registration. An OBU approaches the SC for registration of its identity as follows: the OBU is queried for its identityid and a proof of correctness of this identity (i.e., a proof that id is on the correct form). The SC forwards the accepted identity to all RSUs. From the published blinded tracing parameter bk, an OBU computes its blinded-identity as bid=bkx. Our protocol ensures that none of the 𝒯𝒜 authorities nor the SC authority has any information about which blinded-identity maps to which identity unless the set of 𝒯𝒜 collaborate. Notice that bid=idk and hence given a blinded-identity, bid the identity could be revealed by computing bidk-1.Tracing an OBU
Under court order when a certain blinded-identitybid is required to be traced to its particular identity id, bid is given as input to the tracing authorities 𝒯𝒜 where they perform secure multiparty computations to extract the identity id from this bid using the shared trapdoor parameter inverse k-1.RSU-SC Communication
The SC communicates with the RSUs in only two situations: (i) After registering a new OBU, the SC sends its blinded identity to all RSUs; (ii) In case an OBU is traced to its clear identity and needs to be revoked, the SC instructs the RSUs to remove the corresponding blinded identity from the setℐ𝒟. Both transmissions are noninteractive and require sending short messages and consequently the overheads are insignificant.OBU-RSU Communication
Now when the OBU is put on the road, the communication with any RSU is as follows (notice that the blinded tracing trapdoor parameterbk is known to all RSUs): for an OBU to send a message m to an RSU, m is hashed and signed using the OBU's private key x. The blinded-identity bid is attached to the message. The OBU also prepares a NIZK proofs of knowledge to prove to the RSU that (i)
the OBU knows the private key used to produce the signature;(ii)
the private key used in the signature is consistent with the private key used inbid;(iii)
thebid attached to the message corresponds to one of the identities held by the RSU without revealing which identity.The message is accepted by the RSU only if the above proofs are accepted.
The transmission of authenticated messages from an RSU to an OBU is trivially done using standard digital signature schemes (since anonymity of the RSU is irrelevant) and hence we do not consider this issue no more in the paper. We only notify that, an RSU always attaches thebid of the OBU to whom the message is dedicated.


## 5. Our Basic Tools

In this section we describe the basic tools that will be used to build our secure VANET system. These tools are partitioned into two categories: threshold cryptography tools and proofs of knowledge tools. The reader must be familiar with these tools in order to follow the description of our VANET protocol.


### 5.1. Threshold Cryptography Tools

In this subsection we describe the threshold cryptographic tools used in building our VANET protocol.


#### 5.1.1. Secret Sharing over a Prime Field

Lets∈Zq be a secret held by some dealer where Zq is a prime field. In order to share this secret among a set 𝒫={P1,…,Pn} of n>t players [37], the dealer, defines a polynomial f(x)=∑j=0tajxjmodq, he sets a0=s and each other coefficient aj≠0∈RZq. For all i=1,…,n, the dealer secretly delivers f(i) to player Pi. In the reconstruction phase, each player Pi broadcasts f(i), the players are able to compute s from any t+1 shares using Lagrange interpolation formula, s=f(0)=Σi∈ℬλif(i)modq, where ℬ⊂𝒫,|ℬ|=t+1, and λi is Lagrange coefficient for player Pi.


#### 5.1.2. Verifiable Secret Sharing

Verifiable secret sharing (VSS) extends polynomial secret sharing in a way that allows the recipients of the shares to verify that their shares are consistent (i.e., that any subset oft+1 shares determines the same unique secret). Assuming n>2t, the protocol can tolerate malicious behaviors (e.g., illegal collaboration, sending wrong values, deleting values, etc.) of at most t players. We distinguish two different contributions of VSS; the conditionally secure VSS due to Feldman [38] and the unconditionally secure VSS due to Pedersen [39]. To achieve best security, both of them will be used in our protocol.Feldman's VSS
Two large primesp and q are chosen such that q∣p-1. The primes p and q and an element g∈Zp* of order q are published as the system public parameters. The dealer shares the secret s among the players on a t-degree polynomial f(x)=∑j=0tajxjmodq; the dealer also broadcasts the t+1 commitments cj=gajmodp for all j=0,…,t. These commitments allow each player Pi to verify the consistency of his share f(i) by checking that, gf(i)=∏j=0tcjijmodp. If this check fails for any share f(i), Pi broadcasts a complaint. If more than t players broadcasted a complaint, then at least one of them is honest and consequently the dealer is disqualified. Otherwise, the dealer reveals the share f(i) for each complaining player Pi, if the share is correct, Pi is disqualified, otherwise, if the share does not satisfy the commitments or if the dealer does not respond, the dealer is disqualified. During reconstruction of the secret, any player can check the validity of the share broadcasted by any other player via the published commitments to filter out bad shares and safely perform the interpolation. When it comes to the distributed generation of a secret key k and the joint computation of gkmodp, Feldman's VSS alone is not secure due to the attacks described in the security analysis section.Pedersen's VSS
The idea is to use double exponentiation which allows randomization. The public parameters arep,q,g, and h where p,q, and g are as in Feldman's VSS and h is another element in Zp* subject to the condition that loggh is unknown and assumed hard to compute. In addition to the polynomial f(x)=∑j=0tajxjmodq which holds the secret s as the free term, the dealer sets up a randomizing t-degree polynomial r(x)=∑j=0tbjxjmodq. He secretly delivers (f(i),r(i)) to player Pifor all i=1,…,n. The dealer also publishes the commitments cj=gajhbjmodpfor all j=0,…,t. Each player Pi verifies the consistency of his share f(i) by checking that gf(i)hr(i)=∏j=0tcjijmodp. If this check fails for any share f(i), Pi broadcasts a complaint. If more than t players broadcast a complaint, then at least one of them is honest and consequently the dealer is disqualified. Otherwise, the dealer reveals the pair (f(i),r(i)) for each complaining player Pi, if the pair is correct, Pi is disqualified, otherwise, if the pair does not satisfy the commitments or if the dealer does not respond, the dealer is disqualified. During reconstruction of the secret, any player can check the validity of the share broadcasted by any other player via the published commitments to filter out bad shares and safely perform the interpolation.


#### 5.1.3. Joint Secret Sharing

Joint secret sharing allows the players to jointly share some secret among themselves without the help of the dealer.Joint Random Secret Sharing (JRSS)
JRSS [40] allows a set of n players to jointly share a random secret without the help of the dealer. Each player Pi∈𝒫 picks a random integer ki∈Zq and plays the role of the dealer to share ki among the players over a t-degree polynomial fi(x)=ki+∑j=1tajxjmodq. Each player Pi∈𝒫 simply sums the shares he receives from the other players to compute a share f(i)=∑j=1nfj(i) which is a point on a t-degree polynomial f(x) with its free term equals a random secret k=∑i=1nkimodq.Joint Random Verifiable Secret Sharing (JRVSS)
To withstand malicious behavior of at mostt<n/2 players during the JRSS, JRVSS combines the JRSS with Feldman's VSS for computational security or Pedersen's VSS for unconditional security. Simply, each player Pi∈𝒫 picks a random secret integer ki∈Zq and plays the role of the dealer in the VSS protocol to share this secret among the other players. Complaints are solved as in the VSS protocol. Finally, each player sums what he has to compute his share on a t-degree polynomial f(x) with its free term f(0)=∑i=1nkimodq.Joint Zero Secret Sharing (JZSS)
JZSS is a special case of the JRSS in which the random secret shared by each player is a zero. At the end of the JZSS, each player holds a sharef(i) on a t-degree polynomial f(x) with its free term f(0)=0.Joint Zero Verifiable Secret Sharing (JZVSS)
As in the JRVSS, to with stand malicious behavior of at mostt<n/2 players during the JZSS, JZVSS combines the JZSS with Feldman's VSS for computational security or Pedersen's VSS for unconditional security. Simply, each player Pi∈𝒫 plays the role of the dealer in the VSS protocol to share a zero among the other players. Complaints are solved as in the JRVSS protocol. Finally, each player sums what he has to compute his share on a t-degree polynomial f(x) with its free term f(0)=0. Notice that, from the published commitments, each player can verify that the shared secret is really a zero. This is true since the commitment to a zero will be g0=1.


#### 5.1.4. The Multiplication Protocol

Given two secretsa and b shared over t-degree polynomials A(x) and B(x) respectively, the multiplication protocol [41] computes ξ=abmodq in a robust way with no information revealed about a or b. Each player Pi locally computes C(i)=A(i)B(i)modq. In this case, each C(i) is a share on a 2t-degree polynomial C(x)=A(x)B(x)modq with C(0)=ξ. However, publishing and interpolating the shares C(1),…,C(n) reveals information about A(x) and B(x) [21], consequently, randomizing the shares of C(x) is necessary. To randomize the shares of C(x) without changing C(0), the players run a JZVSS to share a zero over a 2t-degree polynomial R(x) with R(0)=0. Finally, each player P(i) computes and publishes D(i)=C(i)+R(i). The result ξ could be reached by interpolating the 2t-degree polynomial D(x) with the help of the Berlekamp-Welch decoding scheme [22] to filter out corrupted shares. Since we are interpolating a polynomial of degree deg=2t and we have a maximum of t malicious players (i.e., at most t possible faults), using the Berlekamp-Welch bound, the number of shares needed in order to correctly interpolate the polynomial is at least deg + 2faults + 1 = 4t+1. Hence, we need n>4t.


#### 5.1.5. The Reciprocal Protocol

In the tracing protocol of our TR-LDGS, we are faced with the following problem. Given a secretk which is shared among the players, generate a sharing of the reciprocal of k modulo q with no information revealed about k. Each player Pi holds a share f(i) which is a point on a t-degree polynomial f(x) with f(0)=k. To compute shares of k-1, we need n>4t, the n players run the reciprocal protocol [25] as follows:(i)
The players run theJRVSS; at the end, each player holds a share v(i) of a random secret v over a polynomial of degree t.(ii)
The players run themultiplication protocol and reconstruct the value ξ=kvmodq.(iii)
Finally each playerPi computes his share of the reciprocal as ξ-1v(i)modq, which is a share over a t-degree polynomial with its free term equals k-1modq.


### 5.2. Proofs of Knowledge

In this subsection we describe the proof of knowledge tools used in building our TR-LDGS.


#### 5.2.1. Proof of Knowledge of Discrete log

Letp and q be two large primes, where q∣p-1, and g is a generator. We review Schnorr's protocol [42] that allows a prover 𝒫 to prove to a verifier 𝒱 that he knows the Dlog of y to the base g modulo p. Let y=gxmodp, where x is 𝒫's secret. The protocol is as follows:(i)
𝒫→𝒱 picks r∈RZq, computes and sends A=gr.(ii)
𝒱→𝒫 picks and sends c∈RZq.(iii)
𝒫→𝒱 computes and sends s=r+cx.(iv)
𝒱 accepts if gs=tyc, else, rejects.We denote the above protocol byΠDlog←PDlog(g,y,x).


#### 5.2.2. Proof of Equality of Two Discrete Logarithms

We review the protocol of [42, 43] that is believed to be a zero knowledge proof of equality of two discrete logarithms. In this protocol, the public parameters are two large primes p and q such that q∣p-1, two elements α,β∈Zp*, and the two quantities G1,G2∈Zp*. The prover (𝒫) proves to a verifier (𝒱) that he knows x∈Zq* such that G1=αxmodp and G2=βxmodp. The protocol is as follows:(i)
𝒫→𝒱: Choose r∈RZq* and send (A=αrmodp, B=βrmodp).(ii)
𝒱→𝒫:Choose c∈RZq* and send c.(iii)
𝒫→𝒱:Send y=r+cxmodq.(iv)
𝒱:Check that αy=AG1cmodp and βy=BG2cmodp.The standard method to convert the above protocol to a non-interactive protocol (we denote itΠLogEq←PLogEq(α,β,G1,G2,x) ) is by using a sufficiently strong hash function ℋ and setting c=ℋ(A,B). The protocol ΠLogEq becomes as follows:(i)
𝒫→𝒱: Choose r∈RZq* and send (A=αrmodp, B=βrmodp, c=ℋ(A,B) and y=r+cxmodq).(ii)
𝒱: Check that αy=AG1cmodp and βy=BG2cmodp.


#### 5.2.3. Proof of Existence of Discrete log Equality

Letyi=αximodp for i=1,…,n, and let z=βximodp for some i∈{1,…,n}. A prover 𝒫 demonstrates to a verifier 𝒱 that he knows one of the logarithms of yi (i∈{1,…,n}) to the base α and that logαyi=logβzmodq without revealing which i. Let wlog the relation holds for i=1 (i.e., x1=logαy1=logβzmodq). The protocol is as follows [29]:(i)
𝒫→𝒱:Choose ki∈RZq* for i=1,…,n, cj∈RZq* for j=2,…,n and compute
(a)
r1=αk1modp, ri=αkiyi-cimodp for i=2,…,n,(b)
t1=βk1modp, ti=βkiz-cimodp for i=2,…,n.Send the values(r1,…,rn,t1,…,tn).(ii)
𝒱→𝒫:Choose and send c∈RZq*.(iii)
𝒫→𝒱:Calculate c1=c-∑i=2ncimodq, s1=x1c1+k1modq, and set si=ki for i=2,…,n. Send (c1,…,cn,s1,…,sn).(iiii)
𝒱:Check that c=∑i=1nci and that for all i=1,…,n:αsi=yicirimodp and βsi=zcitimodp.The above interactive proof can be transformed into a non-interactive proof that we will denote it by:(1)∏∃LogEq⟵P∃LogEq(α,β,y1,…,yn,z)
using a strong hash function ℋ. This can be done by setting(2)c=ℋ(y1,…,yn,α,z,β,αs1y1-c1,…,αsnyn-cn,βs1z-c1,…,βsnz-cn).


### 5.3. El-Gamal Cryptosystem

Achieving the confidentiality service in our secure VANET system relies on the El-Gamal cryptosystem [44]. It is known that the El-Gamal cryptosystem works for any family of groups for which the discrete logarithm is considered intractable. Part of the security of the scheme actually relies on the Diffie-Hellman assumption, which implies the hardness of computing discrete logarithms modulo of a large prime. We will present our results for subgroups Gq of order q of Zp*, where p and q are large primes such that q∣p-1. Other practical families can be obtained for elliptic curves over finite fields. We will now briefly describe the El-Gamal cryptosystem, where the primes p and q and at least one generator g of Gq are treated as system public parameters. The key pair of a receiver in the El-Gamal cryptosystem consists of a private key s (randomly chosen by the receiver) and the corresponding public key h=gs. Given a message m∈Zp, encryption proceeds as follows. The sender chooses a random r∈Zq, and sends the pair (A,B)=(gr,hrm) as the ciphertext to the receiving party. To decrypt the ciphertext (A,B) the receiver recovers the plaintext as m=B/As, using the private key s. The El-Gamal encryption is known to be a CPA-secure cryptosystem, there exist extensions to this cryptosystem that achieve CCA1 and CCA2 security.


## 5.1. Threshold Cryptography Tools

In this subsection we describe the threshold cryptographic tools used in building our VANET protocol.


### 5.1.1. Secret Sharing over a Prime Field

Lets∈Zq be a secret held by some dealer where Zq is a prime field. In order to share this secret among a set 𝒫={P1,…,Pn} of n>t players [37], the dealer, defines a polynomial f(x)=∑j=0tajxjmodq, he sets a0=s and each other coefficient aj≠0∈RZq. For all i=1,…,n, the dealer secretly delivers f(i) to player Pi. In the reconstruction phase, each player Pi broadcasts f(i), the players are able to compute s from any t+1 shares using Lagrange interpolation formula, s=f(0)=Σi∈ℬλif(i)modq, where ℬ⊂𝒫,|ℬ|=t+1, and λi is Lagrange coefficient for player Pi.


### 5.1.2. Verifiable Secret Sharing

Verifiable secret sharing (VSS) extends polynomial secret sharing in a way that allows the recipients of the shares to verify that their shares are consistent (i.e., that any subset oft+1 shares determines the same unique secret). Assuming n>2t, the protocol can tolerate malicious behaviors (e.g., illegal collaboration, sending wrong values, deleting values, etc.) of at most t players. We distinguish two different contributions of VSS; the conditionally secure VSS due to Feldman [38] and the unconditionally secure VSS due to Pedersen [39]. To achieve best security, both of them will be used in our protocol.Feldman's VSS
Two large primesp and q are chosen such that q∣p-1. The primes p and q and an element g∈Zp* of order q are published as the system public parameters. The dealer shares the secret s among the players on a t-degree polynomial f(x)=∑j=0tajxjmodq; the dealer also broadcasts the t+1 commitments cj=gajmodp for all j=0,…,t. These commitments allow each player Pi to verify the consistency of his share f(i) by checking that, gf(i)=∏j=0tcjijmodp. If this check fails for any share f(i), Pi broadcasts a complaint. If more than t players broadcasted a complaint, then at least one of them is honest and consequently the dealer is disqualified. Otherwise, the dealer reveals the share f(i) for each complaining player Pi, if the share is correct, Pi is disqualified, otherwise, if the share does not satisfy the commitments or if the dealer does not respond, the dealer is disqualified. During reconstruction of the secret, any player can check the validity of the share broadcasted by any other player via the published commitments to filter out bad shares and safely perform the interpolation. When it comes to the distributed generation of a secret key k and the joint computation of gkmodp, Feldman's VSS alone is not secure due to the attacks described in the security analysis section.Pedersen's VSS
The idea is to use double exponentiation which allows randomization. The public parameters arep,q,g, and h where p,q, and g are as in Feldman's VSS and h is another element in Zp* subject to the condition that loggh is unknown and assumed hard to compute. In addition to the polynomial f(x)=∑j=0tajxjmodq which holds the secret s as the free term, the dealer sets up a randomizing t-degree polynomial r(x)=∑j=0tbjxjmodq. He secretly delivers (f(i),r(i)) to player Pifor all i=1,…,n. The dealer also publishes the commitments cj=gajhbjmodpfor all j=0,…,t. Each player Pi verifies the consistency of his share f(i) by checking that gf(i)hr(i)=∏j=0tcjijmodp. If this check fails for any share f(i), Pi broadcasts a complaint. If more than t players broadcast a complaint, then at least one of them is honest and consequently the dealer is disqualified. Otherwise, the dealer reveals the pair (f(i),r(i)) for each complaining player Pi, if the pair is correct, Pi is disqualified, otherwise, if the pair does not satisfy the commitments or if the dealer does not respond, the dealer is disqualified. During reconstruction of the secret, any player can check the validity of the share broadcasted by any other player via the published commitments to filter out bad shares and safely perform the interpolation.


### 5.1.3. Joint Secret Sharing

Joint secret sharing allows the players to jointly share some secret among themselves without the help of the dealer.Joint Random Secret Sharing (JRSS)
JRSS [40] allows a set of n players to jointly share a random secret without the help of the dealer. Each player Pi∈𝒫 picks a random integer ki∈Zq and plays the role of the dealer to share ki among the players over a t-degree polynomial fi(x)=ki+∑j=1tajxjmodq. Each player Pi∈𝒫 simply sums the shares he receives from the other players to compute a share f(i)=∑j=1nfj(i) which is a point on a t-degree polynomial f(x) with its free term equals a random secret k=∑i=1nkimodq.Joint Random Verifiable Secret Sharing (JRVSS)
To withstand malicious behavior of at mostt<n/2 players during the JRSS, JRVSS combines the JRSS with Feldman's VSS for computational security or Pedersen's VSS for unconditional security. Simply, each player Pi∈𝒫 picks a random secret integer ki∈Zq and plays the role of the dealer in the VSS protocol to share this secret among the other players. Complaints are solved as in the VSS protocol. Finally, each player sums what he has to compute his share on a t-degree polynomial f(x) with its free term f(0)=∑i=1nkimodq.Joint Zero Secret Sharing (JZSS)
JZSS is a special case of the JRSS in which the random secret shared by each player is a zero. At the end of the JZSS, each player holds a sharef(i) on a t-degree polynomial f(x) with its free term f(0)=0.Joint Zero Verifiable Secret Sharing (JZVSS)
As in the JRVSS, to with stand malicious behavior of at mostt<n/2 players during the JZSS, JZVSS combines the JZSS with Feldman's VSS for computational security or Pedersen's VSS for unconditional security. Simply, each player Pi∈𝒫 plays the role of the dealer in the VSS protocol to share a zero among the other players. Complaints are solved as in the JRVSS protocol. Finally, each player sums what he has to compute his share on a t-degree polynomial f(x) with its free term f(0)=0. Notice that, from the published commitments, each player can verify that the shared secret is really a zero. This is true since the commitment to a zero will be g0=1.


### 5.1.4. The Multiplication Protocol

Given two secretsa and b shared over t-degree polynomials A(x) and B(x) respectively, the multiplication protocol [41] computes ξ=abmodq in a robust way with no information revealed about a or b. Each player Pi locally computes C(i)=A(i)B(i)modq. In this case, each C(i) is a share on a 2t-degree polynomial C(x)=A(x)B(x)modq with C(0)=ξ. However, publishing and interpolating the shares C(1),…,C(n) reveals information about A(x) and B(x) [21], consequently, randomizing the shares of C(x) is necessary. To randomize the shares of C(x) without changing C(0), the players run a JZVSS to share a zero over a 2t-degree polynomial R(x) with R(0)=0. Finally, each player P(i) computes and publishes D(i)=C(i)+R(i). The result ξ could be reached by interpolating the 2t-degree polynomial D(x) with the help of the Berlekamp-Welch decoding scheme [22] to filter out corrupted shares. Since we are interpolating a polynomial of degree deg=2t and we have a maximum of t malicious players (i.e., at most t possible faults), using the Berlekamp-Welch bound, the number of shares needed in order to correctly interpolate the polynomial is at least deg + 2faults + 1 = 4t+1. Hence, we need n>4t.


### 5.1.5. The Reciprocal Protocol

In the tracing protocol of our TR-LDGS, we are faced with the following problem. Given a secretk which is shared among the players, generate a sharing of the reciprocal of k modulo q with no information revealed about k. Each player Pi holds a share f(i) which is a point on a t-degree polynomial f(x) with f(0)=k. To compute shares of k-1, we need n>4t, the n players run the reciprocal protocol [25] as follows:(i)
The players run theJRVSS; at the end, each player holds a share v(i) of a random secret v over a polynomial of degree t.(ii)
The players run themultiplication protocol and reconstruct the value ξ=kvmodq.(iii)
Finally each playerPi computes his share of the reciprocal as ξ-1v(i)modq, which is a share over a t-degree polynomial with its free term equals k-1modq.


## 5.1.1. Secret Sharing over a Prime Field

Lets∈Zq be a secret held by some dealer where Zq is a prime field. In order to share this secret among a set 𝒫={P1,…,Pn} of n>t players [37], the dealer, defines a polynomial f(x)=∑j=0tajxjmodq, he sets a0=s and each other coefficient aj≠0∈RZq. For all i=1,…,n, the dealer secretly delivers f(i) to player Pi. In the reconstruction phase, each player Pi broadcasts f(i), the players are able to compute s from any t+1 shares using Lagrange interpolation formula, s=f(0)=Σi∈ℬλif(i)modq, where ℬ⊂𝒫,|ℬ|=t+1, and λi is Lagrange coefficient for player Pi.


## 5.1.2. Verifiable Secret Sharing

Verifiable secret sharing (VSS) extends polynomial secret sharing in a way that allows the recipients of the shares to verify that their shares are consistent (i.e., that any subset oft+1 shares determines the same unique secret). Assuming n>2t, the protocol can tolerate malicious behaviors (e.g., illegal collaboration, sending wrong values, deleting values, etc.) of at most t players. We distinguish two different contributions of VSS; the conditionally secure VSS due to Feldman [38] and the unconditionally secure VSS due to Pedersen [39]. To achieve best security, both of them will be used in our protocol.Feldman's VSS
Two large primesp and q are chosen such that q∣p-1. The primes p and q and an element g∈Zp* of order q are published as the system public parameters. The dealer shares the secret s among the players on a t-degree polynomial f(x)=∑j=0tajxjmodq; the dealer also broadcasts the t+1 commitments cj=gajmodp for all j=0,…,t. These commitments allow each player Pi to verify the consistency of his share f(i) by checking that, gf(i)=∏j=0tcjijmodp. If this check fails for any share f(i), Pi broadcasts a complaint. If more than t players broadcasted a complaint, then at least one of them is honest and consequently the dealer is disqualified. Otherwise, the dealer reveals the share f(i) for each complaining player Pi, if the share is correct, Pi is disqualified, otherwise, if the share does not satisfy the commitments or if the dealer does not respond, the dealer is disqualified. During reconstruction of the secret, any player can check the validity of the share broadcasted by any other player via the published commitments to filter out bad shares and safely perform the interpolation. When it comes to the distributed generation of a secret key k and the joint computation of gkmodp, Feldman's VSS alone is not secure due to the attacks described in the security analysis section.Pedersen's VSS
The idea is to use double exponentiation which allows randomization. The public parameters arep,q,g, and h where p,q, and g are as in Feldman's VSS and h is another element in Zp* subject to the condition that loggh is unknown and assumed hard to compute. In addition to the polynomial f(x)=∑j=0tajxjmodq which holds the secret s as the free term, the dealer sets up a randomizing t-degree polynomial r(x)=∑j=0tbjxjmodq. He secretly delivers (f(i),r(i)) to player Pifor all i=1,…,n. The dealer also publishes the commitments cj=gajhbjmodpfor all j=0,…,t. Each player Pi verifies the consistency of his share f(i) by checking that gf(i)hr(i)=∏j=0tcjijmodp. If this check fails for any share f(i), Pi broadcasts a complaint. If more than t players broadcast a complaint, then at least one of them is honest and consequently the dealer is disqualified. Otherwise, the dealer reveals the pair (f(i),r(i)) for each complaining player Pi, if the pair is correct, Pi is disqualified, otherwise, if the pair does not satisfy the commitments or if the dealer does not respond, the dealer is disqualified. During reconstruction of the secret, any player can check the validity of the share broadcasted by any other player via the published commitments to filter out bad shares and safely perform the interpolation.


## 5.1.3. Joint Secret Sharing

Joint secret sharing allows the players to jointly share some secret among themselves without the help of the dealer.Joint Random Secret Sharing (JRSS)
JRSS [40] allows a set of n players to jointly share a random secret without the help of the dealer. Each player Pi∈𝒫 picks a random integer ki∈Zq and plays the role of the dealer to share ki among the players over a t-degree polynomial fi(x)=ki+∑j=1tajxjmodq. Each player Pi∈𝒫 simply sums the shares he receives from the other players to compute a share f(i)=∑j=1nfj(i) which is a point on a t-degree polynomial f(x) with its free term equals a random secret k=∑i=1nkimodq.Joint Random Verifiable Secret Sharing (JRVSS)
To withstand malicious behavior of at mostt<n/2 players during the JRSS, JRVSS combines the JRSS with Feldman's VSS for computational security or Pedersen's VSS for unconditional security. Simply, each player Pi∈𝒫 picks a random secret integer ki∈Zq and plays the role of the dealer in the VSS protocol to share this secret among the other players. Complaints are solved as in the VSS protocol. Finally, each player sums what he has to compute his share on a t-degree polynomial f(x) with its free term f(0)=∑i=1nkimodq.Joint Zero Secret Sharing (JZSS)
JZSS is a special case of the JRSS in which the random secret shared by each player is a zero. At the end of the JZSS, each player holds a sharef(i) on a t-degree polynomial f(x) with its free term f(0)=0.Joint Zero Verifiable Secret Sharing (JZVSS)
As in the JRVSS, to with stand malicious behavior of at mostt<n/2 players during the JZSS, JZVSS combines the JZSS with Feldman's VSS for computational security or Pedersen's VSS for unconditional security. Simply, each player Pi∈𝒫 plays the role of the dealer in the VSS protocol to share a zero among the other players. Complaints are solved as in the JRVSS protocol. Finally, each player sums what he has to compute his share on a t-degree polynomial f(x) with its free term f(0)=0. Notice that, from the published commitments, each player can verify that the shared secret is really a zero. This is true since the commitment to a zero will be g0=1.


## 5.1.4. The Multiplication Protocol

Given two secretsa and b shared over t-degree polynomials A(x) and B(x) respectively, the multiplication protocol [41] computes ξ=abmodq in a robust way with no information revealed about a or b. Each player Pi locally computes C(i)=A(i)B(i)modq. In this case, each C(i) is a share on a 2t-degree polynomial C(x)=A(x)B(x)modq with C(0)=ξ. However, publishing and interpolating the shares C(1),…,C(n) reveals information about A(x) and B(x) [21], consequently, randomizing the shares of C(x) is necessary. To randomize the shares of C(x) without changing C(0), the players run a JZVSS to share a zero over a 2t-degree polynomial R(x) with R(0)=0. Finally, each player P(i) computes and publishes D(i)=C(i)+R(i). The result ξ could be reached by interpolating the 2t-degree polynomial D(x) with the help of the Berlekamp-Welch decoding scheme [22] to filter out corrupted shares. Since we are interpolating a polynomial of degree deg=2t and we have a maximum of t malicious players (i.e., at most t possible faults), using the Berlekamp-Welch bound, the number of shares needed in order to correctly interpolate the polynomial is at least deg + 2faults + 1 = 4t+1. Hence, we need n>4t.


## 5.1.5. The Reciprocal Protocol

In the tracing protocol of our TR-LDGS, we are faced with the following problem. Given a secretk which is shared among the players, generate a sharing of the reciprocal of k modulo q with no information revealed about k. Each player Pi holds a share f(i) which is a point on a t-degree polynomial f(x) with f(0)=k. To compute shares of k-1, we need n>4t, the n players run the reciprocal protocol [25] as follows:(i)
The players run theJRVSS; at the end, each player holds a share v(i) of a random secret v over a polynomial of degree t.(ii)
The players run themultiplication protocol and reconstruct the value ξ=kvmodq.(iii)
Finally each playerPi computes his share of the reciprocal as ξ-1v(i)modq, which is a share over a t-degree polynomial with its free term equals k-1modq.


## 5.2. Proofs of Knowledge

In this subsection we describe the proof of knowledge tools used in building our TR-LDGS.


### 5.2.1. Proof of Knowledge of Discrete log

Letp and q be two large primes, where q∣p-1, and g is a generator. We review Schnorr's protocol [42] that allows a prover 𝒫 to prove to a verifier 𝒱 that he knows the Dlog of y to the base g modulo p. Let y=gxmodp, where x is 𝒫's secret. The protocol is as follows:(i)
𝒫→𝒱 picks r∈RZq, computes and sends A=gr.(ii)
𝒱→𝒫 picks and sends c∈RZq.(iii)
𝒫→𝒱 computes and sends s=r+cx.(iv)
𝒱 accepts if gs=tyc, else, rejects.We denote the above protocol byΠDlog←PDlog(g,y,x).


### 5.2.2. Proof of Equality of Two Discrete Logarithms

We review the protocol of [42, 43] that is believed to be a zero knowledge proof of equality of two discrete logarithms. In this protocol, the public parameters are two large primes p and q such that q∣p-1, two elements α,β∈Zp*, and the two quantities G1,G2∈Zp*. The prover (𝒫) proves to a verifier (𝒱) that he knows x∈Zq* such that G1=αxmodp and G2=βxmodp. The protocol is as follows:(i)
𝒫→𝒱: Choose r∈RZq* and send (A=αrmodp, B=βrmodp).(ii)
𝒱→𝒫:Choose c∈RZq* and send c.(iii)
𝒫→𝒱:Send y=r+cxmodq.(iv)
𝒱:Check that αy=AG1cmodp and βy=BG2cmodp.The standard method to convert the above protocol to a non-interactive protocol (we denote itΠLogEq←PLogEq(α,β,G1,G2,x) ) is by using a sufficiently strong hash function ℋ and setting c=ℋ(A,B). The protocol ΠLogEq becomes as follows:(i)
𝒫→𝒱: Choose r∈RZq* and send (A=αrmodp, B=βrmodp, c=ℋ(A,B) and y=r+cxmodq).(ii)
𝒱: Check that αy=AG1cmodp and βy=BG2cmodp.


### 5.2.3. Proof of Existence of Discrete log Equality

Letyi=αximodp for i=1,…,n, and let z=βximodp for some i∈{1,…,n}. A prover 𝒫 demonstrates to a verifier 𝒱 that he knows one of the logarithms of yi (i∈{1,…,n}) to the base α and that logαyi=logβzmodq without revealing which i. Let wlog the relation holds for i=1 (i.e., x1=logαy1=logβzmodq). The protocol is as follows [29]:(i)
𝒫→𝒱:Choose ki∈RZq* for i=1,…,n, cj∈RZq* for j=2,…,n and compute
(a)
r1=αk1modp, ri=αkiyi-cimodp for i=2,…,n,(b)
t1=βk1modp, ti=βkiz-cimodp for i=2,…,n.Send the values(r1,…,rn,t1,…,tn).(ii)
𝒱→𝒫:Choose and send c∈RZq*.(iii)
𝒫→𝒱:Calculate c1=c-∑i=2ncimodq, s1=x1c1+k1modq, and set si=ki for i=2,…,n. Send (c1,…,cn,s1,…,sn).(iiii)
𝒱:Check that c=∑i=1nci and that for all i=1,…,n:αsi=yicirimodp and βsi=zcitimodp.The above interactive proof can be transformed into a non-interactive proof that we will denote it by:(1)∏∃LogEq⟵P∃LogEq(α,β,y1,…,yn,z)
using a strong hash function ℋ. This can be done by setting(2)c=ℋ(y1,…,yn,α,z,β,αs1y1-c1,…,αsnyn-cn,βs1z-c1,…,βsnz-cn).


## 5.2.1. Proof of Knowledge of Discrete log

Letp and q be two large primes, where q∣p-1, and g is a generator. We review Schnorr's protocol [42] that allows a prover 𝒫 to prove to a verifier 𝒱 that he knows the Dlog of y to the base g modulo p. Let y=gxmodp, where x is 𝒫's secret. The protocol is as follows:(i)
𝒫→𝒱 picks r∈RZq, computes and sends A=gr.(ii)
𝒱→𝒫 picks and sends c∈RZq.(iii)
𝒫→𝒱 computes and sends s=r+cx.(iv)
𝒱 accepts if gs=tyc, else, rejects.We denote the above protocol byΠDlog←PDlog(g,y,x).


## 5.2.2. Proof of Equality of Two Discrete Logarithms

We review the protocol of [42, 43] that is believed to be a zero knowledge proof of equality of two discrete logarithms. In this protocol, the public parameters are two large primes p and q such that q∣p-1, two elements α,β∈Zp*, and the two quantities G1,G2∈Zp*. The prover (𝒫) proves to a verifier (𝒱) that he knows x∈Zq* such that G1=αxmodp and G2=βxmodp. The protocol is as follows:(i)
𝒫→𝒱: Choose r∈RZq* and send (A=αrmodp, B=βrmodp).(ii)
𝒱→𝒫:Choose c∈RZq* and send c.(iii)
𝒫→𝒱:Send y=r+cxmodq.(iv)
𝒱:Check that αy=AG1cmodp and βy=BG2cmodp.The standard method to convert the above protocol to a non-interactive protocol (we denote itΠLogEq←PLogEq(α,β,G1,G2,x) ) is by using a sufficiently strong hash function ℋ and setting c=ℋ(A,B). The protocol ΠLogEq becomes as follows:(i)
𝒫→𝒱: Choose r∈RZq* and send (A=αrmodp, B=βrmodp, c=ℋ(A,B) and y=r+cxmodq).(ii)
𝒱: Check that αy=AG1cmodp and βy=BG2cmodp.


## 5.2.3. Proof of Existence of Discrete log Equality

Letyi=αximodp for i=1,…,n, and let z=βximodp for some i∈{1,…,n}. A prover 𝒫 demonstrates to a verifier 𝒱 that he knows one of the logarithms of yi (i∈{1,…,n}) to the base α and that logαyi=logβzmodq without revealing which i. Let wlog the relation holds for i=1 (i.e., x1=logαy1=logβzmodq). The protocol is as follows [29]:(i)
𝒫→𝒱:Choose ki∈RZq* for i=1,…,n, cj∈RZq* for j=2,…,n and compute
(a)
r1=αk1modp, ri=αkiyi-cimodp for i=2,…,n,(b)
t1=βk1modp, ti=βkiz-cimodp for i=2,…,n.Send the values(r1,…,rn,t1,…,tn).(ii)
𝒱→𝒫:Choose and send c∈RZq*.(iii)
𝒫→𝒱:Calculate c1=c-∑i=2ncimodq, s1=x1c1+k1modq, and set si=ki for i=2,…,n. Send (c1,…,cn,s1,…,sn).(iiii)
𝒱:Check that c=∑i=1nci and that for all i=1,…,n:αsi=yicirimodp and βsi=zcitimodp.The above interactive proof can be transformed into a non-interactive proof that we will denote it by:(1)∏∃LogEq⟵P∃LogEq(α,β,y1,…,yn,z)
using a strong hash function ℋ. This can be done by setting(2)c=ℋ(y1,…,yn,α,z,β,αs1y1-c1,…,αsnyn-cn,βs1z-c1,…,βsnz-cn).


## 5.3. El-Gamal Cryptosystem

Achieving the confidentiality service in our secure VANET system relies on the El-Gamal cryptosystem [44]. It is known that the El-Gamal cryptosystem works for any family of groups for which the discrete logarithm is considered intractable. Part of the security of the scheme actually relies on the Diffie-Hellman assumption, which implies the hardness of computing discrete logarithms modulo of a large prime. We will present our results for subgroups Gq of order q of Zp*, where p and q are large primes such that q∣p-1. Other practical families can be obtained for elliptic curves over finite fields. We will now briefly describe the El-Gamal cryptosystem, where the primes p and q and at least one generator g of Gq are treated as system public parameters. The key pair of a receiver in the El-Gamal cryptosystem consists of a private key s (randomly chosen by the receiver) and the corresponding public key h=gs. Given a message m∈Zp, encryption proceeds as follows. The sender chooses a random r∈Zq, and sends the pair (A,B)=(gr,hrm) as the ciphertext to the receiving party. To decrypt the ciphertext (A,B) the receiver recovers the plaintext as m=B/As, using the private key s. The El-Gamal encryption is known to be a CPA-secure cryptosystem, there exist extensions to this cryptosystem that achieve CCA1 and CCA2 security.


## 6. Detailed Protocol Description

Given a security parameterκ, our system works in subgroups Gq of order q of Zp*, where p and q are large primes where q∣p-1. Other practical families could be obtained from Elliptic curves over finite fields. The primes p and q and a generator g of Gq are the system global parameters. In number theory, a generator g is picked as follows: let p=μq+1, select α∈RZp* and α≠1, if (β=αμmodp≠1) then β is a valid generator g of order q since in this case gqmodp=1. If β=1 (with very low probability), repeat for another α.Each OBU is assumed to come with the unique pair(x,gx), where x∈RZq* of bit-length κ is the OBU's private key and gx is the OBU's identity id.


### 6.1. Setup Protocol by the TAs

Protocol Setup-TA
The set of tracing authorities𝒯𝒜={TA1,…,TAn} join together to compute shares of a random integer k∈Zq of bit-length κ as follows: (i)
Run aJRVSS with Pedersen's VSS as the VSS in place. At the end, each authority TAi holds a share K(i) of a random secret k∈RZq* over a t-degree polynomial K(x) with K(0)=k.(ii)
The authorities that are not disqualified in the JRVSS in the previous step broadcast the commitments to their shared polynomial based on Feldman's VSS. More precisely, ifKi(x)=ki+∑j=1taj is the polynomial of authority TAi then TAi broadcasts gki and gajmodpfor all j=1,…,t.(iii)
For any authorityTAi who receives at least one valid complaint in the previous step, the other authorities join to reconstruct his polynomial Ki(x) and values gki and gajmodpfor all j=1,…,t in the clear.(iv)
Finally, the remaining good authorities join to safely computegk=∏i=1ngkimodp.At this point, the tracing authorities share the tracing trapdoor parameter k over a t-degree polynomial and have jointly computed the blinded tracing trapdoor, bk=gkmodp. They publicize bk (to the RSU's and the security center SC). As a preparation for the tracing protocol, the TAs need to compute shares of k-1modq, so they proceedas follows(v)
The TA's run thereciprocal protocol, at the end, each TAi holds a share D(i) on a t-degree polynomial, D(x) with its free term D(0)=k-1modq.(vi)
Each TA broadcasts Feldman's VSS commitments (i.e., to the baseg) of all her chosen random polynomials during the reciprocal protocol. These commitments allow the TAs to validate the quantities Vi=gD(i)modp for all i.The setup-TA protocol ends with each tracing authority TAiholding a pair of shares 〈K(i),D(i)〉, where K(i) is a share of the tracing trapdoor parameter k on a t-degree polynomial K(x) while D(i) is a share of the reciprocal of the tracing trapdoor parameter k-1 on a t-degree polynomial D(x). Notice that, after the computation of the blinded tracing trapdoor parameter bk, the set of shares 〈K(1),…,K(n)〉 of k and the commitments 〈W1,…,Wn〉 where Wi=gK(i), become useless and could be erased. Each TAi∈𝒯𝒜 holds (and preserves) (i)
A shareD(i) of k-1,(ii)
The tuple〈V1,…,Vn〉 as commitments to the shares 〈D(1),…,D(n)〉 where Vi=gD(i).


### 6.2. Registration of OBUs

Protocol Reg-OBU
The SC interacts with each OBU as follows:(i)
On the arrival of an OBU, the SC queries this OBU for its unique identityid.(ii)
The OBU sends its identityid and a proof, ΠDlog←P(g,id,x), that it knows loggid.(iii)
The SC runs algorithmVDlog(g,id,ΠDlog) to verify the validity of id. If not successful, then rejects this id, else, accepts the id and proceed.(iv)
The SC forwards the accepted identity to all RSUs. Notice that each OBU is able to locally compute its own blinded identity as  bid=bkx which is idk.


### 6.3. OBU-RSU Communication

For an OBU to send a signed messagem to an RSU, the OBU proceeds as follows:(i)
hashesm as h=H(m,r) for a random string r,(ii)
computess=hx,(iii)
preparesΠLogEq←PLogEq(bk,h,bid,s,x) as a proof that logbkbid=loghs,(iv)
preparesΠ∃LogEq←P∃LogEq(bk,g,bid,ℐ𝒟,x) as an or-proof that there exists one of the m identities id∈ℐ𝒟 such that logbkbid=loggid.For an OBU to be able to prepareΠ∃LogEq, it must know all the registered identities. This is easily achieved by allowing each RSU to periodically broadcasts the set ℐ𝒟. Finally the OBU prepares the message to be transmitted as the tuple: 〈bid,m,r,hx,ΠLogEq,Π∃LogEq〉.


### 6.4. Direct OBU to OBU Communications

Direct OBU to OBU anonymous and authenticated communication is possible under the assumption that the RSU in range periodically broadcasts the setℐ𝒟 of the registered OBUs. Two OBUs may communicate using their blinded identities and as in the RSU-OBU communication, each OBU includes a prove of knowledge Π∃LogEq to proof to the other OBU that its identity belongs to the group of registered identities and a proof of knowledge ΠLogEq that the signature on a transmitted message is valid. Moreover, two OBUs may use their blinded identities as an El-Gamal public key to start confidential session in the same way as in the RSU-OBU communication (see Section 9).


### 6.5. Tracing Protocol by the TAs

Protocol Trace-id
Under a court order to trace an identity corresponding to a particular blinded-identitybid, bid is given as an input to all the tracing authorities 𝒯𝒜. They join together to reveal the identity id. Each authority TAi∈𝒯𝒜 performs as follows: (i)
broadcastsYi=(bid)D(i)modp, where D(i) is TAi's share of k-1modq,(ii)
broadcastsΠLogEq←PLogEq(g,bid,Vi,Yi,D(i)) to prove that loggVi=logbidYimodq, From any t+1 quantities, Yi's, that pass the proof ΠLogEq successfully, interpolation in the exponent is performed to compute (bid)1/k=id. Interpolation in the exponent is as simple as computing
(3)∏i∈ℬ(bid)D(i)λi=(bid)∑i∈ℬD(i)λi=(bid)k-1=id,
where |ℬ|=t+1, and λi is Lagrangian coefficient of authority TAi.


### 6.6. OBU Revocation

The revocation of an OBU is very simple, to revoke an identityid (after being traced), the security center simply instructs the RSUs to remove this identity from the set ℐ𝒟, consequently, the proof Π∃LogEq attached to a message of a revoked OBU will fail and the messages from this OBU will not be accepted by the RSU.


## 6.1. Setup Protocol by the TAs

Protocol Setup-TA
The set of tracing authorities𝒯𝒜={TA1,…,TAn} join together to compute shares of a random integer k∈Zq of bit-length κ as follows: (i)
Run aJRVSS with Pedersen's VSS as the VSS in place. At the end, each authority TAi holds a share K(i) of a random secret k∈RZq* over a t-degree polynomial K(x) with K(0)=k.(ii)
The authorities that are not disqualified in the JRVSS in the previous step broadcast the commitments to their shared polynomial based on Feldman's VSS. More precisely, ifKi(x)=ki+∑j=1taj is the polynomial of authority TAi then TAi broadcasts gki and gajmodpfor all j=1,…,t.(iii)
For any authorityTAi who receives at least one valid complaint in the previous step, the other authorities join to reconstruct his polynomial Ki(x) and values gki and gajmodpfor all j=1,…,t in the clear.(iv)
Finally, the remaining good authorities join to safely computegk=∏i=1ngkimodp.At this point, the tracing authorities share the tracing trapdoor parameter k over a t-degree polynomial and have jointly computed the blinded tracing trapdoor, bk=gkmodp. They publicize bk (to the RSU's and the security center SC). As a preparation for the tracing protocol, the TAs need to compute shares of k-1modq, so they proceedas follows(v)
The TA's run thereciprocal protocol, at the end, each TAi holds a share D(i) on a t-degree polynomial, D(x) with its free term D(0)=k-1modq.(vi)
Each TA broadcasts Feldman's VSS commitments (i.e., to the baseg) of all her chosen random polynomials during the reciprocal protocol. These commitments allow the TAs to validate the quantities Vi=gD(i)modp for all i.The setup-TA protocol ends with each tracing authority TAiholding a pair of shares 〈K(i),D(i)〉, where K(i) is a share of the tracing trapdoor parameter k on a t-degree polynomial K(x) while D(i) is a share of the reciprocal of the tracing trapdoor parameter k-1 on a t-degree polynomial D(x). Notice that, after the computation of the blinded tracing trapdoor parameter bk, the set of shares 〈K(1),…,K(n)〉 of k and the commitments 〈W1,…,Wn〉 where Wi=gK(i), become useless and could be erased. Each TAi∈𝒯𝒜 holds (and preserves) (i)
A shareD(i) of k-1,(ii)
The tuple〈V1,…,Vn〉 as commitments to the shares 〈D(1),…,D(n)〉 where Vi=gD(i).


## 6.2. Registration of OBUs

Protocol Reg-OBU
The SC interacts with each OBU as follows:(i)
On the arrival of an OBU, the SC queries this OBU for its unique identityid.(ii)
The OBU sends its identityid and a proof, ΠDlog←P(g,id,x), that it knows loggid.(iii)
The SC runs algorithmVDlog(g,id,ΠDlog) to verify the validity of id. If not successful, then rejects this id, else, accepts the id and proceed.(iv)
The SC forwards the accepted identity to all RSUs. Notice that each OBU is able to locally compute its own blinded identity as  bid=bkx which is idk.


## 6.3. OBU-RSU Communication

For an OBU to send a signed messagem to an RSU, the OBU proceeds as follows:(i)
hashesm as h=H(m,r) for a random string r,(ii)
computess=hx,(iii)
preparesΠLogEq←PLogEq(bk,h,bid,s,x) as a proof that logbkbid=loghs,(iv)
preparesΠ∃LogEq←P∃LogEq(bk,g,bid,ℐ𝒟,x) as an or-proof that there exists one of the m identities id∈ℐ𝒟 such that logbkbid=loggid.For an OBU to be able to prepareΠ∃LogEq, it must know all the registered identities. This is easily achieved by allowing each RSU to periodically broadcasts the set ℐ𝒟. Finally the OBU prepares the message to be transmitted as the tuple: 〈bid,m,r,hx,ΠLogEq,Π∃LogEq〉.


## 6.4. Direct OBU to OBU Communications

Direct OBU to OBU anonymous and authenticated communication is possible under the assumption that the RSU in range periodically broadcasts the setℐ𝒟 of the registered OBUs. Two OBUs may communicate using their blinded identities and as in the RSU-OBU communication, each OBU includes a prove of knowledge Π∃LogEq to proof to the other OBU that its identity belongs to the group of registered identities and a proof of knowledge ΠLogEq that the signature on a transmitted message is valid. Moreover, two OBUs may use their blinded identities as an El-Gamal public key to start confidential session in the same way as in the RSU-OBU communication (see Section 9).


## 6.5. Tracing Protocol by the TAs

Protocol Trace-id
Under a court order to trace an identity corresponding to a particular blinded-identitybid, bid is given as an input to all the tracing authorities 𝒯𝒜. They join together to reveal the identity id. Each authority TAi∈𝒯𝒜 performs as follows: (i)
broadcastsYi=(bid)D(i)modp, where D(i) is TAi's share of k-1modq,(ii)
broadcastsΠLogEq←PLogEq(g,bid,Vi,Yi,D(i)) to prove that loggVi=logbidYimodq, From any t+1 quantities, Yi's, that pass the proof ΠLogEq successfully, interpolation in the exponent is performed to compute (bid)1/k=id. Interpolation in the exponent is as simple as computing
(3)∏i∈ℬ(bid)D(i)λi=(bid)∑i∈ℬD(i)λi=(bid)k-1=id,
where |ℬ|=t+1, and λi is Lagrangian coefficient of authority TAi.


## 6.6. OBU Revocation

The revocation of an OBU is very simple, to revoke an identityid (after being traced), the security center simply instructs the RSUs to remove this identity from the set ℐ𝒟, consequently, the proof Π∃LogEq attached to a message of a revoked OBU will fail and the messages from this OBU will not be accepted by the RSU.


## 7. Security Analysis

Setup and Trace Protocol
We first consider the tracing authorities (the setup and trace protocols). The tracing trapdoor parameter is a random, uniformly distributed valuek which is distributed on a threshold basis and the value bk=gk is made public. The protocol is called t-secure, that is, in the presence of at most t malicious authorities:
(i)
Correctness.
(a)
All subsets oft+1 valid shares reconstruct to the same unique secret parameter k.(b)
Each authority is able to compute the common public valuebk=gk.(c)
k is uniformly distributed in Zq and hence, bk is uniformly distributed in the subgroup generated by g.(ii)
Secrecy. No information on k can be learned by the coalition of at most t members except for what is implied by the value bk=gk.
In the trace protocol, the inverse of the tracing trapdoor parameter k-1 is also distributed on a threshold basis where, whenever there is a legal reason, the value bidk-1=id is jointly computed and delivered to the court. The security of the trace protocol (correctness and secrecy) is similar to the setup protocol.
JRVSS with Feldman's VSS alone is insecure, since malicious authorities can influence the distribution of the result of Feldman's VSS to a non-uniform distribution. More precisely, the attack works as follows: assume that two malicious authorities (sayTA1 and TA2) want to bias the distribution towards values bk whose last bit is 0. TA1 gives authorities TA3,…,TAt+2 shares which are inconsistent with his broadcast values, the rest of the authorities receive consistent shares. Thus, there will be t complaints against TA1, yet t complaints are not enough for disqualification. The traitors compute α=∑i=1ngki and β=∑i=2ngki (where ki=λiK(i)). If α ends with 0 then TA1 will do nothing and continue the protocol as written. If α ends with 1 then it will force the disqualification of TA1, this is achieved by asking TA2 to also broadcast a complaint against TA1, which brings the number of complaints to t+1. This action sets the public value bk to β which ends with 0 with probability 1/2. Thus effectively the traitors authorities have forced strings ending in 0 to appear with probability 3/4 rather than 1/2. One must notice that synchronous broadcast does not prevent such attack to take place. Hence, the third requirement for correctness and the secrecy requirement dramatically fail. In Pedersen's VSS, the view of the authorities is independent of the value of the secret k. One may refer to [24, 30] for more details and simulation.RSU-OBU Communication Security
During communication, when the RSU (verifier) receives a signed message from anOBUi (signer) for the first time, the signer must prove that the included blinded-identity (bidi) is valid (i.e., related to an identity in the set of identities ℐ𝒟 held by the RSUs), hence, the signer OBUi includes the proof Π∃LogEq which proves to an RSU that the included bidi corresponds to some idi∈ℐ𝒟 with no information revealed about which index i and hence the correspondence of bidi to idi is still unknown to an RSU. However, Π∃LogEq does not ensure that the exponent of s=hxi is consistent with the exponent of bidi=bkxi. To do so, the OBUi must include a proof ΠLogEq which ensures to the RSU that the exponents are equal, or else, the message is rejected. Notice that the proof Π∃LogEq is included only in the first message transmitted from the OBUi, once bidi is verified by the RSU as correct and registered, the RSU stores this bidi and the proof Π∃LogEq is omitted from subsequent messages in this session. we emphasize that, the proof ΠLogEq must be included within each transmitted message.Secrecy against SC
We assumed that the SC is honest-but-curious which means that the SC does not behave maliciously, yet, it may misuse any information falls in its hands. From the description of our protocol, the SC interacts with an OBU only once during registration where the OBU sends the clear identityid=gx. Assuming DHP is infeasible, the SC gains no information in the cryptographic sense about the private parameter x. The proof of knowledge of discrete log P(g,id,x) reveals no information about the private parameter x. It is important to notice that nobody is able to compute the blinded identity bid of any OBU except the OBU itself, this follows from CDHP where it is infeasible to compute bid=gxk given id=gx and bk=gk, and consequently, nobody is able to detect the correspondence of any id to its bid except the OBU itself (of course, unless the tracing protocol is run). Since the blinded identity bid=bkx=gkx is computed by an OBU in the absence of the SC, given the tuple 〈id=gx,bid=bkx,bid′=bkx'〉 where g and bk are known to SC, it is infeasible for an SC to decide on the equality of the exponents (better than a random coin flip) and hence cannot construct a correct mapping. Even if an SC eavesdrops on the channel between the OBU and an RSU, the security of the proof of existence of discrete-log equality Π∃LogEq does not help it to construct such mapping. In case an SC communicates with an RSU, notice that this communication is one-way, that is, the SC receives nothing from the RSU, it only sends a new registered id or a revoked id.TAs Communication Channels
We assumed (as in the standard settings of verifiable threshold secret sharing schemes) that the TAs are fully connected via private and authenticated channels. Authentication and privacy are achieved using public-key infrastructure where each authority has her own certified private/public key pair. Although such assumption (regardless of the complexities associated with PKIs, such as scalability) is accepted in the theory of threshold cryptography, an important question arises “Who certifies the public-keys of the authorities?” The direct answer of course is “a root CA” and here comes our argument: by this direct answer, we return back to violate the anonymity service which is the main service we are solving in this paper since we still give full trust to a single authority. In this context, we provide two solutions to solve this problem. The first solution is to avoid using PKIs at all. Each authority registers her public-key with every other authority in the set, and this registration must be performed off-line to avoid man-in-the-middle attacks (i.e., the authorities must meet personally before the setup protocol). This solution if combined with the advances in the field of forward secure signatures (please see Section 9.3) does not add much complexities to our protocol but requires some extra presetup work. The second solution is to recall the work in [45] where a provably secure construction is given for secure multiparty computation (with meaningful level of security) without authentication among the parties and hence no need for authenticated channels. However, the computations and communications complexities of the protocol become very high and almost unbearable by many networks.


## 8. Efficiency Considerations

In this section we discuss some issues concerning the efficiency of our VANET system.


### 8.1. Adaptive Anonymity

As one may notice the highest computation and communication complexity is during the setup-TA and trace-id protocol, yet, the setup-TA protocol is run only once to setup a tracing trapdoor parameter while the trace-id protocol is run only to trace an identity which is not supposed to be done frequently. A serious complexity issue is the amount of computations performed by an OBU and the bandwidth required for transmission. The quantity that most affects the efficiency of transmission isΠ∃LogEq since the computation of this quantity and the bandwidth is proportional to the number of registered identities in the system. For a huge population, the computation and the verification of this quantity become a serious burden on both the OBU and the RSU (specially the OBU). Hence, we introduce the idea of adaptive anonymity, in which, the level of anonymity (that could be selected by the OBU) ranges from zero-anonymous to n-anonymous where n is the number of registered identities. The OBU, according to its available resources, could select any level of anonymity it desires. Zero-anonymous transmission means that an OBU may select to disable anonymity and instead of attaching its blinded-identity to the message, it attaches its identity in the clear and consequently, the quantity Π∃LogEq becomes obsolete. For nonzero-anonymous transmission, the level of anonymity may be selected adaptively as follows: The OBU picks 1<ℓ≤N as its selected anonymity level, where N is the number of registered identities. Let id=gx be the identity of this particular OBU while bid is its blinded-identity. Next, the OBU picks a subset ℬ⊆ℐ𝒟 where |ℬ|=ℓ and id∈ℬ. Then, the OBU generates the proof Π∃LogEq←P∃LogEq(bk,g,bid,ℬ,x) and prepares the message to be transmitted as the tuple:
(4)〈bid,m,r,hx,ΠLogEq,Π∃LogEq,ℬ〉.The complexity (computations and bandwidth) of the transmission is now proportional to the anonymity levelℓ and hence, the adaptive anonymity approach provides a complexity-anonymity tradeoff.


### 8.2. On the Number of Tracing Authorities

We have described our protocol assuming a high level of security against a corruptive adversary that may corrupt (completely masquerades) a minority (at mostt) of the authorities and consequently the number of authorities is required to be at least 4t+1. However, in many circumstances (depending on the network environment) a corruption of an authority is ensured to be impossible and hence, all authorities are assumed honest-but-curious (equivalently, the adversary has only eavesdropping and halting capabilities), in this case, the lower bound on the number of authorities may be reduced to 3t+1 where 2t+1 authorities perform the computations while t of them may be disconnected at any time without disrupting the correct output. Moreover, there is no need for verifiable secret sharing (i.e., Feldmann's and Pedersen's VSS become obsolete), only JRSS and JZSS are incorporated without the need for verifiability and hence, the computations complexity and bandwidth are significantly reduced. Furthermore, if an adversary has only eavesdropping capabilities without being able to halt an authority, all authorities are assumed online and active all the time, consequently, we may reduce the number of authorities by t, hence becomes only 2t+1 where the adversary is able to eavesdrop no more than t of them.


## 8.1. Adaptive Anonymity

As one may notice the highest computation and communication complexity is during the setup-TA and trace-id protocol, yet, the setup-TA protocol is run only once to setup a tracing trapdoor parameter while the trace-id protocol is run only to trace an identity which is not supposed to be done frequently. A serious complexity issue is the amount of computations performed by an OBU and the bandwidth required for transmission. The quantity that most affects the efficiency of transmission isΠ∃LogEq since the computation of this quantity and the bandwidth is proportional to the number of registered identities in the system. For a huge population, the computation and the verification of this quantity become a serious burden on both the OBU and the RSU (specially the OBU). Hence, we introduce the idea of adaptive anonymity, in which, the level of anonymity (that could be selected by the OBU) ranges from zero-anonymous to n-anonymous where n is the number of registered identities. The OBU, according to its available resources, could select any level of anonymity it desires. Zero-anonymous transmission means that an OBU may select to disable anonymity and instead of attaching its blinded-identity to the message, it attaches its identity in the clear and consequently, the quantity Π∃LogEq becomes obsolete. For nonzero-anonymous transmission, the level of anonymity may be selected adaptively as follows: The OBU picks 1<ℓ≤N as its selected anonymity level, where N is the number of registered identities. Let id=gx be the identity of this particular OBU while bid is its blinded-identity. Next, the OBU picks a subset ℬ⊆ℐ𝒟 where |ℬ|=ℓ and id∈ℬ. Then, the OBU generates the proof Π∃LogEq←P∃LogEq(bk,g,bid,ℬ,x) and prepares the message to be transmitted as the tuple:
(4)〈bid,m,r,hx,ΠLogEq,Π∃LogEq,ℬ〉.The complexity (computations and bandwidth) of the transmission is now proportional to the anonymity levelℓ and hence, the adaptive anonymity approach provides a complexity-anonymity tradeoff.


## 8.2. On the Number of Tracing Authorities

We have described our protocol assuming a high level of security against a corruptive adversary that may corrupt (completely masquerades) a minority (at mostt) of the authorities and consequently the number of authorities is required to be at least 4t+1. However, in many circumstances (depending on the network environment) a corruption of an authority is ensured to be impossible and hence, all authorities are assumed honest-but-curious (equivalently, the adversary has only eavesdropping and halting capabilities), in this case, the lower bound on the number of authorities may be reduced to 3t+1 where 2t+1 authorities perform the computations while t of them may be disconnected at any time without disrupting the correct output. Moreover, there is no need for verifiable secret sharing (i.e., Feldmann's and Pedersen's VSS become obsolete), only JRSS and JZSS are incorporated without the need for verifiability and hence, the computations complexity and bandwidth are significantly reduced. Furthermore, if an adversary has only eavesdropping capabilities without being able to halt an authority, all authorities are assumed online and active all the time, consequently, we may reduce the number of authorities by t, hence becomes only 2t+1 where the adversary is able to eavesdrop no more than t of them.


## 9. Other Security Services

In this section we discuss other security services and enhancements that could be provided by our VANET system.


### 9.1. Confidential Communications

Until now, we were only considering authenticated (and nonrepudiable) transmission from an OBU to an RSU and vice versa. Now we turn our attention to the confidentiality service. First, we need to show why confidential transmission is necessary, since if the transmission is anonymous and the identity of the message originator is unknown, then there is no strong reason to consider confidential transmission. Yet, there is still a strong reason for this service: consider the situation where a particular OBU is revoked. We have already shown that an RSU will not accept messages from a revoked OBU, but, what about messages transmitted from an RSU? Since this OBU is revoked, it must not accept any service messages from the RSU (unless the information included in the transmitted message is for free) or else we assume the service is still running for this OBU. Nothing prevents the OBU from accepting messages from an RSU since these messages are sent in the clear. In the context of this scenario, confidential transmission is necessary to be realized. Our goal in this section is to realize this service while maintaining anonymity, the possibility of tracing identities and all the other system attributes. Our idea is that the RSU replies to an OBU using the OBU's blinded-identity as its public key for an El-Gamal cryptosystem wherebk is the generator for the system, this requires spending a little more time in the TA-setup phase to test and ensure that bk is also a generator. Simply, bk is a generator if (bk)q=1modp. More precisely, the RSU performs as follows:(i)
on the reception of a signed message (or request) from an OBU, it checks the validity of the attached blinded-identitybid as before,(ii)
picks a random session-keyKs for any available symmetric cryptosystem,(iii)
prepares an El-Gamal encryption of this session-key usingbid as the public key. The ciphertext is the pair 〈A,B〉 where A=bkr and B=bidrKs,(iv)
generates the ciphertextC=EKs(m) for a message m,(v)
sends the tuple〈A,B,C,bid〉 as a hybrid encryption of the message m.Only the OBU that knows the private keyx corresponding to this particular blinded-identity will be able to decrypt the message m. The OBU decrypts for Ks=B/Ax and decrypts C for m. Moreover, this session-key may be used between The RSU and the OBU as an established private session.


### 9.2. Proactive Security

In(t,n)-threshold, secret sharing schemes security is assured if throughout the entire lifetime of the secret, it is assumed that the adversary is restricted to compromise at most t of the n locations. For long-lived and sensitive secrets (tracing trapdoor parameter k in our system), this assumption about the adversary may be insufficient since the adversary may behave in a mobile manner, that is, she jumps among the authorities collecting as much information as she can. She has the whole life-time of the secret to do so. An easy strategy is to periodically refresh the secret parameter itself by reinitializing the setup phase which leads to a fresh k and hence a fresh blinded tracing trapdoor parameter bk and erasing all previous versions. However, such an attempt disables traceability of blinded identities generated using previous versions of bk and hence such a strategy becomes insecure.Therefore, what is actually required to protect the secrecy of the tracing trapdoor parameterk is to be able to periodically renew its shares without changing its value in such a way that any information learned by the adversary about individual shares becomes obsolete after the shares are renewed. Similarly to avoid the gradual destruction of the information by corruption of shares it is necessary to periodically recover lost or corrupted shares without compromising the secrecy of any of the shares [46].Proactive secret sharing is mainly based on the(+,+)-homomorphic property of polynomial secret sharing and secure computations in the exponent of Feldman's VSS. The life-time of the secret is divided into time periods. The time period must be small enough to ensure that the adversary will not exceed the threshold t in her attack during any period, and big enough to reduce complexity to the minimum. At the beginning of every time period, the update of shares is triggered and it consists of the following stages (please refer to [46] for more details):(1)
update of personal private/public keys,(2)
detection of lost or corrupted shares,(3)
verifiable shares renewal,(4)
erasure of old shares.Here we must emphasize that the erasure of previous versions of shares and private keys is a must and all parties (except the malicious minority) must be honest about erasing their old parameters; since we are working in the static adversary model, the proactive VANET system is secure only in the erasure model.


### 9.3. Forward Security

Since for proactive security to be effective in protecting the tracing trapdoor parameter and since we assume static adversary model, all authorities must erase their past information after shares update. Since all private and authenticated communications among the authorities are performed using private/public keys. An adversary may target these private keys so that she is able to decrypt and recover past ciphertexts that she may have recorded on the channels. Here, we recall the advances in forward-secure cryptography. The goal of forward-secure cryptosystems is to provide the benefits of frequent rekeying without incurring the costs of changing public keys (and associated overhead). They enable the user to frequently erase the secret key while maintaining the same public key. The notion of a forward-security originated from the notion of “perfect forward secrecy” for key agreement, which protects (locks-down) past traffic even after long-term keys are compromised.A generic forward-secure signature scheme is constructed from any ordinary (non-forward-secure) scheme used as a black-box [47]. The security of the forward-secure scheme is then reduced to the security of the underlying ordinary scheme (i.e., if some adversary can efficiently compromise the forward-secure scheme, then we can construct an adversary compromising the security of the underlying ordinary scheme). The efficiency of a generic scheme is usually measured in terms of the number of the invocations of the underlying ordinary scheme, the number of the ordinary keys, and so forth.Forward-secure public key encryption proved harder to achieve, and the first and so far the only result in that area was obtained in [48]. The constructions share similarities with previous tree-based, forward-secure signature schemes. In the construction, however, time periods are associated with all the nodes of the tree (in a preorder traversal) instead of associating time periods with the leaves only; this improves the efficiency of the key-generation and key-update algorithms.


## 9.1. Confidential Communications

Until now, we were only considering authenticated (and nonrepudiable) transmission from an OBU to an RSU and vice versa. Now we turn our attention to the confidentiality service. First, we need to show why confidential transmission is necessary, since if the transmission is anonymous and the identity of the message originator is unknown, then there is no strong reason to consider confidential transmission. Yet, there is still a strong reason for this service: consider the situation where a particular OBU is revoked. We have already shown that an RSU will not accept messages from a revoked OBU, but, what about messages transmitted from an RSU? Since this OBU is revoked, it must not accept any service messages from the RSU (unless the information included in the transmitted message is for free) or else we assume the service is still running for this OBU. Nothing prevents the OBU from accepting messages from an RSU since these messages are sent in the clear. In the context of this scenario, confidential transmission is necessary to be realized. Our goal in this section is to realize this service while maintaining anonymity, the possibility of tracing identities and all the other system attributes. Our idea is that the RSU replies to an OBU using the OBU's blinded-identity as its public key for an El-Gamal cryptosystem wherebk is the generator for the system, this requires spending a little more time in the TA-setup phase to test and ensure that bk is also a generator. Simply, bk is a generator if (bk)q=1modp. More precisely, the RSU performs as follows:(i)
on the reception of a signed message (or request) from an OBU, it checks the validity of the attached blinded-identitybid as before,(ii)
picks a random session-keyKs for any available symmetric cryptosystem,(iii)
prepares an El-Gamal encryption of this session-key usingbid as the public key. The ciphertext is the pair 〈A,B〉 where A=bkr and B=bidrKs,(iv)
generates the ciphertextC=EKs(m) for a message m,(v)
sends the tuple〈A,B,C,bid〉 as a hybrid encryption of the message m.Only the OBU that knows the private keyx corresponding to this particular blinded-identity will be able to decrypt the message m. The OBU decrypts for Ks=B/Ax and decrypts C for m. Moreover, this session-key may be used between The RSU and the OBU as an established private session.


## 9.2. Proactive Security

In(t,n)-threshold, secret sharing schemes security is assured if throughout the entire lifetime of the secret, it is assumed that the adversary is restricted to compromise at most t of the n locations. For long-lived and sensitive secrets (tracing trapdoor parameter k in our system), this assumption about the adversary may be insufficient since the adversary may behave in a mobile manner, that is, she jumps among the authorities collecting as much information as she can. She has the whole life-time of the secret to do so. An easy strategy is to periodically refresh the secret parameter itself by reinitializing the setup phase which leads to a fresh k and hence a fresh blinded tracing trapdoor parameter bk and erasing all previous versions. However, such an attempt disables traceability of blinded identities generated using previous versions of bk and hence such a strategy becomes insecure.Therefore, what is actually required to protect the secrecy of the tracing trapdoor parameterk is to be able to periodically renew its shares without changing its value in such a way that any information learned by the adversary about individual shares becomes obsolete after the shares are renewed. Similarly to avoid the gradual destruction of the information by corruption of shares it is necessary to periodically recover lost or corrupted shares without compromising the secrecy of any of the shares [46].Proactive secret sharing is mainly based on the(+,+)-homomorphic property of polynomial secret sharing and secure computations in the exponent of Feldman's VSS. The life-time of the secret is divided into time periods. The time period must be small enough to ensure that the adversary will not exceed the threshold t in her attack during any period, and big enough to reduce complexity to the minimum. At the beginning of every time period, the update of shares is triggered and it consists of the following stages (please refer to [46] for more details):(1)
update of personal private/public keys,(2)
detection of lost or corrupted shares,(3)
verifiable shares renewal,(4)
erasure of old shares.Here we must emphasize that the erasure of previous versions of shares and private keys is a must and all parties (except the malicious minority) must be honest about erasing their old parameters; since we are working in the static adversary model, the proactive VANET system is secure only in the erasure model.


## 9.3. Forward Security

Since for proactive security to be effective in protecting the tracing trapdoor parameter and since we assume static adversary model, all authorities must erase their past information after shares update. Since all private and authenticated communications among the authorities are performed using private/public keys. An adversary may target these private keys so that she is able to decrypt and recover past ciphertexts that she may have recorded on the channels. Here, we recall the advances in forward-secure cryptography. The goal of forward-secure cryptosystems is to provide the benefits of frequent rekeying without incurring the costs of changing public keys (and associated overhead). They enable the user to frequently erase the secret key while maintaining the same public key. The notion of a forward-security originated from the notion of “perfect forward secrecy” for key agreement, which protects (locks-down) past traffic even after long-term keys are compromised.A generic forward-secure signature scheme is constructed from any ordinary (non-forward-secure) scheme used as a black-box [47]. The security of the forward-secure scheme is then reduced to the security of the underlying ordinary scheme (i.e., if some adversary can efficiently compromise the forward-secure scheme, then we can construct an adversary compromising the security of the underlying ordinary scheme). The efficiency of a generic scheme is usually measured in terms of the number of the invocations of the underlying ordinary scheme, the number of the ordinary keys, and so forth.Forward-secure public key encryption proved harder to achieve, and the first and so far the only result in that area was obtained in [48]. The constructions share similarities with previous tree-based, forward-secure signature schemes. In the construction, however, time periods are associated with all the nodes of the tree (in a preorder traversal) instead of associating time periods with the leaves only; this improves the efficiency of the key-generation and key-update algorithms.


## 10. Conclusions

In this paper we introduced an efficient and secure protocol for message transmission in VANETs that integrates anonymity, traceability, revocation, and confidentiality services in an efficient and robust way. Our protocol realizes noninteractive transmission which is suitable for VANETs as a high mobility network. The protocol uses the idea of adaptive anonymity to further reduce complexity as possible. Our protocol, although has some complexities in the setup phase, yet provides a very simple and efficient way of communication among units on the road. Up to our knowledge, our protocol is the first to achieve all these security services in a noninteractive way of communication.



---

*Source: 702346-2010-01-24.xml*