Network-efficient authenticated pseudonym-based V2X communications with constant revocation costs

Standard Vehicle-to-everything (V2X) communications guarantee privacy against tracking by provisioning each vehicle with many conditionally unlinkable pseudonym certificates, which can be linked to each other only with knowledge of a secret information, disclosed by ad-hoc authorities in case of misbehavior for efficient revocation. Certificates are bound to independent keys, but include pseudo-random indexing values which enable such an efficient mechanism at the expense of increasing network overhead of all V2X messages. We propose a novel network-efficient protocol where each vehicle is provisioned with conditionally unlinkable pseudo-random asymmetric key pairs, thus removing the need for linkage values and reducing network overhead while still supporting revocation at constant network costs. Our approach represents a novel application of hierarchical deterministic homomorphic key derivation schemes, which are mostly known for deterministic wallets in the context of blockchains. Compared to standards based on explicit certificates, our approach has lower network overhead, no computational overhead for securing communications, and same cryptographic assumptions. Computational costs for key management operations are higher, but still affordable. We analyze the costs of our proposal both asymptotically and analytically when instantiated with the NIST p-256 elliptic curve recommended by standards.