Brown CS Blog

In a large metropolitan area such as NYC, the public transportation system is a vital part of the city's day-to-day operation. But transportation systems do not work for free: each of the millions of passengers they serve must pay for their rides. Let's take a look at their underlying payment systems.

The simplest, and oldest, payment system is with actual cash, tokens, or tickets. One of its advantages is that the passengers do not leave behind an electronic trail of their comings and goings. However, it also has severe limitations: physical payments require cashiers or customized payment booths or turnstiles; it is hard to adapt the system to variable pricing or to collect statistics that lead to better services,

As a result, pre-paid or monthly cards (those that need to be swiped, or sometimes contactless cards) such as MetroCards in NYC and Charlie Cards in Boston have replaced the physical tokens. Contactless devices have also made paying highway tolls easier: systems such as E-ZPass give drivers a device that automatically pays their tolls as they drive through the toll booth.

These convenient systems raise concerns about the privacy of their customers. One’s MetroCard or Charlie Card is a persistent identifier, and the MTA in New York, or MBTA in Boston, has the ability to locate an individual in a large metropolis based on where they’ve used their card. These devices do not necessarily offer security for the transportation authorities either — for example, the Charlie Card was shown vulnerable to forgery by three MIT students doing a class project. Thus, current practices are the worst of both worlds since there are no guarantees for either private or secure payments.

One may argue that giving up one’s privacy is a small price to pay for such important benefits as ease and convenience, not to mention the fact that the information collected can facilitate advanced traveler information dissemination, traffic management, travel time estimation, emergency management, congestion pricing, carbon emissions control, and environmental justice assessments. But is it possible to get the best of both worlds? Can we get the ease and convenience of Metrocards as well as the benefits of data collection without sacrificing privacy?

In theory, there exist cryptographic techniques that make this possible. Electronic cash schemes (e-cash) have all the privacy benefits of actual physical cash. But how can we implement them on constrained devices such as a MetroCard? How do we make them work with the same speed and convenience as non-privacy-preserving MetroCards? How do we preserve the ability to collect the same useful information about traffic patterns, without sacrificing the privacy of individuals?

Pay-As-You-Go (PAYG) is a multi-disciplinary research project funded by the NSF¹ that started in 2010 and seeks to answer these questions. The project includes a diverse team of computer scientists, cryptographers, electrical and computer engineers, and transportation systems researchers from Brown University and the University of Massachusetts. The goal of PAYG is to bridge the gap between theoretical constructions and practical implementations on RFID devices. Starting on the crypto side, we want to construct efficient and provable secure e-cash schemes. On the other end, we want to achieve highly efficient implementations of e-cash in RFID devices that would be appropriate for the transportation scenario. Working from both ends of the problem, the goal of PAYG is to obtain a solution that offers speed and convenience on the one hand, and cryptographic guarantees of security and privacy on the other. By incorporating additional cryptographic techniques, we can derive additional benefits, such as variable pricing and privacy-preserving data collection.

The results of the PAYG project are very promising! On the crypto end we managed to construct a new e-cash scheme [1], to be presented at ACM-CCS 2013, that perfectly suits the purpose of payments in public transportation systems. It is very efficient, has a formal proof of security, and allows the encoding of a user’s attributes (such as age, address, etc.) on the coins/tokens withdrawn which is essential for the transportation setting. Encoding users’ attributes in the coins/tokens allows us to implement additional features in our system such as variable pricing (e.g. reduced fare for senior customers) and privacy-preserving data collection. Our new e-cash scheme is a very exciting development in the e-cash research: previous schemes were either not provably secure or too computationally expensive for scenarios where lightweight devices are used and efficiency is crucial.

On the implementation end, the biggest challenge is the processing time constraints of transportation payment systems. To avoid congestion in front of turnstiles, a payment transaction should take approximately 300 ms which is a considerable challenge given the computational complexity of advanced payment protocols. The efficiency of loading money on one’s payment device is less critical but should also not take longer than a few seconds. Another set of challenges are related to the payment device itself. First, it should be based on inexpensive hardware due to the potentially very high volume and the need to replace payment cards frequently. Second, it should be able to communicate and work contactlessly and without a battery. These two conditions are seemingly in conflict with the need to run very complex cryptographic operations. The results of the PAYG project on the implementation side are also very encouraging.

In a work that was recently presented at Privacy Enhancing Technology Symposium (PETS’13) we implemented our new e-cash scheme using an NFC enabled smartphone [2]. We managed to take advantage of certain elements of the smartphone’s API in order to speed up our implementation. We implemented loading in 300 milliseconds (including terminal, communication and smartphone execution time) and payment in about 380 milliseconds (when two attributes are revealed; less if no attributes were revealed).

In conclusion, our work on the PAYG project shows that private and cryptographically secure payments in public transportation systems are a practical possibility. We managed to use cryptographic techniques that were previously considered prohibitively inefficient for such an application. But, are transportation systems the only possible application area of our results? How can we extend our results to be used in other scenarios where private and efficient transactions are required?

----------------------------------- 

^1: NSF grant numbers: 096464, 0964379.
[1] "Anonymous Credentials Light", Foteini Baldimtsi, Anna Lysyanskaya, ACM Conference on Computer and Communications Security (ACM-CCS), 2013.
[2] "Efficient E-cash in Practice: NFC-based Payments for Intelligent Transportation Systems", Gesine Hinterwälder, Christian T. Zenger, Foteini Baldimtsi, Anna Lysyanskaya, Christof Paar and Wayne P. Burleson, Privacy Enhancing Technologies Symposium - PETS, 2013.