All You Need to Know About V2X PKI Certificates: Butterfly Key Expansion and Implicit Certificates

AutoCrypt SCMS now supports Butterfly Key Expansion for both implicit and explicit certificates of the V2X PKI ecosystem. This article explains why Butterfly Key Expansion is necessary for the SCMS and why implicit certificates might be a useful alternative to conventional certificates.

Vehicle-to-everything (V2X) communication allows vehicles to communicate with other vehicles and road entities for safety warnings, traffic coordination, and eventually vehicle-infrastructure cooperated autonomous driving (VICAD). Given that these V2X messages are critical to road safety, a vehicular public key infrastructure (PKI) known as the Security Credential Management System (SCMS) has been adopted worldwide to protect the integrity of V2X messages and the privacy of road users. V2X PKI certificates, or SCMS certificates, are therefore a crucial enabler of secure V2X communications.

What Is Unique About V2X PKI Certificates?

What makes V2X PKI certificates unique? The most significant difference between IT and V2X authentication is that IT authentication is centralized and hierarchical. Users use their digital signature to reveal their identity to the server, after which the server verifies the identity and grants the user access. There is apparently no need for users to prove their identity to other users. On the other hand, V2X authentication is decentralized, where users (vehicles) need to verify each other’s identity without revealing it. Sounds contradictory? This is made possible by using pseudonym certificates.

In the SCMS, pseudonym certificates are issued by authorization certification authorities (CA) to every road user (vehicle). As suggested by its name, these certificates are pseudonymous and thus do not contain the vehicle’s identity, but instead contain proof that the vehicle’s identity had been verified by the CA and that it is a legitimate entity.

Furthermore, to prevent a stalker from spying on the same pseudonym certificate over an extended period to trace its travel routes and behaviours, pseudonym certificates have very short validity periods. For an average private vehicle, up to 20 pseudonym certificates are issued weekly, rotating every few hours to prevent tracing. These numbers can vary depending on local regulations and the importance of the passenger. For instance, the vehicle for a head of state might require non-rotating, one-time pseudonym certificates issued every five minutes.

What Is Butterfly Key Expansion?

Every time a vehicle requests a pseudonym certificate, the responsible CA needs to sign a new certificate and return it to the vehicle. Given that a typical vehicle needs up to 20 certificates per week, the CA needs to sign over a thousand certificates to a single vehicle over a year. This is a scale never seen before in the IT or financial industry. As more and more vehicles join the V2X environment, it can soon become difficult for CAs to cope with the growing number of requests.

With advancements in cryptographic construction technology, a novel approach known as Butterfly Key Expansion now overcomes this disadvantage. Butterfly Keys allow a vehicle to request an arbitrary number of certificates all at once; each certificate with a different signing key and each encrypted with a different encryption key. A request using Butterfly Key Expansion contains only one signing public key seed, one encryption public key seed, and two expansion functions that enable expansion. Therefore, Butterfly Keys are very useful for requesting pseudonym certificates as they can drastically decrease the number of requests needed.

Note that Butterfly Keys are not needed for issuing application certificates* to roadside units (RSU). Since privacy is not a concern to roadside infrastructures, application certificates are issued once at a time and have very long validity periods, meaning that application CAs are fully capable of dealing with the volume of requests.

(*Pseudonym certificates are used by vehicles for self-identification in V2V communications, whereas application certificates are used by roadside infrastructures for self-identification in V2I applications.)

Explicit vs. Implicit Certificates

Pseudonym certificates can be constructed in two different forms: conventional (explicit) certificates and implicit certificates. Conventional certificates consist of three distinct pieces of data: 1) a public key, 2) the digital signature of the CA, binding the public key to the vehicle’s identification data, and 3) the vehicle’s identification data. During V2V message transmission, the sender signs the certificate with the private key, after which the receiver uses the public key in the certificate to verify and view the message. In this process, the sender’s identity is “explicitly verified” because by opening the message, the receiver knows that the sender is the only entity holding the private key. As such, these certificates are also known as explicit certificates.

However, a disadvantage of explicit certificates is that, since they contain three distinct pieces of data, their size can range between 2,000 bits to 30,000 bits, depending on the level of security needed. Such a size isn’t a concern in and of itself. But in the V2X environment, where traffic volume is high and transmission speeds are pivotal, smaller sizes can be more advantageous.

To enable speedier message transmission and more efficient certificate issuance, a new form of V2X PKI certificate is gaining popularity. Known as implicit certificates, or Elliptic Curve Qu-Vanstone (ECQV), these certificates contain the same three pieces of data as explicit certificates do, but do not carry them as three distinct elements. Instead, the public key and the digital signature are superimposed, leaving a single reconstruction value that is similar in size as the public key. The receiver of the message uses this reconstruction value to reconstruct the public key and verify the message. The way in which the public key and the digital signature are superimposed means that by verifying the public key, the digital signature and the legitimacy of the sender get “implicitly verified”.

Since implicit certificates contain a single reconstruction value, they are much lighter and thus require much less bandwidth to transmit. The typical size of an implicit certificate is only 200 to 500 bits, which is ideal for the SCMS, where a large volume of certificates needs to be transmitted within a constrained timeframe.

The concept of implicit certificates is developed and patented by Blackberry Certicom. Nevertheless, CAs are free to issue implicit certificates for applications in the SCMS in accordance with IEEE 1609.2.

V2X PKI Regional Requirements and Preferences

As mentioned earlier, Butterfly Key Expansion is only beneficial for issuing pseudonym certificates and is not used for generating application certificates. The same is true for implicit certificates. The lightweight advantage of implicit certificates is best seen when applied to pseudonym certificates, but less significant when applied to application certificates. Given that the mechanism behind implicit certificates is more complex, some parts of the world prefer to stay with explicit certificates.

As a result, a mix of different mechanisms is used in the real world. In fact, different transport authorities have established different requirements for the certificates used in their SCMS. In North America, implicit certificates have become the standard for all V2X PKI certificates, whereas, in China, explicit certificates are required. Europe has been establishing two different standards, one for explicit certificates and one for implicit certificates.

In general, V2X PKI certificates can be constructed using four different combinations.

AutoCrypt SCMS Ready to Support All Certificate Types

In late 2022, AUTOCRYPT completed its development on the issuance of both explicit and implicit certificates with Butterfly Key Expansion, gaining the full capability to issue and provision all types of V2X PKI certificates in the SCMS.

To learn more about AUTOCRYPT’s V2X security solutions and AutoCrypt SCMS, contact

To stay informed and updated on the latest news about AUTOCRYPT and mobility tech, subscribe to AUTOCRYPT’s newsletter.

Related Articles