  Anonymity is a desirable feature for vehicle-to-vehicle (V2V) communications,
but it conflicts with other requirements such as non-repudiation and
revocation. Existing, pseudonym-based V2V communications schemes rely on
certificate generation and signature verification. These schemes require
cumbersome key management, frequent updating of certificate chains and other
costly procedures such as cryptographic pairings. In this paper, we present
novel V2V communications schemes, that provide authentication, authorization,
anonymity, non-repudiation, replay protection, pseudonym revocation, and
forward secrecy without relying on traditional certificate generation and
signature verification. Security and privacy of our schemes rely on hard
problems in number theory. Furthermore, our schemes guarantee security and
privacy in the presence of subsets of colluding malicious parties, provided
that the cardinality of such sets is below a fixed threshold.
