Congestion pricing that respects “driver privacy”

Andrew J. Blumberg
Robin Chase
Stanford University
Meadow Networks
Mathematics Department
robin@meadownetworks.com
blumberg@math.stanford.edu

Abstract— In 2003, the city of London implemented a conges- per traveler to triple in major cities in the United States
tion pricing policy in order to reduce traffic and raise revenues between 1982-2003 [1]. Given the greater associated costs of
for transit improvements. The dramatic success of this system traffic congestion, the gathering concern about urban sprawl,
has led to widespread consideration of the adoption of such
variable tolling, including road pricing, in dense urban cores and the lack of successful policy alternatives, it seems highly
around the world. While from many perspectives the broad likely that there will be broad deployment of congestion
implementation of such congestion pricing systems would be pricing systems in the next decade. From many perspectives,
socially beneficial, the likely consequences for the privacy of the widespread adoption of such systems is a very welcome
motorists are extremely negative. A sophisticated congestion development. In particular, nuanced usage tolls which ac-
pricing strategy will assign a cost to a specific space-time
path of a vehicle through the pricing zone. Straightforward curately charge drivers for the higher value of driving on
implementations of monitoring systems to assess congestion tolls scarce road resources during peak periods allow fine-tuned
thus require detailed tracking technology to monitor the paths incentives to promote the reduction of non-essential driving,
of each individual vehicle. car-pooling, and time or mode shifts, leading to a variety of
In this paper, we introduce a novel protocol for computing societally beneficial outcomes.
congestion pricing tolls in a fashion that preserves driver pri-
vacy. Our scheme uses cryptographic algorithms to guarantee Unfortunately, from the perspective of driver privacy
that the state can collect arbitrarily nuanced congestion pricing there are some extremely worrisome consequences of the
tolls without being able to track the movements of individual adoption of such highly nuanced usage charge systems. A
drivers. That is, the system provides simultaneous guarantees sophisticated pricing strategy will assign tolls as a function
that the state can correctly compute the tolls for a particular of the specific space-time path of a vehicle through the
driver from the information it collects but that the state cannot
reconstruct the path of the driver no matter what it does with congestion pricing zone. That is, to compute the cost of a
this information. particular trip one must know the entire path for the trip.
Our system is built using a variant of the protocol we As a consequence, straightforward designs for implementing
described in a previous paper to handle automated traffic such congestion pricing systems require detailed tracking
enforcement (i.e. stop-light violation detection) in a way that of individual drivers. For example, the less-sophisticated
preserves driver privacy and eliminates camera use. The pro-
tocol is relatively easy to implement with existing technology,
systems in use in London and Stockholm use extensive
and such implementation can be done in a fashion which is networks of cameras to identify and charge vehicles entering
sufficiently robust to handle realistic operational requirements. the congestion pricing zone. Despite well-meaning intentions
In particular, we discuss methods for ensuring resistance to and promises to discard data immediately, once cameras are
attempts to cheat and modifications to handle sporadic users installed and the technological capacity is in place, such sys-
(tourists).
tems can provide governments with tempting opportunities
for the real-time tracking of citizens’ movements. History
I. I NTRODUCTION
suggests that assurances by government entities that such
As a consequence of the success of the congestion pricing information will be used responsibly cannot be trusted over
system in the city of London, many municipalities are the long-term. It seems preferable to develop and implement
considering the adoption of such variable usage pricing a system that does not offer such temptation by simply not
for their dense urban cores. It is hoped that such tolling facilitating vehicle tracking. Such systems will also have
will decrease traffic, shift travelers to more sustainable much greater public acceptance than the alternatives.
transportation modes and generate much-needed revenue to In this paper we present a system which supports the
support the transit infrastructure. In January 2006, Stockholm implementation of arbitrarily sophisticated congestion pric-
undertook a six-month trial implementation of such a system ing schemes while preserving driver privacy. Although there
and local governments in many U.S. cities including New has been substantial previous work on anonymous electronic
York, Boston, and San Francisco are considering imple- toll collection [2], existing protocols are better-suited to
menting some form of congestion pricing. Moreover, there traditional pricing schemes. While we have taken pains to
has recently been serious discussion of the introduction of attempt to ensure that our system is reasonable for actual
an integrated system of nuanced road usage charges on implementation, we are not necessarily convinced nor argu-
highways throughout Europe. ing that this is the best possible design. Rather, we simply
Steady increases in vehicular traffic on relatively fixed contend that our system is a sufficiently plausible alternative
urban road infrastructure have caused the annual traffic delay so as to shift the nature of the debate — it is possible to have
sophisticated congestion pricing without surrendering driver of dynamic license plates, it is impossible for the DMV to
privacy. reconstruct any information about Dennis’s paths through the
We have adapted ideas developed in previous work for congestion pricing zone. Nonetheless, the DMV can collect
automated traffic enforcement systems which preserve driver the money it is due with confidence.
privacy [3]. The key ingredient is a cryptographic protocol The remainder of the paper is organized as follows. We
for secure multi-party shared computation. Such a protocol begin by reviewing and extending the notion of driver privacy
allows mutually untrusting parties to compute functions of we introduced in our previous paper. Then, we quickly
private information without revealing the data. Specifically, review the properties of the cryptographic primitives we
in a two-party shared computation, there are two individuals utilize. Next, we formally describe the protocol and discuss
A and B who wish to compute a function f . The function f its properties. Finally, we discuss the implementation of
depends on two variables x and y, and we will assume that our proposed congestion pricing scheme. A natural concern
A possesses the argument x and B possesses the argument y. is the susceptibility of the design to scams and cheats,
Certainly a naive way to compute the value f (x, y) is for A and we describe how to make the protocols robust against
and B to share their private information (the values of x and common attacks. Another significant implementation issue is
y). But via the two-party shared computation algorithm, A accommodation of intra-regional travelers, those just passing
and B can compute f (x, y) in such a way that neither A nor through. That is, in the early years of adoption of such
B learn anything about the others’ private data except what systems it is likely that they will be piecemeal — areas
could be inferred from the value of f (x, y). Thus, neither A with congestion tolling in place will be accessible to drivers
nor B needs to reveal their private information. who cannot be assumed to possess appropriate transponders,
We will now outline our congestion pricing protocol. for instance. Ensuring that there is a sensible strategy for
Every car is assumed to have a radio-frequency transponder handling the issue of such “tourists” is essential to any
(akin to an EZ-pass or related automatic tolling technology), practical implementation of a system such as ours.
and the congestion pricing zone is presumed to have an ar-
II. A REVIEW OF THE NOTION OF DRIVER PRIVACY
bitarily dense distribution of monitoring devices that interact
with the transponders. We will describe the interaction for a In a previous paper, we introduced and developed a notion
driver Dennis and the tolling agency, which we will refer to of driver privacy. We will review and refine these ideas in
as the DMV. this section. There has been a great deal of prior work on
1) At the beginning of the year, Dennis privately chooses informational privacy, and there are now reasonably compre-
a lengthy sequence of “dynamic license plates”. This is hensive ideas about what this should mean, developed both
just a long list of very large numbers (chosen in such from a legal standpoint and from a cryptographic standpoint.
a way so as to minimize the probability of overlap However, there had previously been relatively little work on
with any other driver). Dennis digitally signs the list characterizing how to extend these notions to the context of
of numbers, and gives the signature but not the list to driving.
the DMV. The first and most central piece of information of value in
2) As Dennis drives, the transponder in his car rapidly this discussion is the location of a particular vehicle at a par-
cycles through the list of dynamic license plates, at ticular time t. However, merely protecting the specific path
the rate of a new number each second. of the vehicle is insufficient. We must also safeguard partial
3) When Dennis enters the congestion pricing zone, as he information about the location during a timespan [t1 , t2 ]. For
drives past monitoring devices, the devices record his example, we want also to keep private information that “a
current dynamic license plate number. particular vehicle has crossed an intersection near the owner’s
4) At the end of the a predetermined billing period, house an odd number of times between 9am and 2pm” since
Dennis returns to the DMV to renew his registration. such information indicates that the vehicle owner is not home
at 2pm. In formal terms, partial information about a vehicle
a) The DMV has a long list of numbers collected
can be modeled by considering functions of the location of
from drivers in the congestion pricing zone.
a vehicle and the time. Thus, we must also seek to limit the
b) Dennis has a long list of dynamic license plates.
class of functions of the location which can be learned from
c) Dennis and the DMV engage in secure two-
data collected by any tolling system. This kind of constraint
party computation of the charges Dennis owes
is reasonable for the purely computational aspects of the
the DMV.
protocol.
At the end of this computation, the DMV does not However, driving is a physical activity which is embedded
learn Dennis’s license plate numbers, and Dennis does in a social context that modifies and limits the kinds of pri-
not learn the DMV’s list of charged numbers. Because vacy guarantees that are reasonable. It is useful to carefully
the DMV has the signature Dennis created at the recall the kind of “implicit privacy” which is currently avail-
beginning of the year, the DMV is assured Dennis did able. On the one hand, most drivers (correctly) assume that
not lie about the license plates he chose. in general the path of their vehicle is basically completely
The important property of this protocol is that because unmonitored, and that the path cannot be reconstructed at a
the DMV never learns the actual values of Dennis’s choice later date by some governmental entity except insofar as they
leave other traces of their movements (e.g. geographically III. I NFRASTRUCTURE AND PROTOCOLS
localized credit card activity). On the other hand, it is nearly In the next sections, we describe our protocol, which
universally legal for a police car to follow a private vehicle can be used for any kind of variable tolling including both
for short periods of time without requiring any special road and congestion pricing. There are two components
dispensation from higher authority. Furthermore, in the event to our design for a secure privacy-preserving protocol for
that a driver commits a traffic infraction, they immediately congestion pricing. The first important choice is a rejection of
surrender their right to driving privacy and can be tracked cameras in favor of radio transponders, modeled on the EZ-
and pursued. pass transmitters in common use in the northeastern United
There are two important characteristics of this “implicit States.1 . As discussed in the previous section, extensive
privacy” that we wish to emphasize as worthy of preserva- camera networks are unsuitable for the kinds of privacy
tion. we envision. When misused, they allow arbitrary covert
surveillance of individual vehicles. Relying on assurances
1) The resource costs of tracking are prohibitively high of the goodwill of the monitoring entities is unacceptable.
on a large scale. It is a major investment for the state The second component in our design is the employment of
to track any given driver for a sustained basis, and cryptographic algorithms (e.g. to provide secure signatures
completely impossible for the state to track even a tiny and encrypted channels) as a foundation on which we can
fraction of the total number of drivers. base protocols that offer strong security guarantees.2
2) It is difficult for the state to gather information about
an individual driver without the driver becoming aware A. An intuitive sketch of our protocol
of the monitoring. Since police cars tend to be dis- The core idea of our solution is reasonably simple. Cur-
tinctively marked, it is fairly obvious when a driver is rently, when an individual registers a car they receive a
being followed by one. Even when unmarked cars are license plate. Automobile registration is authenticated using
employed, it often becomes apparent that monitoring is official identification of the individual as well as a vehicle
occurring. Only with a very significant use of resources identification code. A naive congestion pricing system would
can the state reliably track vehicles in an undetectable employ a ubiquitous network of monitoring devices (e.g.
fashion. cameras) or require license plates with unique RFID tags to
track the path of a specific vehicle in order to assess charges.
Therefore, we propose the following rough notion of Our proposed solution bootstraps from the same proce-
a system which preserves driver privacy. We require that dural base. An individual seeks to register a car or get a
the idealized technical underpinnings of the system (e.g. residential parking permit. When they do so (either in person
the transponder interactions) guarantee the stronger cryp- or online), they commit to a very long list of “digital license
tographic level of privacy outlined above — computational plates”. However, the list of such license plates itself is not
hardness of computing functions of the path of a particular disclosed to the registering authority — only a ”digital com-
vehicle other than those expressly permitted by the protocol mitment” to the list is revealed, which assures the registering
(such as the amount of the toll). And moreover we require authority that the list cannot be changed later. The individual
that the actual reification of the system in a social and is issued a radio transponder or purchases one at outlets
technical implementation guarantee the level of “implicit arranged for by the city or state (i.e. convenience stores,
privacy” provided by sporadic police monitoring today. consumer electronics stores, gas stations) and places it in
Naive congestion pricing schemes which rely on the use the registered vehicle. Using a cell phone or the internet, this
of cameras or transponders with a fixed unique ID to track transponder is programmed with the previously agreed upon
vehicle motion fail to preserve either of these characteristics. list of “digital license plates”. The transponder cycles through
It becomes trivial for the state to access detailed real-time the list of license plates, maintaining a different one as the
information about the path of any particular vehicle. We “current license plate” each second. As the motorist moves
believe that there is an essential qualitative difference in the through the congestion pricing zone, monitoring devices
nature of the privacy available between the situation where record their digital license plates for use in charging the
a court order and the investment of activity by many police driver.
officers is required for tracking, and the situation where an However, since the motorist is rapidly cycling their digital
intern at the mayor’s office can push a button and track a license plate number, it is not possible for the network
driver. In addition, in such implementations the monitoring of monitoring devices to track the motion of the motorist
is undetectable to the driver. That is, the driver has no way of through the city. At the end of the billing period, in order
knowing whether the information which is being constantly to keep their registration active, the motorist must engage in
collected is being utilized (or might in the future be utilized) 1 Note however, although the EZ-pass system uses radio transponders,
for tracking purposes, or is simply being thrown away after it does not preserve driver privacy. Our transponders are somewhat more
use for toll pricing. sophisticated
2 Our constructions rely on making computational assumptions about the
The system we will describe in the following sections difficulty of certain kinds of problems, like factoring large integers. These
satisfies our notion of driver privacy. are standard assumptions that have been well-studied.
a special protocol with the registering authority to compute input, a message x, and produces a pair of strings (α, β)
the charges based on the intersection of the motorist’s list of which consists of a commitment α (safe) , and a secret
digital license plate numbers and the authority’s very long opening value β (key). The recipient, upon receiving β, can
list of numbers collected by the monitoring devices. This open the value by running O PEN(α, β) → x. See [5] for a
special protocol enables this computation to be performed detailed description of this primitive.
in a “zero-knowledge” fashion, so that the motorist does not Zero-knowledge Proof System. A zero-knowledge proof
disclose any information about their list of numbers other system consists of two programs, a P ROVER and a V ER -
than those in the intersection. IFIER, which interact in a way that allows the Prover to
In order to make this work in a fashion which is resistant to convince the Verifier of a true statement without revealing
tampering on either side, there are a number of cryptographic any extra information about the statement. The proof system
techniques that must be used. We have alluded to some of guarantees three properties: (a) any true statement can be
them — for instance, the digital commitment the motorist proven so that an honest Verifier will accept the proof, (b)
discloses at the beginning of the year prevents her from a malicious Prover, no matter how it tries to cheat, has a
changing her list later or disavowing her list of numbers at vanishingly small chance of convincing a Verifier of a false
the end of the year. Similarly, we require “zero-knowledge statement, (c) a malicious Verifier, no matter how it tries
proofs” and “secure multi-party computation algorithms” to to cheat, will not “learn” anything other than the truth of
perform the computation at the end of the year. We begin the statement. For the purpose of this paper, we shall only
the formal description of our protocol by reviewing the attempt to prove statements which have short “witnesses”
cryptographic supports we require. (i.e. NP languages). Such a statement might be, for example,
“The value committed in c does not appear in the list
B. Cryptographic infrastructure a1 , a2 , . . . , an .” This statement has a short witness since the
Unless otherwise noted, all of the algorithms listed are opening to the commitment c, i.e. β, allows anyone to run
efficient probabilistic algorithms. Certain common inputs, O PEN(c, β) and verify the statement. The salient point, then
such as security parameters which indicate how long keys is that, using zero-knowledge proof systems, a Prover can
should be, for example, are omitted for clarity. The overall prove the same statement to a verifier, without revealing β,
introduction to these primitives is cursory and informal due m or anything else other than the verity of the statement!
to limited space. Since their discovery by Goldreich, Micali and Widger-
Blind Signature Scheme. A blind signature scheme, first son [6], zero-knowledge proofs have become an essential
introduced by Chaum [2], consists of a four-tuple of proba- tool for designing modern cryptographic protocols. A good
bilistic algorithms, G EN , S IGN , R EQUEST, and V ERIFY. The introduction is presented in [5].
G EN algorithm generates a public key, pk, and a secret key Secure Multi-party Computation In a secure multi-party
sk. The S IGN(sk) and R EQUEST(pk, m) algorithms together computation protocol, there are a series of agents Ai who
form a protocol in which a signer with input sk and signature each possess private information xi and wish to compute a
requester, with input pk and message m interact with one function f (x1 , x2 , . . . , xn ). If there existed a trusted third
another in order to generate a signature σ. At the end of the party, the agents could send their private information to the
protocol, (a) the signer has no knowledge about m or σ, and third party, who would perform the computation of f and
(b) the requester receives σ, and nothing more. In particular, send back the answer. A secure multi-party computation
upon receiving σ at a later point, it is infeasible for the signer protocol is a means for simulating the characteristics of this
to associate σ with the requester; likewise, it is infeasiable ideal situation in the absense of a trusted third party. In such
for the requester to forge signatures on any other message a protocol, the agents engage in a series of interactions such
m0 6= m. Finally, the V ERIFY(σ 0 , mi , pk) algorithm runs on that with high probability the outcome is the computation
input, a pair of strings σ 0 , m0 and public key pk and returns of f (x1 , x2 , . . . , xn ) but it impossible for any particular
either accept or reject. The VERIFY algorithm accepts all agent Ai to recover any information about an agent’s private
signatures generated by the signing algorithm (when run with information xi beyond anything which can be inferred from
corresponding public and secret keys). The blind signature the value of f . Various algorithms for achieving this sort
scheme in [4] is suitable for our application. of goal have been around for over a decade, and a good
Commitment Scheme. A commitment scheme consists of introduction is presented in [5].
two algorithms, L OCK and O PEN, which are run during two
separate phases. Often the following analogy with a metal C. Hardware infrastructure
safe is used: in the commitment phase, the sender locks a
message m into a safe and sends the entire safe to a receiver. Our system involves three physical components.
The message is hidden since the receiver cannot crack the Car Transponder. Each car is equipped with a transponder
safe, and it is bound since the sender cannot change the which can be requested to broadcast its identification string.
contents of the safe after having given it to the receiver. In As mentioned above, a transponder’s identification string can
the second, decommitment phase, the sender gives the safe’s periodically change. We say that at time t, the transponder
key to the receiver, thereby allowing the receiver to read broadcasts a string ρt . In addition, the transponder is capable
the message. Thus, the L OCK(x) → (α, β) algorithm takes of performing standard authentication procedures to verify
that the request for identification is being made by an 1) (Authentication) L authenticates itself by presenting
authorized party. a certificate signed by pk 0 and requests v to send its
Traffic logger. A traffic logger L monitors the roads. When current token.
a car passes a traffic logger, the logger authenticates itself to 2) (Reply) The vehicle v sends (t, σt , mt ) to L, encrypted
the vehicles transponder, requests the transponder’s ID and in L’s public key pk.
logs the string which it receives. In order to authenticate 3) (Verify) The Logger verifies that σt is a valid signature
itself, the logger has a signing key which is signed by the of mt generated from D’s token-signing key pk, and
registering authority. This interaction is triggered by a non- records (t, σt , mt ). If the signature does not verify,
specific signal to the logger that a car has passed, for instance then L calls the local police office to indicate that
from a plate in the road or a simple optical detector. a malfunctioning Transponder has passed through its
Registration server. The registering authority D maintains a location.
public signing key, pk for a blind signature scheme, a public 4) (Post) At the end of each day, D posts and timestamps
signing key pk 0 to sign certificates, and a website. a list, ld of all of the events that have been logged by
all traffic loggers for that day d.
D. The protocol
There are three simple protocols in our system. Renewal
Common Input: D’s public token-signing key pk, for a blind
Registration Protocol signature scheme. D’s public logger-signing key pk 0 for a
Common Input: D’s public token signing key pk, for a blind signature scheme.
signature scheme. D’s public logger signing key pk 0 for a At the end of each billing period, and in order to keep
signature scheme. Let n be the number of minutes in the the registration current, a Transponder and D engage in the
registration period (e.g., n = 60 ∗ 24 ∗ 365 if the registration following steps:
period is one year). 1) (Determine Tolls) The Transponder and D engage in
At the beginning of each registration period, the Transponder a secure two-party computation to determine the toll
and D perform the following steps. owed based on the intersection between its private
1) (Generate tokens) The Transponder randomly sequence of tokens M = {m1 , . . . , mn } and the
generates a sequence of k-bit token strings, public list of traffic events, Y = {l1 , . . . , l365 }.
{m01,a , m01,b , . . . , m0n,a , m0n,b }, two for each minute 2) (Prove consistency) The Transponder then proves in
of the time period. These are the “digital license zero-knowledge that the tolls computed are correct.
plates” the motorist uses during the registration This is done by proving in zero-knowledge that the
period. The Transponder computes a commitment, commitments in the list C only intersect with Y at
LOCK (m0i,j ) = (αi,j , βi,j ) of each token, and then (me1 , . . . , mek ) and that this intersection was provided
sends the sequence of commitments (α1,a , . . . , αn,b ) as input to the secure two-party computation.
to D. 3) If D accepts the proof, the Transponder pays the tolls
2) (Proof Challenge) For each index i = 1, . . . , n of the and then repeats the Registration process. If any step
registration period, D randomly assigns the variable ci of the protocol is not completed, then the registration
to a or b and then sends to the Transponder a list of renewal is considered to have failed.
requests, (c1 , . . . , cn ).
3) (Proof Response) The Transponder reveals the com-
mitment m0i,ci for each challenge ci requested by We emphasize that our protocols are to be executed sequen-
sending βi,ci . This is a proof that the Transponder tially. In other words, D must perform the Registration and
actually knows each of the tokens that it is register- Renewal process one-at-a-time with each of the Transpon-
ing. Let the sequence of remaining, unopened tokens ders, and the Logger and Transponder should also engage in
be re-labelled M = {m1 , m2 , . . . , mn }, and let the only one interaction at a time. 3
sequence of corresponding commitments be labelled
E. Why Privacy is Preserved
C = {α1 , α2 , . . . , αn }.
4) (Blind Signature) The Transponder and D engage in a Intuitively, the information recorded by a traffic logger
blind signature protocol in order to generate signatures does not identify a vehicle per se. During the initial reg-
for each pair (i, mi ). Let σi denote the signature for istration phase, the registering authority does not learn the
(i, mi ) which the Transponder receives. values of the tokens which are sent, nor its own signatures of
those tokens. It only learns a cryptographic commitment to
Congestion tolling monitoring event the token which hides its value; this value, however, can be
Common Input: D’s public token signing key pk, D’s public used later to guarantee that a motorist pays all of his tolls.
logger signing key pk 0 for a signature scheme. 3 While there are various approaches to proving that a protocol is secure
A traffic logger L records an event at time t involving a in a concurrent setting when D interacts with several Transponders at the
vehicle v as follows: same time, this type of discussion is beyond the scope of this paper.
F. How Tolls are Paid confirm and pay. We may incentivize prompt payment (by
At the end of the billing period, the motorist is required account reconciliation) by price. For example, if a charge is
to reconcile any outstanding tolls owed. During this period, paid (reconciled) with 24 hours of incurring it, the price
the motorist and the registering authority engage in a secure might be p; if paid within one week, it might be 1.5p;
two-party computation to compute the toll. In order to if paid monthly 2p. Drivers could use a public website to
be complete, the motorist must furthermore prove via a reconcile their accounts, or query as to whether they have any
zero-knowledge interaction that all such charges have been unpaid congestion charges outstanding. A variety of payment
acknowledged. A driver who refuses to complete the renewal options could be established, many of them automated, to
protocol can be barred from using the public roads through conform with the individual’s access to credit or preference
traditional mechanisms (i.e., license suspension). for prepaid options.
Spoofing and “man-in-the-middle” attacks. One might be
IV. I MPLEMENTATION concerned that a rogue transponder v1 , while passing another
Various modifications to existing bureaucratic, legal, and transponder v2 , could attempt to read v2 ’s token, and then
technical infrastructure are necessary to implement the passes it off as its own token for that time period. Indeed,
scheme we describe. In our presentation of the protocol, we this type of attack is a serious one.
have outlined the new regulatory behaviors of the registry of For this reason, we require any Logger to authenticate
motor vehicles and the technical behavior of the transpon- itself to the transponder and send the token over an encrypted
ders and loggers. Implicit in this are certain required legal channel. Hence, a rogue reader will be unable to convince a
modifications. Transponder to send its token.
Our general view is that all of the required changes are Additionally, we may legally prohibit Transponders from
eminently reasonable and achievable based on observation broadcasting outside a certain frequency band, and design the
of the experiences of various municipalities in rapidly con- Loggers to send their requests on a different frequency band.
structing infrastructure for automated toll collection. Just (See the next point for how this can be enforced.) Restricting
as in our proposed system, modifications to registration transmission bands also provides protection against attacks
policies, technical infrastructure, and enforcement behaviors in which a malicious transponder sits between a logger and
were necessary to implement these toll collection systems. In another (innocent) transponder, ferrying messages back and
fact, the obstacles to creating such systems were significantly forth.4
greater than the ones our system faces precisely because of Broken Transponder. Suppose the owner of a vehicle
the lack of prior examples. tampers with or disconnects the car transponder when using
the roads. In such a situation, the Traffic logger has no
A. Malicious attacks information to record about this vehicle when it commits
Our system is secure against a variety of malicious attacks. an infraction. We consider this type of attack no different
It is important, however, to be clear about the kinds of than if an individual removes or obscures his license plates.
security guarantees we provide. We can prove that the It is a serious crime to drive without a license plate; it can
mathematical protocols we describe achieve some notion be just as serious to drive without a transponder. We rely
of privacy and guarantee correctness. However, as we are on the classical (and indispensible) presence of the highway
describing a system which must be reified in a physical and patrol in order to solve this problem. Highway patrol officers
bureaucratic implementation, there are of course limits to the can be equipped with devices that monitor whether a vehicle
kinds of guarantees we can expect simply from analysis of has a functioning transponder. Moreover, since the Loggers
the protocols. will receive information that a car without a transponder has
On the other hand, in our situation, we can leverage the passed, a sufficiently dense network of Loggers will allow
power of the “real world” to protect against certain kinds the tracking of such an offending vehicle.
of attacks — for instance, motorists who might choose to Challenges to toll charges. In the current system, disputing
simply remove their transponders altogether face the threat a toll charge requires considerable proof on the part of the
of police enforcement. Cars traveling without emitting the accused that the charge was issued incorrectly. Our system is
requisite radio signals can be tagged as driving without a no different in this respect. One might, however, require the
transponder and fined. Moreover, by restricting the frequency Traffic logger to post calibration information which indicates
bands on which transponders and loggers transmit their proper functioning to a website every day, or to record, along
information, we can prevent various spoofing attacks (see with each tolling event, calibration data which can be used
below). To avoid committing to a particular implementation to support the charges.
technology at this point, our suggestions of this nature should Corrupt registering authority. Since the recorded tokens
be regarded as “qualitative” and necessarily requiring inter- do not contain any private information, every day, each of
pretation in the specific technical context of implementation. the traffic loggers sends its daily event log to a central server.
Outstanding charges. Recall that drivers receive “unoffi-
4 We should note that traditional solutions to this type of man-in-the-
cial” notification from their transponder when a logger has
middle attack do not apply because, although the Logger is “authenticated”
recorded its plate number, and so we imagine that in standard to the Transponder, the requirement for Transponder anonymity makes the
usage following such an event the driver would log on to converse impossible.
This server timestamps the log using a third party time- cash” systems do not preserve sufficient information to
stamping service, and posts the list to a publicly available support general usage pricing schemes. Such a system would
bulletin board (or internet site). This prevents D from however be a plausible means to implement the “tourist
generating false events, after the fact, in order to gather protocol” we sketched above.
information about the location of a vehicle, say at the behest Chaum has also proposed a trusted-hardware model in
of a district attorney involved in a case against a vehicle’s which each smartcard contains a tamper-proof “observer”
owner. chip which is installed and certified by the registering
authority. In this model, credentials can be stored on the
B. Tourists and incremental adoption smartcard. A credential is simply an authorization which has
An essential issue to confront is the handling of sporadic been assigned to its holder. In our contexts, credentials can
motorists, those just passing through a congestion pricing model the right to use a highway at a specific time (only
zone, who have not obtained a registered transponder. Given granted to vehicles traveling under a set speed limit), or
the local nature of decision-making regarding the imple- the right to cross an intersection (only granted when the
mentation of congestion pricing systems, it is highly likely light is green). Verifiers along the entire route can check
that there will be a lengthy period of time in which there whether each vehicle is authorized to travel on that route.
will be a sizeable population of occasional visitors without The problem, however, the process of presenting credentials,
suitable transponders. We will refer to such sporadic users as when repeated a few times, allows the verifier to ”link” the
“tourists”, although we intend to denote a potentially broader credentials of a single vehicle to one another.
class than actual tourists. One wishes to be able to success- Thus, neither of these classes of protocols allow the
fully charge such motorists in a fashion without either unduly implementation of the kind of congestion pricing system we
burdening the tourist (e.g. requiring full participation in the require. More recently, the authors have learned of a paper
transponder registration process) or opening up opportunities by Bangerter, Camenisch, and Lysyanskaya [7] describing
for residents to cheat the system. a framework for anonymous and unlinkable releasing of
The most straightforward solution is to require the tourists ”credential information.” Their protocols, which can perhaps
to purchase a disposable temporary transponder (e.g. a smart be used for certain parts of our system, suggest promising
RFID device) at a gas station or convenience store. How- directions for efficient implementations.
ever, this transponder is not tied to any sort of registration
protocol. Instead, the transponder simply has a fixed cost, VI. C ONCLUSIONS
perhaps the maximum charge for the time period of its We envision a future in which every car has a signal
applicability. The transponder has a crytographically secure transponder and there are virtually ubiquitous state-managed
timestamp and an interval of validity, and as the tourist monitoring devices spread throughout public road space.
vehicle passes a logging device the transponder engages in Drivers will be charged tolls that precisely reflect their
a short interaction proving that the transponder is valid. By usage of public road transporation infrastructure; rather than
equipping the transponder with a long list of timestamped simply congestion pricing for downtown areas, all driving
certificates, this can be done in a fashion which does not will be assessed charges depending on the time, location, and
permit tracking of the tourist vehicle. If full variable tolling vehicle specifications. There are grave and obvious threats
is desired for tourists, the process can be augmented by to the privacy of the individual in such a situation, as
permitting tourists to apply for a rebate by engaging in a standard implementations of such pricing schemes involve
version of the billing protocol. comprehensive monitoring and tracking of each vehicle. We
believe that there is an essential right to “locational privacy”
V. R ELATIONSHIP TO OTHER C RYPTOGRAPHIC for individuals.
P ROTOCOLS FOR T RANSPORTATION It is sometimes argued that the benefits of congestion
Many cryptographic notions have been applied to prob- pricing systems outweight the costs of sacrificing driver
lems in transportation. As early as 1992, David Chaum privacy. One of the main achievements of this paper is to
et.al. [2] proposed and built a prototype anonymous elec- demonstrate that this is an unnecessary choice. We have in-
tronic toll-system, called Dynacash, and installed it in Hol- troduced a protocol which allows the collection of arbitarily
land and in Japan. The critical element of his system involved nuanced variable tolls while guaranteeing the preservation of
smartcard technology which could be “charged up” with locational privacy for individuals. Our protocol is relatively
digital cash, and automatically debited as a vehicle passed straightforward to implement using existing technology, and
a toll-booth. This system is far more respectful of driver robust against various commonplace attacks. The existence
privacy than a system like EZ-Pass, which must record of this protocol serves to demonstrate that it is not necessary
a static special-purpose vehicle ID every time the vehicle to surrender driver privacy in order to achieve sophisticated
passes through a toll-booth. Almost all of the “electronic congestion pricing systems.
cash” technologies that have subsequently been developed
could be employed in this fashion. In such systems, en- VII. ACKNOWLEDGEMENTS
forcement of toll violations must be handled by an external We would like to thank Abhi Shelat for a fruitful previous
mechanism, typically a camera. In addition, such “electronic collaboration which led to this research and Karl Schafer for
useful conversations about the formalization of the idea of
driver privacy. We would also like to express our gratitude
to Razvan Surdulescu for a careful reading of the paper and
useful criticism.
R EFERENCES
[1] T. transportation institute, “Urban mobility information,”
http://mobility.tamu.edu/ums/congestion data/tables/national/table
4.pdf.
[2] D. Chaum, “Blind signatures for untraceable payments,” in CRYPTO
’82, 1982, pp. 199–203.
[3] A. J. Blumberg, L. S. Keeler, and abhi shelat, “Automated traffic
enforcement which preserves driver privacy,” in ITSC 2005, 2005,
vienna, Austria.
[4] J. Camenisch, M. Koprowski, and B. Warinschi, “Efficient blind signa-
tures without random oracles,” in In Forth Conference on Security in
Communication Networks - SCN ’04, 2004.
[5] O. Goldreich, Foundations of Cryptography. Cambridge University
Press, 2004, vol. 2, ch. 7 (General Cryptographic Protocols), pp. 599–
759.
[6] O. Goldreich, S. Micali, and A. Wigderson, “Proofs that yield nothing
but their validity or all languages in NP have zero-knowledge proofs,”
Journal of the ACM, vol. 38, no. 3, 1991.
[7] E. Bangerter, J. Camenisch, and A. Lysyanskaya, “A cryptographic
framework for the controlled release of certified data,” in Twelfth
International Workshop on Security Protocols, Apr 2004, cambridge,
England.