  Revocation of dishonest users is not an easy problem. This paper proposes a
new way to manage revocation of pseudonyms in vehicular ad-hoc networks when
using identity-based authentication to increase efficiency and security through
certificateless authentication. In order to improve the performance of
revocation lists, this paper proposes the use of a data structure based on
authenticated dynamic hash k-ary trees and the frequency with which revoked
pseudonyms are consulted. The use of the knowledge about the frequency of
consultation of revoked pseudonyms allows an easier access to the most popular
revoked pseudonyms to the detriment of revoked pseudonyms that are the least
consulted. Accordingly, the proposal is especially useful in urban environments
where there are vehicles that spend more time on road than others, such as
public service vehicles.
