Protecting location privacy of drivers

As background to this one. you might want to read the more general article we just wrote for the Huffington Post on why we call for a national dialogue about (and promise for) location privacy. Below are some specific ways we might technically provide location privacy in for cars.

We start with what we consider to be the gold standard:

A privacy-preserving taxing protocol should reveal the minimum possible amount of information needed to achieve the policy goal, in this case the amount of tax owed.

Most current systems (e.g., E-ZPass) operate on the "trust us" model:
the government promises to properly respect the security of the driver, but collects potentially invasive information. But we all know, there just aren’t any “trusted third parties” that can be trusted forever. And we don’t need to rely on them.

For some kinds of applications, simply having a tamper-resistant device in the car that calculates the tolls and reports only the amount owed would suffice. Such a device could be auditable (so that drivers could know that the device is not secretly delivering information about their position) and equipped with a self-destruct feature (to erase location information) so that the driver could hide her information if necessary (perhaps at a cost of paying an excessive "default toll").

But wouldn't it be great if the tolling and traffic software could run on any smartphone? For this kind of setup, there are more sophisticated solutions available. One of the truly amazing aspects of modern cryptography is that it makes it possible to design protocols for mutually untrusting parties to act as if there is a trusted third-party mediating, without actually requiring such a third-party. For instance, electronic cash allows people to pay bills anonymously and untraceably, but in a way that assures merchants that they are actually getting paid (it's hard to forge). Anonymous credential systems allow individuals to prove that they are authorized to access certain data or enter particular areas without revealing their identity. We need to demand that these sorts of protections are required and part of any future road pricing systems.

Cryptographic protocols can be designed to allow the government to collect taxes, detect infractions, and record aggregate traffic statistics without violating the privacy of drivers. For a more comprehensive discussion of such solutions, see here. The big contractors likely to be involved in designing and implementing the road pricing systems (e.g., IBM and Siemens) have on staff some of the finest cryptographers in the world. Requiring such protections would pose no substantial obstacle to the technical adoption of a mileage-based system.

This post was co-authored by Andrew Blumberg.

Photo by Gerlos.

Read more!

An overview of a system for implementing congestion pricing that preserves locational privacy

Our proposal for an implementation of a congestion pricing system that preserves locational privacy depends on the idea of "secret dynamic license plates.'' Here's how the system would process the interaction of a driver ("Irving'') and the state toll collection agency ("the DMV'')

At the beginning of the year, Irving privately chooses a collection of "secret dynamic license plates.'' This is just a long list of very large numbers, chosen in such a way so as to minimize the probability of overlap with any other driver's list.

Irving digitally signs the list of license plates, and gives the signature, but not the secret list of license plates, to the DMV.

As Irving drives around, the transponder in his car rapidly cycles through the list of dynamic license plates, at the rate of a new number each second.

When Irving enters the congestion pricing zone, monitoring devices record his current dynamic license plate number as he drives past.

At the end of the billing period, Irving settles with the DMV via the following process:

The DMV has a long list of numbers collected from drivers who have incurred tolls in the congestion pricing zone.

Irving has a long list of secret dynamic license plate numbers, some of which were picked up by the DMV's monitoring devices as he drove past.

Irving and the DMV engage in a secure two-party computation of the charges Irving owes the DMV.

At the end of the secure two-party computation, the DMV has not learned Irving's license plate numbers, only the amount Irving owes (see below for a discussion of how this works). Because the DMV has the signature Irving created when he chose the secret dynamic plate numbers, the DMV can be sure that Irving is paying the tolls accrued by his own secret dynamic plate numbers, even though it doesn't know what those numbers are.

This protocol preserves Irving's locational privacy. The information collected by the DMV does not personally identify Irving, nor does it allow them to actively track his vehicle. Nonetheless, complicated tolling information can be computed accurately during the final interaction. As a further advantage, this kind of implementation integrates well with solutions to automated traffic enforcement (e.g. stoplight cameras to catch red-light violators) that already preserve locational privacy.

Some answers to technical questions about the implementation:

Q: What's a "secure two-party computation"?
A: A protocol for "secure two-party computation" is a modern cryptographic technique which solves the following kind of problem: I have a secret number, and you have a secret number. We want to compute the product of these numbers, but I don't want you to learn my secret and you don't want me to learn your secret. A "secure two-party computation" allows us to compute the product of both numbers without revealing either secret.

Q: This sounds like magic. How could it possibly work?
A: Well, it's complicated. This technology is closely related to the modern cryptographic tools that make secure internet purchases possible (e.g., https) and make ATM's safe for banking. Besides, everyone engages in a very familiar privacy-preserving computation --- voting! After I vote, even though my vote can be used to decide who wins the election, no one knows how I voted. Secure two-party computations work via analogous principles.

Q: How does the state know that Irving isn't lying about the secret list of license plates he chose when this protocol started?
A: That's the point of the digital signature that Irving gave at the beginning --- using it, the DMV can verify that Irving is telling the truth (via another secure two-party interaction).

Q: How does a digital signature work?
A: It produces a number associated with some piece of information (a list of license plates, for instance) that uniquely identifies that list without revealing any other information about it. Imagine that I have a "secret number'', and I tell you the sum of the digits but not the number itself. It would be very hard for me to change my number without altering this sum. Digital signatures work a little like this, only much more securely.

Some more answers to pragmatic questions about the system:

As a general response to concerns about enforcement and potential attempts to defeat this system, it's worth pointing out that the existing situation involving physical license plates is the current gold standard for traffic enforcement. If I physically removed my license plates from my car, it might take a while for the police to catch me, because enforcement would depend solely on visual detection by a passing police officer. Because this system employs many eyes (the system's monitoring devices) in conjunction with the eyes of law enforcement, toll violators should be even easier to catch than someone driving without a physical license plate.

Q: This seems enormously complicated. Won't it be really difficult to implement?
A: It is somewhat complicated; but so was the London congestion pricing system (which is still plagued by high costs associated with collecting the tolls). But all of the hardware we require is basically bootstrapped from existing devices; most of the innovation is in the software. And the basic software for the modern cryptographic tools already exists.

Q: Is each person really responsible for picking a huge list of dynamic license plates and then engaging in this complicated interaction to pay tolls?
A: Well, yes, but drivers will be able to obtain devices that perform these tasks automatically.

Q: What if I try to fool the system by leaving my transponder at home?
A: Just as the police stop people driving without license plates on their cars, they will be able to stop people driving through the congestion pricing zone without transponders. Furthermore, the tolling points can report that a "transponder-less'' car has gone through, alerting local law enforcement.

Q: What happens if I choose not to engage in a periodic interaction to pay my tolls?
A: Drivers already engage in periodic, enforceable interactions with the state to, for example, renew their registrations. Drivers who haven't reconciled their congestion tolls could have their registrations revoked. The state might provide financial incentives to encourage early settlements of toll bills. Or the transponders could be equipped with a time-stamped authorization to operate, which expires at intervals and is renewed as part of the bill-settling process.

Q: Does this mean everyone has to have a transponder?
A: Yes.

Q: What about tourists and people "just passing through''?
A: Tourists and other legitimate sporadic users can pick up transponders at gas stations, convenience stores, and rest areas and leave a deposit in addition to charging up the device. On exiting the congestion charging area, these transponders can be returned and the deposit and congestion pricing balance credited back to the driver. These prepaid transponders would likely not preserve locational privacy, although they could be designed to do so.

Q: How could the system be integrated with automatic traffic enforcement?
A: Once the "secret dynamic license plates'' infrastructure is in place, it's easy to build traffic enforcement systems (or retrofit existing ones) that respect locational privacy. For instance, when a stop-light violation is detected, the vehicle's current dynamic license plate could be recorded rather than the physical license plate. Once again, via a secure two-party computation, tickets can be assessed.

Q: Do we really want freight trucks to be anonymous?
A: This system is designed primarily for passenger cars on personal business. Freight trucks engaged in commercial shipping probably should be closely monitored and tracked at all times. The point of this system is to preserve the locational privacy of private citizens using personal vehicles, while at the same time allowing the collection of congestion tolls and other traffic-management fees.

Authors of this posting are Andrew J. Blumberg, Department of Mathematics, Stanford University, Stanford, CA 94305, email blumberg @ math.stanford.edu and Robin Chase, Meadow Networks, email robin @ meadownetworks.com

Read more!

How to make EZ-pass preserve locational privacy

In many ways, the EZ-pass system of automated toll collection devices on highways, tunnels, and bridges throughout the Northeast has been a huge success. Penetration is impressive: A majority of drivers now have the devices. But the system has the potential to substantially compromise its users' privacy.

The signal sent out by the EZ-pass transponder is unencrypted and could be read by anyone. Each transponder is uniquely linked to a particular credit card account. The states maintain databases of EZ-pass tolling data for indefinite periods of time. Uniform standards for access and use of this data do not exist. This data may be subject to demands by other private citizens, and has been successfully subpoenaed as evidence establishing the locations of alleged philanderers in divorce cases. In sum, as implemented, EZ-pass violates the locational privacy of its users.

There's no reason the system must expose its users to locational privacy violations. Over a decade ago, automated highway tolling systems which did preserve locational privacy were successfully implemented, notably David Chaum's Dynacash in Holland and Japan. Dynacash and others were based on one of the fruits of modern cryptography -- electronic cash.

Q: What's electronic cash?
A: Electronic cash functions like ordinary cash, but it is "virtual'' and stored in a computer. To use it, I go to a virtual "bank'' and buy some electronic cash using "real'' money. Later, I spend the electronic cash on goods and services. The vendor can then redeem it for "real'' money with the bank.

Q: What does "function like ordinary cash'' mean?
A: When I give you a twenty dollar bill, you know you were paid. You can exchange that bill with other people. But once that bill is in circulation, no one knows who gave it to you. Once I've given it away, that bill is gone. And I can't tell just by looking at my remaining money where that particular bill went. Finally, the bank that originally provided the specific bill never knows whether I spent it or to whom I gave it.

Q: How would this work in the toll-collection context?
A: Users would purchase electronic cash and use it "charge up'' their EZ-pass transponders. The transponder then pays tollbooths using the electronic cash. From the user's perspective, there would be almost no change in how EZ-pass works.

Q: But the bank knows I bought the electronic cash. Isn't my privacy violated?
A: No. Even if you buy the electronic cash from the state, the state knows only that at the beginning of the month a certain amount of money was purchased to be used for tolls -- not which tollbooths were used.

Q: This seems like magic. Does this really work?
A: Yes. In fact, electronic cash systems are widely used for internet purchases. And electronic cash based tolling systems were implemented temporarily in Holland and Japan in the early 90's. Modern cryptography is amazing. We trust it every day to secure our use of the internet (via https) and ATM machines. Modern cryptographic techniques have been proposed to help ensure the safety of electronic voting. Electronic cash is based on the same kind of technology.

Q: Could we use electronic cash to implement congestion pricing?
A: For simple congestion pricing systems, definitely! For instance, if a proposed congestion pricing plan charges a fixed amount to anyone who comes within a set boundary drawn around the downtown district during business hours, electronic cash would work well. But it doesn't work as well for more nuanced systems (e.g., the charge depends on the amount of driving within the downtown boundary), and it doesn't integrate well with privacy-preserving automated traffic enforcement solutions. For a richer approach to congestion pricing which preserves locational privacy, see our other posting.

Authors of this posting are Andrew J. Blumberg, Department of Mathematics, Stanford University, Stanford, CA 94305, email blumberg @ math.stanford.edu and Robin Chase, Meadow Networks, email robin @ meadownetworks.com

Read more!

Congestion pricing poses a threat to locational privacy.

What this means and why you should care

Q: What does "locational privacy" mean?
A: "Locational privacy" means the ability to walk in public space and drive on public roads with the expectation that one's movements are not being tracked or recorded for later analysis.


Q: How will congestion pricing violate my locational privacy?
A: Congestion pricing systems track drivers in order to charge them for their road usage. In practice, congestion pricing systems use pervasive networks of cameras and electronic tag readers to charge drivers and catch violators. Some proposed systems require a GPS transmitter in every car to assess charges based on the car's recorded path. Almost all of the designs in use or under consideration require the tolling authority to build a giant database of tracking information that includes data for each driver who uses the congestion pricing zone.

Q: Aren't law enforcement agencies allowed to track my movements already? How is congestion pricing different?
A: The police have limited resources to devote to tracking your movements. As a consequence, they can't afford to track very many people at once. Besides, it's hard for the police to track you without your knowledge -- even if an unmarked car is following you, you'll probably become aware of it sooner or later. With a congestion pricing system, by contrast, a widespread network of inexpensive data-collection devices silently records everyone's movements in a central log, without anyone noticing. This quantitative difference in the ease of tracking and exploiting the collected data creates a huge qualitative difference in the tracking's impact. It's like wiretapping: there's a critical qualitative difference between single wiretaps that require a court order and disclosure, and the government secretly recording all phone calls for subsequent analysis.

Q: Don't EZ-Pass and similar existing electronic tolling systems already violate my locational privacy this way?
A: YES! The tolling data collected by EZ-Pass is linked to a credit card account (without being encoded to protect your privacy) and then stored in a single central location. In contrast, "electronic cash''-based highway tolling systems which preserve locational privacy have been deployed in the past, but are not widespread today.

Q: Won't the government keep the data safe and delete it as soon as it's no longer needed?
A: No. Many states keep EZ-Pass tolling data indefinitely, for example, and such data has already been (successfully) subpoenaed for use in divorce cases. Tolling authorities will be tempted to keep the data for ostensibly reasonable "law and order'' purposes.

Q: What kinds of tracking data misuse should we be afraid of?
A: It's easy to imagine civil-rights abuses based on data-mining. For instance, people who are tracked driving to a mosque might be referred to the FBI for careful observation. People who are tracked visiting the Riverdale Democratic clubhouse could be singled out for audits by the IRS. Neither of these examples is farfetched --- reports of officers recording the license plate numbers of cars parked at mosques are fairly widespread, and All Souls church in Pasadena was investigated by the IRS and threatened with revocation of its tax-exempt status based on an anti-war sermon delivered in 2004. And of course, such data could be used to pursue illegal immigrants. In addition to actual government abuses, the reasonable fear that visits to such locations might be tracked, stored and used later could have a chilling effect on legitimate political and religious expression.

Q: I frequently provide a lot of identifying information about my physical location --- for instance, to my credit card company. Why is this any worse?
A: It's hard to interact with the modern financial world without leaving a trace. And if you have a cell phone, you're probably already trackable by your cell phone company. But that doesn't make it right. The slow but steady erosion of locational privacy is a good reason to be concerned about further loss of privacy. Anyway, if you're worried about privacy, it's much easier to switch to cash, or turn off your cell phone occasionally, than to stop driving. Furthermore, these two examples involve the use of your data by private corporations, which -- unlike the government -- have no power to arrest you or take away your rights.

Q: Pervasive tracking of all vehicles will provide needed security in this age of terrorism. Shouldn't we be willing to sacrifice this kind of privacy for security?
A: No. We should no more have to sacrifice locational privacy for security than we should have to consent to the deprivation of any other rights. Residents of former Eastern bloc countries have written eloquently about the horrors of pervasive monitoring and surveillance. Even if it were reasonable to have cameras constantly watching high-risk areas (Wall Street, courthouses, and so forth), congestion pricing will cover the city and eventually the whole metropolitan area, and pervasive surveillance everywhere is fundamentally incompatible with a free and democratic society.

Q: Driving is privilege, not a right. Why shouldn't we demand the sacrifice of privacy in return for that privilege?
A: Particularly in areas that are poorly served by mass transit, it's such a hardship to refrain from driving that there's no reasonable way to opt out. In those situations, this proposition is coercive. As an analogy, suppose we demanded that people whose homes are connected to public sewer lines allow cameras in their bathrooms to track water usage. But there's really no need to use cameras for the purpose of monitoring water usage --- and the same is true of congestion pricing (see the next question).

Q: But we need congestion pricing systems to alleviate downtown traffic problems. What alternatives do we have?
A: There are ways of designing congestion pricing systems that preserve locational privacy! Using modern cryptography, a congestion pricing system could simultaneously protect our locational privacy and allow tolling authorities to collect revenue. This is the same technology that makes it safe to use ATMs or buy things online. See our other documents for more information on how this could work.

Authors of this posting are Andrew J. Blumberg, Department of Mathematics, Stanford University, Stanford, CA 94305, email blumberg @ math.stanford.edu and Robin Chase, Meadow Networks, email robin @ meadownetworks.com

Read more!