  Connected and Autonomous vehicles stand to drastically improve the safety and
efficiency of the transportation system in the near future while also reducing
pollution. These systems leverage communication to coordinate among vehicles
and infrastructure in service of a number of safety and efficiency driver
assist and even fully autonomous applications. Attackers can compromise these
systems in a number of ways including by falsifying communication messages,
making it critical to support security mechanisms that can operate and scale in
dynamic scenarios. Towards this end, we present TVSS, a new VPKI system which
improves drastically over prior work in the area (including over SCMS; the US
department of transportation standard for VPKI). TVSS leverages the idea of
unforgeable tokens to enable rapid verification at the road side units (RSUs),
which are part of the road infrastructure at the edge of the network. This edge
based solution enables agile authentication by avoiding the need for back-end
servers during the potentially short contact time between a moving vehicle and
the infrastructure. It also results in several security advantages: (1)
Scalable Revocation: it greatly simplifies the revocation problem, a difficult
problem in large scale certificate systems; and (2) Faster Refresh: Vehicles
interact more frequently with the system to refresh their credentials,
improving the privacy of the system. We provide a construction of the system
and formally prove its security. Field experiments on a test-bed we develop
consisting of on-board units (OBUs) and RSUs shows substantial reduction in the
latency of refreshing credentials compared to SCMS, allowing the system to work
even with smaller window of connectivity when vehicles are moving at higher
speeds. Notably, we are able to execute the bottleneck operation of our scheme
with a stationary RSU while traveling at highway speeds .
