Abstract: Real-time map plays an important role in autonomous vehicles (AVs) navigation. Compared with the existing map updating methods, the real-time map updating method is based on crowdsensing has lower cost and higher accuracy. However, in the process of map updating, this method increases the risk of data and user identity leakage. How to ensure the confidentiality of uploaded data and the anonymity of users is a challenge in real-time map updating. This paper proposes a secure and efficient map update scheme for AVs (SEMU). In the SEMU, vehicle users can sign the sensing data and store the encrypted data in the vehicular fog node by using signcryption and proxy re-encryption technology. When the map company wants to access the data, the vehicular fog node sends the encrypted data to the server, and the server re-encrypts the data to the map company. At the same time, server cannot obtain any explicit information about the data. In addition, the aggregate signature technology is applied to reduce the computational overhead. Through the credit management of vehicle users, the reliability of data can be improved. Finally, security analysis shows that the scheme achieves data confidentiality, integrity, reliability, authentication and non-repudiation, and guarantees the anonymity and traceability of users. The simulation results illustrate that the proposed SEMU has the incentive, and it is efficient in terms of computational overhead.