Fast Enough, Too Big: Post-Quantum Signatures on the Road

Fast Enough, Too Big: Post-Quantum Signatures on the Road 

On a Raspberry Pi 5, post-quantum cryptography (PQC) signatures proved fast enough for vehicle-to-everything (V2X) communication, but most of them are too large for a single wireless message. Only two of the seven PQC configurations we measured fit in one message when the certificate is attached. In both, the vehicle keeps signing with the Elliptic Curve Digital Signature Algorithm (ECDSA), and PQC is applied only to the signature of the certificate authority (CA). 

This report presents the results and their implications. You can compare PQC signature options for V2X by speed and size, assess the effect on pseudonym certificate issuance, and see where standardization and Korean validation stand.

Why V2X Needs PQC

V2X trust rests on digital signatures, and the quantum threat to ECDSA makes PQC a requirement for V2X. 

Why Every Message Is Signed 

V2X lets vehicles in Cooperative Intelligent Transport Systems (C-ITS) communicate with a wide range of external parties: other vehicles and fixed devices such as roadside units (RSUs), including traffic lights and roadside devices that gather road information. These parties cooperate rather than act independently, allowing the transport network to operate more intelligently. 

That cooperation works only if each party can trust the messages it receives. V2X establishes that trust with digital signatures: every Basic Safety Message (BSM) a vehicle broadcasts, for example, carries one. From the signature, the receiver can confirm that the sender holds a valid certificate and that the content was not altered in transit.

The Quantum Clock on ECDSA 

V2X signatures have been based on ECDSA, whose small size and good speed suit mostly wireless environments. 

Quantum computing threatens ECDSA and the other public-key schemes in use today, and V2X is no exception. Once a cryptographically relevant quantum computer (CRQC) emerges, receivers can no longer be sure that a V2X message is authentic, and the trust underpinning the whole domain will be undermined. PQC is the family of algorithms for which no weakness against quantum attack is known. 

Three Regions, Three Timelines 

Governments are already setting timelines: 

  • The United States requires major federal systems to move digital signatures to PQC by the end of 2031. 
  • Europe targets a full transition by the end of 2035. 
  • In Korea, the National Intelligence Service announced the PQC schedule for its cryptographic module validation program in September 2026. 

PQC support is no longer optional. 

The Two Contenders: ML-DSA and FN-DSA 

The first question for V2X is whether PQC signatures keep the two advantages of ECDSA: small size and good speed. To answer it, Saesol Tech integrated two PQC signature algorithms into its own implementation of the IEEE 1609.2 standard, which defines V2X message signatures and certificate formats. It benchmarked them across a range of configurations. The two algorithms are: 

  • ML-DSA (Module-Lattice-Based Digital Signature Algorithm), standardized as Federal Information Processing Standard (FIPS) 204. 
  • FN-DSA (FFT over NTRU-Lattice-Based Digital Signature Algorithm), to be standardized as FIPS 206. 

Speed Is Not the Problem 

Even the heaviest combination uses at most 3% of the 100 ms budget for signing, and five of the seven PQC configurations verify more messages per second than ECDSA. 

The 100 ms Test 

A vehicle broadcasts 10 BSMs per second, so each message must be processed within 100 milliseconds (ms). In practice, the allowance is far smaller, because a vehicle communicates with many surrounding parties. Even so, we measured how much of the 100 ms one message consumes and how much headroom is left. The more headroom there is, the more peers a vehicle can serve before processing becomes a bottleneck. 

Verification runs more often than signing: a vehicle signs only its own messages, but must verify every message it receives from the parties around it. We therefore report verification as throughput, in messages verified per second, relative to current ECDSA. Table 1 lists the vehicle's signature algorithm together with the signature algorithm of the CA that issued the vehicle's certificate. 

The Numbers: Signing and Verifying 

Signing time and verification throughput 

The Real Bottleneck Is Size 

These results come from a Raspberry Pi 5 rather than an on-board unit (OBU) in a vehicle; measuring on commercial C-ITS devices is future work. Signing with even the heaviest combination takes no more than 3% of the 100 ms budget, leaving at least 97% headroom. Verification is faster still: ML-DSA-44 verifies 2.76 times as many messages per second as ECDSA. Taken together, PQC performs comparably to today's ECDSA and, in several configurations, better. The exceptions are the two composite configurations, which verify fewer messages per second than ECDSA (0.50× and 0.95×). PQC is often assumed to be slow. Here, size rather than speed is the real constraint. 

Inside a 10-Hz Heartbeat Message 

A BSM passes through three layers on its way out, and only three values in the final message change size with the signature algorithm. 

Three Layers, One Message 

Message size depends on how a BSM is packaged for transmission, a process defined by three standards: 

  1. 1. The vehicle's state, such as its position, speed, and heading, forms the BSM payload (SAE J2735). 
  1. 2. The vehicle signs the payload, producing the signed message defined in IEEE 1609.2: the Secured Protocol Data Unit (SPDU). The SPDU holds the payload and the vehicle's signature, together with the signer's certificate, so a receiver can verify a message from a sender it has not encountered before. The certificate, in turn, contains the vehicle’s public key and the CA's signature. 
  1. 3. The SPDU is carried in a WAVE Short Message (WSM), the unit of wireless transmission (IEEE 1609.3). 

Three Values That Grow with PQC 

How a BSM is carried in a WSM 

As Figure 1 shows, three values, marked in blue, change size with the signature algorithm: the vehicle's public key, the CA's signature, and the vehicle's signature; everything else is independent of the algorithm.

The 1,400-Byte Ceiling 

A WSM holds 1,400 bytes (B) by default and at most 2,302 B even after a configuration change. With ECDSA, the SPDU including the certificate is 333 B, which leaves ample room. 

One Message, Too Many Bytes 

Replacing ECDSA with PQC grows the SPDU from 333 B to between 937 B and 12,195 B, and only two measured combinations fit in a single 1,400 B WSM. 

ML-DSA: Nothing Fits 

With PQC, each of the three algorithm-dependent values grows to somewhere between a few hundred bytes and several kilobytes (KB). Even ML-DSA-44, the smallest ML-DSA variant, produces a 6,331 B message when used for both signatures, 19 times the ECDSA size and well beyond both WSM limits, the 1,400 B default and the 2,302 B maximum. Using ML-DSA for both signatures takes 5 fragments (ML-DSA-44) to 9 (ML-DSA-87). No ML-DSA parameter set fits in a single WSM in any configuration, including those that use different algorithms for the CA signature and the vehicle signature. 

FN-DSA: The Alternative to ML-DSA 

ECDSA's small size does not carry over to PQC, so staying within a single WSM calls for a smaller scheme. The alternative to ML-DSA is FN-DSA, which is not yet fully standardized. 

Every Combination, Byte by Byte 

SPDU size by signature combination 

Two Algorithms, One Message 

When the vehicle signs with ECDSA and only the CA signs with FN-DSA-512, the message is 937 B and fits in one 1,400 B WSM. 

Two Designs That Fit 

Using FN-DSA for both signatures still exceeds the single-WSM limit: when the vehicle and the CA both sign with FN-DSA-512, the message is 2,408 B. Two other configurations fit: 

  • Role split. The vehicle signs with ECDSA, and only the CA signature on its certificate uses FN-DSA-512. The message is 937 B. 
  • Composite dual signature. The CA signature combines ECDSA and FN-DSA-512. The message is 1,002 B. 

Both fit, but each comes with two caveats: 

Caveat 1: The Vehicle Signature Stays Quantum-Vulnerable 

The vehicle's ECDSA signature remains exposed to quantum attack. 

Signatures face a different quantum threat from encryption. Encrypted data is at risk from “harvest now, decrypt later” (HNDL) attacks. In contrast, signatures are at risk from “trust now, forge later” (TNFL): a signature or certificate that receivers trust today can be forged once a CRQC emerges. The longer a key must stay trusted, the greater the risk. Vehicle certificates are generally short-lived, which keeps the window for an attacker relatively small. CA certificates matter more and stay in use longer, so it is reasonable to apply PQC signatures to CA certificates and keep ECDSA, with its existing efficiency, on the vehicle. 

Caveat 2: The Standard Isn’t Final 

FN-DSA standardization is not complete. 

Even so, moves toward using it in V2X are already visible, and commercial products with experimental support could appear before standardization is finished. 

Sending an ID Instead of a Certificate 

In our measurements, a vehicle and CA that both sign with FN-DSA-512 and attach their certificates produce a 2,408 B message, which exceeds one WSM. Sending only the certificate identifier in place of the certificate reduces this to 797 B, which fits. The receiving vehicle must then already hold the sender's certificate, so a separate path for delivering certificates apart from messages is needed, along with a protocol to run it. Defining that delivery method and validating it in scenarios such as RSUs is future work. 

3,120 Certificates, One Privacy Problem 

Standard PQC signatures make bulk issuance of pseudonym certificates less efficient and weaken privacy, unless PQC is applied only to the CA. 

Why Vehicles Carry Thousands of Certificates 

Beyond signing and verifying messages, V2X must also issue certificates efficiently. Privacy protection is an important requirement in V2X, so vehicles are issued short-lived pseudonym certificates in large quantities. A vehicle changes the certificate it uses about once a week, receives 20 certificates for each week, and picks one of the 20 at random whenever it needs one. The intent is that no one can trace a certificate back to the vehicle's real identity from the certificate alone. 

How Butterfly Keys Keep Requests Small 

A vehicle that requests three years of certificates at once receives 3,120. To issue that many efficiently, the current Security Credential Management System (SCMS), the V2X certificate management infrastructure, uses a technique called butterfly key expansion: 

  1. 1. The vehicle generates one public-private key pair and uploads the public key. 
  1. 2. The server derives the public keys for thousands of certificates from it and issues the certificates. 
  1. 3. The vehicle computes the private key for each certificate itself. 

This works because elliptic curve public keys can be added together. Standard ML-DSA and FN-DSA keys do not have this property. 

What Happens Without Butterfly Keys 

Without butterfly key expansion, the vehicle must generate a key for every certificate it requests and upload each one. For 3,120 certificates, the upload grows from 49 B (including one public key) to about 3.9 mebibytes (MiB) with ML-DSA-44, and it keeps growing in proportion to the number of certificates. 

When Privacy Starts to Leak 

Privacy also weakens. SCMS is not a single server: the registration authority (RA) and the authority that issues pseudonym certificates (ACA) have separate roles and issue certificates together. With ECDSA today, linking a pseudonym certificate to a real identity requires the RA, which knows the vehicle's identity, to collude with the ACA. With PQC, uploading large numbers of public keys in plaintext lets the RA link certificates to identities on its own. 

This privacy loss applies when the public keys are uploaded in plaintext. Encrypting them so that only the ACA can read them was not evaluated here, but it merits further study. 

How the Role Split Sidesteps It 

Accepting the privacy loss is not the only option. The role split described in "Two Algorithms, One Message", with PQC on the CA signature only and ECDSA on the vehicle, also works here: vehicle keys stay ECDSA, so butterfly key expansion still works. The vehicle again uploads a single public key, and only the download of the larger certificates grows.

Where the Standard Stands 

The IEEE 1609 working group (WG) considered a role-split interim option in April 2026 and decided in July 2026 to submit a Project Authorization Request (PAR) for a PQC amendment to IEEE 1609.2. 

April 2026: An Interim Option on the Table 

In April 2026, the WG considered an interim option in which the vehicle keeps signing BSMs with ECDSA and only the CA that issues its certificate signs with Falcon-512 (April 2026 meeting materials). The WG estimated that converting everything to PQC would increase the data a vehicle sends by about 7 times, against only about 2.2 times for this option. This is the same structure as the role split in "Two Algorithms, One Message", and the measurements in this report show that it fits in a single WSM. 

July 2026: The Work Gets Formal 

In July 2026, the WG voted to submit a PAR for a PQC amendment to IEEE 1609.2 (July 2026 meeting materials). The PAR itself does not select an algorithm; the direction on algorithms comes from a work proposal at the same meeting, which is still at the proposal stage: 

  • It adds FN-DSA and SLH-DSA (Stateless Hash-Based Digital Signature Algorithm), instead of ML-DSA, for CA signatures. 
  • The stated reason is that FN-DSA is the likely choice if vehicles adopt PQC signatures, so the verification code can align on a single algorithm. 
  • It states that this direction depends on the publication of FIPS 206. 

  • The PQC signature for vehicles is not yet decided. The presenter expects PQC support to be required in vehicles around 2032. 

Korea’s Road to Validated PQC 

Korea's cryptographic module validation program (KCMVP) does not yet validate PQC signatures, but products that include PQC can already be certified. 

Korea’s Plan at a Glance 

A government plan already exists: the joint-ministry Comprehensive Plan for the Transition to a Pan-National Post-Quantum Cryptography System, September 2025. In September 2026, the National Intelligence Service announced AIMer, HAETAE, ML-DSA, and SLH-DSA as the candidate digital signature algorithms; FN-DSA is not among them (Notice on Candidate PQC Validation Targets and Schedule, September 1, 2026). The schedule is: 

  • January 2028: validation targets are selected. 
  • One year after selection: validation begins. 
  • Two years after selection: inclusion of PQC becomes mandatory. 

Certification Before Validation 

Products with PQC can be certified before validation begins. Under the current standard, PQC counts as a function outside the validation scope (a non-security function), may be included in hybrid form, and may operate in validated mode (Cryptographic Module Implementation Guide Part 1, Annex C.5, National Intelligence Service and others, December 2025). 

Built to Swap Algorithms 

FN-DSA is not on the Korean candidate list, but the September 2026 notice says the list may expand. Crypto-agility, a design that allows swapping the algorithm later, will become a practical requirement. 

Three Realistic Paths Forward 

PQC cannot replicate today’s pure single-algorithm design, in which ECDSA serves every case. This is partly because replacing the existing network infrastructure wholesale to absorb the size increase is out of reach. 

Pick the Algorithm by Layer 

Without a single-algorithm design, the question becomes which algorithm to use at which layer and for what purpose. The answer depends on how long a certificate remains valid and whether a given layer can handle the added size. The realistic options are: 

  • Protect the long-lived certificates. Keep ECDSA for pseudonym certificates in the wireless segment, and apply PQC to enrollment certificates delivered over wired links. Enrollment certificates stay in use for a long time, so they are more exposed to the TNFL threat, whereas pseudonym certificates change about once a week, which makes the quantum threat to them relatively small. 
  • Adopt PQC and standardize fragmentation. Adopt PQC signatures together with a standardized way to fragment and reassemble messages, and leave the privacy weakened by plaintext uploads as a topic for further research.

  • Test the role split, then decide. Implement and evaluate the FN-DSA role split first, since it satisfies the size limit, and decide on deployment after FIPS 206 is finalized and IEEE 1609.2 is amended. 

Making the Case for FN-DSA 

Every measured PQC combination that fit in one WSM used FN-DSA-512, yet FN-DSA is not standardized and is not on the Korean candidate list. Ahead of FIPS 206, the IEEE 1609.2 amendment, and Korea’s selection of validation targets, the industry needs to make the case for FN-DSA in V2X, backed by measurements. 

Signature Algorithms 

Algorithm Full form Standard 
ECDSA Elliptic Curve Digital Signature Algorithm — 
FN-DSA FFT over NTRU-Lattice-Based Digital Signature Algorithm FIPS 206 (planned) 
ML-DSA Module-Lattice-Based Digital Signature Algorithm FIPS 204 
SLH-DSA Stateless Hash-Based Digital Signature Algorithm FIPS 205 

Glossary 

Term Full form Description 
Butterfly key expansion — A technique that lets a vehicle request thousands of certificates while uploading only one public key: the server derives a separate public key for each certificate, and the vehicle works out each matching private key itself. 
Composite signature — A signature that carries two signatures together: one from the method used today and one from a quantum-resistant method. Also called a composite dual signature. 
FIPS Federal Information Processing Standard A series of U.S. government standards. Each standard has a number, such as FIPS 204 for the signature method ML-DSA. 
Fragmentation — Splitting a message that is too large for one wireless transmission unit (a WSM) into smaller pieces (fragments). The receiver puts the pieces back together. 
IEEE 1609.2 — The standard that defines how V2X messages are signed and secured, including the format of certificates. The signed message it defines is called an SPDU. 
KCMVP Korea’s cryptographic module validation program Korea’s program that validates cryptographic modules, meaning the hardware or software that performs signing and encryption. 
PQC post-quantum cryptography Cryptographic methods for which no weakness against attacks by quantum computers is known. 
Pseudonym certificate — A short-lived certificate designed so that it cannot be traced back to the vehicle’s real identity from the certificate alone. A vehicle holds many of them and regularly changes the one in use. 
Role split — A design in which the vehicle keeps signing with the method used today, and only the signature of the organization that issued its certificate uses a quantum-resistant method. 
SPDU Secured Protocol Data Unit The signed message in V2X. It bundles the message content, the sender’s digital signature, and the sender’s certificate, so a receiver can check it even if it has never met the sender. The WSM is the container that carries it over the air. 
TNFL trust now, forge later A threat to signatures: a signature or certificate that receivers trust today can be forged later, once a powerful enough quantum computer exists. The longer a key must stay trusted, the greater the risk. 
WSM WAVE Short Message The container that carries a signed message (an SPDU) over the wireless link. It has a size limit, so a larger signed message must be split into pieces.