Abstract: Mobile edge computing (MEC) deploys computing and storage resources to the edge of the network, which brings real-time and high-reliability services to the Internet of vehicles (IoV). However, MEC faces various security threats. Attackers may control edge data centers and leak the pseudonym information of the vehicle, thereby threatening the vehicle’s identity privacy. For this problem, a vehicle pseudonym management scheme in MEC-IoV is proposed, which can realize efficient update of pseudonym information, secure storage of pseudonym information in the edge cloud, and traceability of pseudonyms. This scheme uses the edge cloud with high real-time performance to replace the central cloud to authenticate the vehicle identity, which improves the efficiency of identity authentication and realizes efficient pseudonym update. The pseudonym information is encrypted by the homomorphic encryption algorithm, which guarantees the security of the pseudonym information and doesn’t affect pseudonym management in the edge cloud. Each pseudonym table of the vehicle is associated with a search term calculated based on the pseudonym in the table, and the highest authority of the system can calculate the search term based on the ciphertext of the pseudonym table to expose the real identity of the malicious vehicle, which realize traceability of pseudonyms. After that, through the provable security theory, it is proved that the scheme is indistinguishable under the chosen plaintext attack, and the security analysis of the anonymity of the vehicle identity, the integrity and non-repudiation of the message in the scheme is carried out, which achieve the security requirements of preserving vehicle’s identity privacy in IoV. In the end, the efficiency analysis and simulation of the scheme in terms of identity authentication, pseudonym request, and homomorphic encryption performance are carried out. Experimental results show this scheme can achieve the requirements of low-latency communication in IoV and is superior to existing schemes in authentication efficiency.