  Vehicular ad hoc networks allow vehicles to connect themselves as networks so
that cars could communicate with each other. This paper introduces an anonymous
communication scheme providing integrity protection, multi-level privacy and
auditability. The scheme is based on a certificateless ring signature proposed
in this paper, which is contributed to reduce the length of the signature and
simplify the key management. In our scheme, vehicles can compose the anonymous
group without the help of road-side infrastructure or central authority. The
computation overhead is close to a normal signature scheme, so it is efficient
in most application scenarios. We also present a small-scale implementation to
show the availability of the prototype system.
