research-article

Cryptographic Theory Meets Practice: Efficient and Privacy-Preserving Payments for Public Transport

Authors:

Andy Rupp,

Foteini Baldimtsi,

Gesine Hinterwälder,

Christof PaarAuthors Info & Claims

ACM Transactions on Information and System Security (TISSEC), Volume 17, Issue 3

Article No.: 10, Pages 1 - 31

https://doi.org/10.1145/2699904

Published: 27 March 2015 Publication History

Get Access

Abstract

We propose a new lightweight cryptographic payment scheme for transit systems, called P4R (Privacy-Preserving Pre-Payments with Refunds), which is suitable for low-cost user devices with limited capabilities. Using P4R, users deposit money to obtain one-show credentials, where each credential allows the user to make an arbitrary ride on the system. The trip fare is determined on-the-fly at the end of the trip. If the deposit for the credential exceeds this fare, the user obtains a refund. Refund values collected over several trips are aggregated in a single token, thereby saving memory and increasing privacy. Our solution builds on Brands’s e-cash scheme to realize the prepayment system and on Boneh-Lynn-Shacham (BLS) signatures to implement the refund capabilities. Compared to a Brands-only solution for transportation payment systems, P4R allows us to minimize the number of coins a user needs to pay for his rides and thus minimizes the number of expensive withdrawal transactions, as well as storage requirements for the fairly large coins. Moreover, P4R enables flexible pricing because it allows for exact payments of arbitrary amounts (within a certain range) using a single fast paying (and refund) transaction. Fortunately, the mechanisms enabling these features require very little computational overhead. Choosing contemporary security parameters, we implemented P4R on a prototyping payment device and show its suitability for future transit payment systems. Estimation results demonstrate that the data required for 20 rides consume less than 10KB of memory, and the payment and refund transactions during a ride take less than half a second. We show that malicious users are not able to cheat the system by receiving a refund that exceeds the overall deposit minus the overall fare and can be identified during double-spending checks. At the same time, the system protects the privacy of honest users in that transactions are anonymous (except for deposits) and trips are unlinkable.

Supplementary Material

a10-rupp-apndx.pdf (rupp.zip)

Supplemental movie, appendix, image and software files for, Cryptographic Theory Meets Practice: Efficient and Privacy-Preserving Payments for Public Transport

Download
86.31 KB

References

[1]

Massachusetts Bay Transportation Authority. 2013. MBTA ScoreCard. Retrieved from http://www.mbta.com/about_the_mbta/scorecard/.

Google Scholar

[2]

Josep Balasch, Alfredo Rial, Carmela Troncoso, Bart Preneel, Ingrid Verbauwhede, and Christophe Geuens. 2010. PrETP: Privacy-preserving electronic toll pricing. In USENIX Security Symposium. USENIX Association, 63--78.

Digital Library

Google Scholar

[3]

Foteini Baldimtsi and Anna Lysyanskaya. 2013a. Anonymous credentials light. In ACM Conference on Computer and Communications Security, Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung (Eds.). ACM, 1087--1098.

Digital Library

Google Scholar

[4]

Foteini Baldimtsi and Anna Lysyanskaya. 2013b. On the security of one-witness blind signature schemes. In ASIACRYPT (2), Kazue Sako and Palash Sarkar (Eds.), Vol. 8270. Springer, 82--99.

Google Scholar

[5]

Mihir Bellare, Juan A. Garay, Ralf Hauser, Amir Herzberg, Hugo Krawczyk, Michael Steiner, Gene Tsudik, Els Van Herreweghen, and Michael Waidner. 2000. Design, implementation, and deployment of the iKP secure electronic payment system. IEEE Journal on Selected Areas in Communications 18 (2000), 611--627.

Digital Library

Google Scholar

[6]

Erik-Oliver Blass, Anil Kurmus, Refik Molva, and Thorsten Strufe. 2009. PSP: Private and secure payment with RFID. In WPES, Ehab Al-Shaer and Stefano Paraboschi (Eds.). ACM, 51--60.

Digital Library

Google Scholar

[7]

Alexandra Boldyreva. 2003. Threshold signatures, multisignatures and blind signatures based on the gap-diffie-hellman-group signature scheme. In Public Key Cryptography, Yvo Desmedt (Ed.), Vol. 2567. Springer, 31--46.

Digital Library

Google Scholar

[8]

Dan Boneh, Ben Lynn, and Hovav Shacham. 2004. Short signatures from the weil pairing. Journal of Cryptology 17, 4 (2004), 297--319.

Digital Library

Google Scholar

[9]

Stefan Brands. 1993a. An Efficient Off-line Electronic Cash System Based on the Representation Problem. Technical Report CS-R9323. CWI.

Digital Library

Google Scholar

[10]

Stefan Brands. 1993b. Untraceable off-line cash in wallets with observers (extended abstract). In CRYPTO, Douglas R. Stinson (Ed.), Vol. 773. Springer, 302--318.

Digital Library

Google Scholar

[11]

Jan Camenisch, Susan Hohenberger, and Anna Lysyanskaya. 2005. Compact E-cash. In EUROCRYPT, Ronald Cramer (Ed.), Vol. 3494. Springer, 302--321.

Digital Library

Google Scholar

[12]

Jan Camenisch, Anna Lysyanskaya, and Mira Meyerovich. 2007. Endorsed E-cash. In IEEE Symposium on Security and Privacy. IEEE Computer Society, 101--115.

Digital Library

Google Scholar

[13]

Jan Camenisch, Jean-Marc Piveteau, and Markus Stadler. 1994. An efficient electronic payment system protecting privacy. In ESORICS, Dieter Gollmann (Ed.), Vol. 875. Springer, 207--215.

Digital Library

Google Scholar

[14]

Sébastien Canard and Aline Gouget. 2007. Divisible E-cash systems can be truly anonymous. In EUROCRYPT, Moni Naor (Ed.), Vol. 4515. Springer, 482--497.

Digital Library

Google Scholar

[15]

Agnes Hui Chan, Yair Frankel, Philip D. MacKenzie, and Yiannis Tsiounis. 1996. Mis-representation of identities in E-cash schemes and how to prevent it. In ASIACRYPT, Kwangjo Kim and Tsutomu Matsumoto (Eds.), Vol. 1163. Springer, 276--285.

Digital Library

Google Scholar

[16]

David Chaum. 1982. Blind signatures for untraceable payments. In CRYPTO, David Chaum, Ronald L. Rivest, and Alan T. Sherman (Eds.). Plenum Press, New York, 199--203.

Google Scholar

[17]

Bram Cohen. 2001. AES-hash. Retrieved from http://csrc.nist.gov/groups/ST/toolkit/BCM/documents/proposedmodes/aes-hash/aeshash.pdf.

Google Scholar

[18]

Jeremy Day, Yizhou Huang, Edward Knapp, and Ian Goldberg. 2011. SPEcTRe: Spot-checked private ecash tolling at roadside. In WPES, Yan Chen and Jaideep Vaidya (Eds.). ACM, 61--68.

Digital Library

Google Scholar

[19]

Morris Dworkin. 2005. Recommendation for Block Cipher Modes of Operation: The CMAC Mode for Authentication. (May 2005). http://csrc.nist.gov/publications/nistpubs/800-38B/SP_800-38B.pdf.

Google Scholar

[20]

E-ZPass. 2013. E-ZPass. Retrieved from http://www.e-zpassiag.com/.

Google Scholar

[21]

Matthias Enzmann, Marc Fischlin, and Markus Schneider. 2004. A privacy-friendly loyalty system based on discrete logarithms over elliptic curves. In Financial Cryptography, Ari Juels (Ed.), Vol. 3110. Springer, 24--38.

Google Scholar

[22]

Marc Fischlin, Anja Lehmann, and Dominique Schröder. 2012. History-free sequential aggregate signatures. In SCN, Ivan Visconti and Roberto De Prisco (Eds.), Vol. 7485. Springer, 113--130.

Digital Library

Google Scholar

[23]

Oded Goldreich. 2001. The Foundations of Cryptography - Volume 1, Basic Techniques. Cambridge University Press.

Digital Library

Google Scholar

[24]

Nils Gura, Arun Patel, Arvinderpal Wander, Hans Eberle, and Sheueling Chang Shantz. 2004. Comparing elliptic curve cryptography and RSA on 8-bit CPUs. In CHES, Marc Joye and Jean-Jacques Quisquater (Eds.), Vol. 3156. Springer, 119--132.

Google Scholar

[25]

Christina Hager. 2007. Divorce Lawyers Using Fast Lane to Track Cheaters. Retrieved from http://msl1.mit.edu/furdlog/docs/2007-08-10_wbz_fastlane_tracking.pdf.

Google Scholar

[26]

Thomas S. Heydt-Benjamin, Hee-Jin Chae, Benessa Defend, and Kevin Fu. 2006. Privacy for public transportation. In Privacy Enhancing Technologies, George Danezis and Philippe Golle (Eds.), Vol. 4258. Springer, 1--19.

Digital Library

Google Scholar

[27]

Gesine Hinterwälder, Christof Paar, and Wayne P. Burleson. 2012. Privacy preserving payments on computational RFID devices with application in intelligent transportation systems. In RFIDSec, Vol. 7739. Springer, 109--122.

Digital Library

Google Scholar

[28]

Gesine Hinterwälder, Christian T. Zenger, Foteini Baldimtsi, Anna Lysyanskaya, Christof Paar, and Wayne P. Burleson. 2013. Efficient E-cash in practice: NFC-based payments for public transportation systems. In Privacy Enhancing Technologies, Emiliano De Cristofaro and Matthew Wright (Eds.), Vol. 7981. Springer, 40--59.

Google Scholar

[29]

Tibor Jager and Andy Rupp. 2010. The semi-generic group model and applications to pairing-based cryptography. In ASIACRYPT, Vol. 6477. Springer, 539--556.

Crossref

Google Scholar

[30]

Florian Kerschbaum, Hoon Wei Lim, and Ivan Gudymenko. 2013. Privacy-preserving billing for e-ticketing systems in public transportation. In WPES, Ahmad-Reza Sadeghi and Sara Foresti (Eds.). ACM, 143--154.

Digital Library

Google Scholar

[31]

Massachusetts Bay Transportation Authority. 2013. MBTA Charlie Card. Retrieved from http://www.mbta.com/fares_and_passes/charlie/.

Google Scholar

[32]

Sarah Meiklejohn, Keaton Mowery, Stephen Checkoway, and Hovav Shacham. 2011. The phantom tollbooth: Privacy-preserving electronic toll collection in the presence of driver collusion. In USENIX Security Symposium. USENIX Association.

Digital Library

Google Scholar

[33]

Nicolas Meloni. 2007. New point addition formulae for ECC applications. In WAIFI, Claude Carlet and Berk Sunar (Eds.), Vol. 4547. Springer, 189--201.

Digital Library

Google Scholar

[34]

Peter L. Montgomery. 1987. Speeding the pollard and elliptic curve methods of factorization. Mathematics of Computation 48, 177 (1987), 243--264.

Crossref

Google Scholar

[35]

Karsten Nohl, David Evans, Starbug, and Henryk Plotz. 2008. Reverse-engineering a cryptographic RFID tag. In 17th USENIX Security Symposium. USENIX Association, 185--194.

Digital Library

Google Scholar

[36]

Christian Paquin. 2013. U-Prove Cryptographic Specification V1.1 (Revision 3). Technical Report. Microsoft Research.

Google Scholar

[37]

Jin Park, Jeong-Tae Hwang, and Young-Chul Kim. 2005. FPGA and ASIC implementation of ECC processor for security on medical embedded system. In ICITA (2). IEEE Computer Society, 547--551.

Digital Library

Google Scholar

[38]

Raluca A. Popa, Hari Balakrishnan, and Andrew J. Blumberg. 2009. VPriv: Protecting privacy in location-based vehicular services. In USENIX Security Symposium. USENIX Association, 335--350.

Digital Library

Google Scholar

[39]

Certicom Research. 2000. Standards for Efficient Cryptography -- SEC 2: Recommended Elliptic Curve Domain Parameters. Retrieved from http://www.secg.org/collateral/sec2_final.pdf.

Google Scholar

[40]

Patrick F. Riley. 2008. The tolls of privacy: An underestimated roadblock for electronic toll collection usage. Computer Law & Security Report 24, 6 (2008), 521--528.

Crossref

Google Scholar

[41]

Andy Rupp, Gesine Hinterwälder, Foteini Baldimtsi, and Christof Paar. 2013. P4R: Privacy-preserving pre-payments with refunds for transportation systems. In Financial Cryptography, Ahmad-Reza Sadeghi (Ed.), Vol. 7859. Springer, 205--212.

Google Scholar

[42]

Ahmad-Reza Sadeghi, Ivan Visconti, and Christian Wachsmann. 2008. User privacy in transport systems based on RFID E-tickets. In PiLBA (CEUR Workshop Proceedings), Claudio Bettini, Sushil Jajodia, Pierangela Samarati, and Xiaoyang Sean Wang (Eds.), Vol. 397. CEUR-WS.org.

Google Scholar

[43]

Claus-Peter Schnorr. 1989. Efficient identification and signatures for smart cards. In CRYPTO, Gilles Brassard (Ed.), Vol. 435. Springer, 239--252.

Digital Library

Google Scholar

[44]

Issai J. Schur. 1926. Zur additiven Zahlentheorie. Sitzungsberichte Preussische Akad. Wiss. (1926), 488--495.

Google Scholar

[45]

Victor Shoup. 1997. Lower bounds for discrete logarithms and related problems. In EUROCRYPT, Walter Fumy (Ed.), Vol. 1233. Springer, 256--266.

Digital Library

Google Scholar

[46]

Trans Link Systems. 2014. OV-Chipkaart. Retrieved from https://www.ov-chipkaart.nl/.

Google Scholar

[47]

Hong Zhang, Jeremy Gummeson, Benjamin Ransford, and Kevin Fu. 2011. Moo: A Batteryless Computational RFID and Sensing Platform. Retrieved from https://web.cs.umass.edu/publication/docs/2011/UM-CS-2011-020.pdf.

Google Scholar

Cited By

View all

Zhan YYuan FShi RShi GDong C(2024)PriTKT: A Blockchain-Enhanced Privacy-Preserving Electronic Ticket System for IoT DevicesSensors10.3390/s2402049624:2(496)Online publication date: 13-Jan-2024
https://doi.org/10.3390/s24020496
Chakraborty RMondal UDebnath AGhosh URoy B(2023)Lightweight micro-architecture for IoT & FPGA securityInternational Journal of Information Technology10.1007/s41870-023-01460-y15:7(3899-3905)Online publication date: 5-Sep-2023
https://doi.org/10.1007/s41870-023-01460-y
Eskandarian S(2021)Fast Privacy-Preserving Punch CardsProceedings on Privacy Enhancing Technologies10.2478/popets-2021-00482021:3(289-307)Online publication date: 27-Apr-2021
https://doi.org/10.2478/popets-2021-0048
Show More Cited By

Index Terms

Cryptographic Theory Meets Practice: Efficient and Privacy-Preserving Payments for Public Transport

Recommendations

A fair e-cash payment scheme based on credit
ICEC '05: Proceedings of the 7th international conference on Electronic commerce

A new fair e-cash payment scheme based on credit is present in this paper. In the scheme, an overdraft credit certificate is issued to user by bank. Using the overdraft credit certificate, user can produce e-cash himself to pay in exchanges. Merchant ...
Platypus: A Central Bank Digital Currency with Unlinkable Transactions and Privacy-Preserving Regulation
CCS '22: Proceedings of the 2022 ACM SIGSAC Conference on Computer and Communications Security

Due to the popularity of blockchain-based cryptocurrencies, the increasing digitalization of payments, and the constantly reducing role of cash in society, central banks have shown an increased interest in deploying central bank digital currencies (...
Traversing Bitcoin's P2P network: insights into the structure of a decentralised currency

Lots of existing work addresses the analysis of Bitcoin's publicly available transaction graph. There are evaluations of the user's anonymity and privacy, but no proper measurements of the underlying network. This paper presents novel insights about ...

Reviews

Reviewer: Amos O Olagunju

Electronic devices for executing transactions in real time for applications such as transit systems and vending machines require safekeeping mechanisms for users. But how should customers who use low-cost devices with scarce storage securely perform transactions on systems with imperfect instantaneous processing power__?__ Rupp and colleagues offer cryptographic ideas for effectively preserving the privacy of customers who use devices with insufficient storage and processing time to carry out transactions in public transportation systems. Readers unfamiliar with the Diffie-Hellman key exchanges, the reliability of the discrete logarithm, the applications of zero-knowledge proofs, and Galois fields should browse the concepts of these security protocols in Trappe and Washington [1], prior to exploring the assumptions and proofs of the trustworthy algorithms for providing security in real-world application systems in this paper. The authors present a privacy-preserving payment for public transportation system (P4TS) with voyage go-ahead voucher (VGAV), reimbursement estimation ticket (RET), and repayment token (RT) subsystems. The users in P4TS purchase tickets from an offline VGAV subsystem. The VGAV subsystem encodes the identification of each user on each ticket. Each user inserts a ticket into a reader at an access gate, applies a zero-knowledge proof to validate his/her identity to gain entrance into the P4TS, and receives a stamped RET that contains the date and time, reader identification, and message authentication code of the VGAV. At the exit gate, the user submits the RET and an RT to a reader. The reader computes the trip fare and transfers any balance to the RT for reimbursement at a vending machine. Test results from the prototype implementation of the P4TS reveal that (1) the display of a VGAV and obtaining an RET can be efficiently executed on some devices; (2) the time to obtain a refund is more costly; and (3) buying trip tokens consumes more processing time due to the elliptic curve cryptography used in this project. Nevertheless, the performance of the P4TS has a constant runtime for all withdrawal and spending fares, as opposed to the linear time growth of the well-known Brands's e-cash algorithm. Clearly, the paper presents reliable probabilistic algorithms and security protocols that enable users to enroll with the VGAV subsystem, use tokens, and receive accurate refunds from the P4TS. The authors provide convincing lemmas and formal proofs to illustrate the security of the VGAV, RET, and RT subsystems. I strongly encourage all database and user security experts to read and weigh in on the insightful and practical safekeeping ideas in this paper. Online Computing Reviews Service

Access critical reviews of Computing literature here

Become a reviewer for Computing Reviews.

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

ACM Transactions on Information and System Security Volume 17, Issue 3

March 2015

124 pages

ISSN:1094-9224

EISSN:1557-7406

DOI:10.1145/2744298

Editor:
Gene Tsudik
University of California at Irvine, USA

Issue’s Table of Contents

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected].

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 27 March 2015

Accepted: 01 October 2014

Revised: 01 July 2014

Received: 01 January 2014

Published in TISSEC Volume 17, Issue 3

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article
Research
Refereed

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
600
Total Downloads

Downloads (Last 12 months)12
Downloads (Last 6 weeks)4

Reflects downloads up to 16 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Zhan YYuan FShi RShi GDong C(2024)PriTKT: A Blockchain-Enhanced Privacy-Preserving Electronic Ticket System for IoT DevicesSensors10.3390/s2402049624:2(496)Online publication date: 13-Jan-2024
https://doi.org/10.3390/s24020496
Chakraborty RMondal UDebnath AGhosh URoy B(2023)Lightweight micro-architecture for IoT & FPGA securityInternational Journal of Information Technology10.1007/s41870-023-01460-y15:7(3899-3905)Online publication date: 5-Sep-2023
https://doi.org/10.1007/s41870-023-01460-y
Eskandarian S(2021)Fast Privacy-Preserving Punch CardsProceedings on Privacy Enhancing Technologies10.2478/popets-2021-00482021:3(289-307)Online publication date: 27-Apr-2021
https://doi.org/10.2478/popets-2021-0048
Chow SLi MZhao YJin W(2021)Sipster: Settling IOU Privately and Quickly with Smart MetersProceedings of the 37th Annual Computer Security Applications Conference10.1145/3485832.3488029(219-234)Online publication date: 6-Dec-2021
https://dl.acm.org/doi/10.1145/3485832.3488029
Li ZAlazab MGarg SHossain M(2021)PriParkRec: Privacy-Preserving Decentralized Parking Recommendation ServiceIEEE Transactions on Vehicular Technology10.1109/TVT.2021.307482070:5(4037-4050)Online publication date: May-2021
https://doi.org/10.1109/TVT.2021.3074820
Hatzivasilis GPapadakis NHatzakis IIoannidis SVardakis G(2020)Artificial Intelligence-Driven Composition and Security Validation of an Internet of Things EcosystemApplied Sciences10.3390/app1014486210:14(4862)Online publication date: 15-Jul-2020
https://doi.org/10.3390/app10144862
Bobolz JEidens FKrenn SSlamanig DStriecks CSun HShieh SGu GAteniese G(2020)Privacy-Preserving Incentive Systems with Highly Efficient Point-CollectionProceedings of the 15th ACM Asia Conference on Computer and Communications Security10.1145/3320269.3384769(319-333)Online publication date: 5-Oct-2020
https://dl.acm.org/doi/10.1145/3320269.3384769
Anwar NRasjidin RNajoan DRolando CTamimmanar Warnars H(2020)E-payment for Jakarta Smart Public Transportation, Using the Point System for E-CommerceJournal of Physics: Conference Series10.1088/1742-6596/1477/2/0220351477(022035)Online publication date: 15-Apr-2020
https://doi.org/10.1088/1742-6596/1477/2/022035
Han JChen LSchneider STreharne HWesemeyer S(2019)Privacy-Preserving Electronic Ticket Scheme with Attribute-Based CredentialsIEEE Transactions on Dependable and Secure Computing10.1109/TDSC.2019.2940946(1-1)Online publication date: 2019
https://doi.org/10.1109/TDSC.2019.2940946
Dimitriou TGiannetsos TChen L(2019)REWARDS: Privacy-preserving rewarding and incentive schemes for the smart electricity grid and other loyalty systemsComputer Communications10.1016/j.comcom.2019.01.009Online publication date: Feb-2019
https://doi.org/10.1016/j.comcom.2019.01.009
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Cited By

Index Terms

Recommendations

A fair e-cash payment scheme based on credit

Platypus: A Central Bank Digital Currency with Unlinkable Transactions and Privacy-Preserving Regulation

Traversing Bitcoin's P2P network: insights into the structure of a decentralised currency

Reviews

Access critical reviews of Computing literature here