## 2 Related Works and Techniques  
According to [PERSON] _et al._[5], a smart vehicle can record, compute, and specify its position. It uses the traditional public-key infrastructure (PKI). The complexity of computation is increased if the vehicle uses PKI to encrypt the messages. The computation overhead of the communication step is also then increased. Moreover, for privacy and un-traceability, the vehicle must frequently change its certificate, imposing a burden on the TA. [PERSON] _et al._[6] proposed a scheme in which RSUs were used to support message authentication by vehicles. When a vehicle enters the coverage range of an RSU, it establishes a secret key after mutual authentication. The vehicle will then generate a short message authentication code (MAC) using this secret key. The RSU will verify the authentication of MAC. However, exposure of the certificate creates the problem that the vehicles will become traceable. In 2010, [PERSON] _et al._[7] proposed the RSU-aided distributed certificate service (DCS), which enables vehicles to update their certificates from an RSU. A vehicle can update its certificate from any RSU, even when it is not in the coverage range of that RSU. The performance of the DCS depends on the density of the RSUs. [PERSON] _et al._[8] proposed a pseudonymous authentication scheme with privacy preservation (PASS), which supports the DCS. The scheme can reduce the certificate-updating overhead and the revocation overhead. Attackers cannot trace legitimate vehicles, even when they compromise the RSU. However, the DCS has the loading of certificate and it can not work in sparse RSU environment. [PERSON] _et al._[9] used chameleon hash values to perform anonymous authentication and used ID-based cryptography (CH-IBC) to perform key agreement. In this scheme, vehicles use a chameleon hash value as a disposable alias. They can verify message authentication and message integrity, but it still needs the assistance of an RSU. [PERSON] _et al._[10] proposed a chameleon hash function-based message authentication scheme without RSUs, but they did not solve the problem of malicious revocation. [PERSON] _et al._[11] used the bilinear Diffie-Hellman method (BDH) to propose a message authentication scheme for a dense RSU environment, which involves certificate request RSU by RSU. [PERSON] [12] proposed a message authentication scheme that can get pairing value to establish mutual trust in intra- and inter-RSU environments based on the chameleon hash function, but this scheme suffers from malicious revocation. Section 4 will compare DCS [7], PASS [8], CH-IBC [9], BDH [11] and the proposed scheme in terms of functionality and performance. Two problems are evident in all of the listed schemes. First, RSUs perform the most important roles in message authentication, but their performance worsens as they become sparser. The second problem concerns the certification base. The privacy of vehicles is maintained by making their identities and routes non-traceable. Accordingly, identities must be anonymous and changed frequently, generating heavy loads that are associated with certificate changing and informing of revoked certification. To solve the two aforementioned problems, we propose a secure scheme for VANET. The installation of RSUs can be increased even in very sparse environment, and the vehicles establish mutual trust and obtain the pairing value based on the secret that is embedded in their anonymous identities instead of by certification. The following section presents in the scheme in detail. In a WSN, the random key pre-distribution (RKP) [13] is used to perform mutual authentication using a common secret key. A random subset of keys in the pool will be embedded into the sensor nodes before node deployment. The nodes in the WSN can authenticate each other if they have common secret keys. The plain secret keys in the nodes make RKP vulnerable to compromise attacks [14].