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'')
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
Tuesday, October 16, 2007
An overview of a system for implementing congestion pricing that preserves locational privacy
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.
Subscribe to:
Post Comments (Atom)
6 comments:
At the settling-up period, what's to stop Irving from saying "none of these license plates you collected are mine"? It seems to me that Irving can prove if he /did/ enter the congestion zone, but it's not clear how he would prove that he /didn't/.
Hi Robin! Great blog - I look forward to following it.
For a technologically challenged person such as myself, this all gets pretty confusing. Is there a pilot project underway to show that this works? Or if this is all off-the-shelf technology, is there an analogous system already in place that works on similar principles?
On the vistor question and the issue of the person who trys to circumvent the system by driving without a transponder, wouldn't one obvious answer be something analogous to toll booths?
Not a station where everyone has to stop or where everyone is charged, but stations located along the main entry points into a city where police could monitor for non-compliance and where visitors could pick up their transponders?
Anyway, great conversation! I'll plan on following this closely!
All the best,
Brian
Vectro: Irving (or more realistically, a computational device that Irving purchased at Radio Shack) and the DMV together compute the intersection of the plate numbers Irving has and the plate numbers the DMV collected --- if this is empty, then Irving didn't enter the congestion zone. Since Irving gave the DMV a digital signature when he chose the plates, he can't try to disavow the plate numbers he's using.
Brian: This is all essentially off-the-shelf technology, although assembling it as described would be a significant engineering challenge. Then again, so was the implementation of the London system --- any congestion pricing system is going to be a big job. There is not yet a pilot going for this specific system, though; although related technology guards the security of financial transactions every day.
Regarding the toll booth suggestion: sure, that could definitely work. We've been imagining monitoring points all over the place, but strategically placed monitoring stations at major arteries makes a lot of sense as well.
- andrew
Hi Andrew,
In reply to your reply to Vectro's comment, it's still not instantly clear how you would compute the intersection... If you could describe this in detail it would be useful.
It would also be good to describe what happens when two devices happen to randomly generate the same plate, and both get "seen" by the charging system with that same plate.
Finally, IMHO the London system is significantly less complex because it doesn't involve every user having a device.
Thanks!
hi david,
well, unfortunately the short answer to how the computation of the intersection works is "it's complicated". we rely on a cryptographic protocol called a "secure two-party protocol"; but it's hard to say much about how that works in this space. basically, the result is that any computation which can be done by two people and a "trusted third party" can be replaced by one without the trusted party. for example, in this situation, if there was a trusted third party, giving them both irving's list and the DMV's list would clearly enable them to figure out the correct tolls.
for a somewhat more detailed discussion, i'd recommend our paper on the congestion pricing system, which is available here. if you want the real technical background, i like oded goldreich's books on the foundations of cryptography.
regarding plate collision: if that happens, the charges are computed wrong. the probability of this can be made arbitrarily small by choosing large plate numbers (and using a suitable randomness generator), however, and so i tend to regard this as a problem on the order of "the OCR for reading the plate number from the camera failed".
finally, regarding complexity: you're right, there is substantially more "social complexity" in this kind of system. but i think from a technical standpoint (i.e. implementing the software, building the transponders, and so forth) it's perhaps easier or comparable to the challenges in getting the plate recognition system going --- at least based on the reports i heard about the difficulties in london.
thanks for the thoughtful comments.
- andrew
This may actually be even easier. Rather than rely on the Internets, I suggest you think about the mobile phone network, and specifically the GSM network. The GSM network does everything you need to do today, including locational awareness. It's all built-in to the system specs. Privacy and cryptography are also built-in to the system spec.
Post a Comment