POBA: Privacy-Preserving Operator-Side Bookkeeping and Analytics
Authors
Dennis Faut, Valerie Fetzer, Jörn Müller-Quade, Markus Raiber, Andy Rupp
Dennis Faut
Karlsruhe Institute of Technology, Karlsruhe, Germany
University of Luxembourg, Esch-sur-Alzette, Luxembourg
dennis dot faut at kit dot edu
University of Luxembourg, Esch-sur-Alzette, Luxembourg
dennis dot faut at kit dot edu
Valerie Fetzer
Karlsruhe Institute of Technology, Karlsruhe, Germany
valerie dot fetzer at kit dot edu
valerie dot fetzer at kit dot edu
Jörn Müller-Quade
Karlsruhe Institute of Technology, Karlsruhe, Germany
joern dot mueller-quade at kit dot edu
joern dot mueller-quade at kit dot edu
Markus Raiber
Karlsruhe Institute of Technology, Karlsruhe, Germany
markus dot raiber at kit dot edu
markus dot raiber at kit dot edu
Andy Rupp
University of Luxembourg, Esch-sur-Alzette, Luxembourg
KASTEL Security Research Labs, Karlsruhe, Germany
andy dot rupp at uni dot lu
KASTEL Security Research Labs, Karlsruhe, Germany
andy dot rupp at uni dot lu
Keywords:
Analytics
Bookkeeping
Building-Block
MPC
Protocols
Privacy
Provable Security
UC
Universal Composability
Abstract
Many user-centric applications face a common privacy problem: the need to collect, store, and analyze sensitive user data. Examples include check-in/check-out based payment systems for public transportation, charging/discharging electric vehicle batteries in smart grids, coalition loyalty programs, behavior-based car insurance, and more. We propose and evaluate a generic solution to this problem. More specifically, we provide a formal framework integrating privacy-preserving data collection, storage, and analysis, which can be used for many different application scenarios, present an instantiation, and perform an experimental evaluation of its practicality.
We consider a setting where multiple operators (e.g., different mobility providers, different car manufacturers and insurance companies), who do not fully trust each other, intend to maintain and analyze data produced by the union of their user sets. The data is collected in an anonymous (wrt. all operators) but authenticated way and stored in so-called user logbooks. In order for the operators to be able to perform analyses at any time without requiring user interaction, the logbooks are kept on the operator's side. Consequently, this potentially sensitive data must be protected from unauthorized access. To achieve this, we combine several selected cryptographic techniques, such as threshold signatures and oblivious RAM. The latter ensures that user anonymity is protected even against memory access pattern attacks.
To the best of our knowledge, we provide and evaluate the first generic framework that combines data collection, operator-side data storage, and data analysis in a privacy-preserving manner, while providing a formal security model, a UC-secure protocol, and a full implementation. With three operators, our implementation can handle over two million new logbook entries per day.
References
[AG20]
D. F. Aranha and C. P. L. Gouvêa. RELIC is an Efficient LIbrary for Cryptography. https://github.com/relic-toolkit/relic. 2020.
[AGJ+22]
Surya Addanki, Kevin Garbe, Eli Jaffe, Rafail Ostrovsky, and Antigoni Polychroniadou. Prio+: Privacy Preserving Aggregate Statistics via Boolean Shares. In Clemente Galdi and Stanislaw Jarecki, editors, SCN 22: 13th International Conference on Security in Communication Networks, volume 13409 of Lecture Notes in Computer Science, pages 516–539. September 2022. Springer, Cham. DOI: 10.1007/978-3-031-14791-3_23
[ALF+14]
Man Ho Au, Joseph K. Liu, Junbin Fang, Zoe L. Jiang, Willy Susilo, and Jianying Zhou. A New Payment System for Enhancing Location Privacy of Electric Vehicles. IEEE Transactions on Vehicular Technology, 63(1):3-18, 2014. DOI: 10.1109/TVT.2013.2274288
[ALT+15]
Ghada Arfaoui, Jean-François Lalande, Jacques Traoré, Nicolas Desmoulins, Pascal Berthomé, and Saïd Gharout. A Practical Set-Membership Proof for Privacy-Preserving NFC Mobile Ticketing. Proceedings on Privacy Enhancing Technologies, 2015(2):25–45, April 2015. DOI: 10.1515/popets-2015-0019
[APR21]
Diego F. Aranha, Elena Pagnin, and Francisco Rodríguez-Henríquez. LOVE a Pairing. In Patrick Longa and Carla Ràfols, editors, Progress in Cryptology - LATINCRYPT 2021: 7th International Conference on Cryptology and Information Security in Latin America, volume 12912 of Lecture Notes in Computer Science, pages 320–340, Bogotá, Colombia. October 2021. Springer, Cham. DOI: 10.1007/978-3-030-88238-9_16
[BBC+21]
Dan Boneh, Elette Boyle, Henry Corrigan-Gibbs, Niv Gilboa, and Yuval Ishai. Lightweight Techniques for Private Heavy Hitters. In 2021 IEEE Symposium on Security and Privacy, pages 762–776. May 2021. IEEE Computer Society Press. DOI: 10.1109/SP40001.2021.00048
[BDN18]
Dan Boneh, Manu Drijvers, and Gregory Neven. Compact Multi-signatures for Smaller Blockchains. In Thomas Peyrin and Steven Galbraith, editors, Advances in Cryptology – ASIACRYPT 2018, Part II, volume 11273 of Lecture Notes in Computer Science, pages 435–464. December 2018. Springer, Cham. DOI: 10.1007/978-3-030-03329-3_15
[BGL+23]
James Bell, Adrià Gascón, Tancrède Lepoint, Baiyu Li, Sarah Meiklejohn, Mariana Raykova, and Cathie Yun. ACORN: Input Validation for Secure Aggregation. In Joseph A. Calandrino and Carmela Troncoso, editors, USENIX Security 2023: 32nd USENIX Security Symposium, pages 4805–4822. August 2023. USENIX Association.
[BLS01]
Dan Boneh, Ben Lynn, and Hovav Shacham. Short Signatures from the Weil Pairing. In Colin Boyd, editor, Advances in Cryptology – ASIACRYPT 2001, volume 2248 of Lecture Notes in Computer Science, pages 514–532. December 2001. Springer, Berlin, Heidelberg. DOI: 10.1007/3-540-45682-1_30
[BN06]
Paulo S. L. M. Barreto and Michael Naehrig. Pairing-Friendly Elliptic Curves of Prime Order. In Bart Preneel and Stafford Tavares, editors, SAC 2005: 12th Annual International Workshop on Selected Areas in Cryptography, volume 3897 of Lecture Notes in Computer Science, pages 319–331. August 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11693383_22
[BPRS23]
Lennart Braun, Mahak Pancholi, Rahul Rachuri, and Mark Simkin. Ramen: Souper Fast Three-Party Computation for RAM Programs. In Weizhi Meng, Christian Damsgaard Jensen, Cas Cremers, and Engin Kirda, editors, ACM CCS 2023: 30th Conference on Computer and Communications Security, pages 3284–3297. November 2023. ACM Press. DOI: 10.1145/3576915.3623115
[Can00]
Ran Canetti. Universally Composable Security: A New Paradigm for Cryptographic Protocols. Cryptology ePrint Archive, Report 2000/067. 2000.
[Can20]
Ran Canetti. Universally Composable Security. J. ACM, 67(5), September 2020. DOI: 10.1145/3402457
[CB17]
Henry Corrigan-Gibbs and Dan Boneh. Prio: Private, Robust, and Scalable Computation of Aggregate Statistics. In Aditya Akella and Jon Howell, editors, 14th USENIX Symposium on Networked Systems Design and Implementation, NSDI 2017, Boston, MA, USA, March 27-29, 2017, pages 259–282. 2017. USENIX Association.
[CHB+24]
Ying Chen, Debiao He, Zijian Bao, Min Luo, and Kim-Kwang Raymond Choo. A Post-Quantum Privacy-Preserving Payment Protocol in Vehicle to Grid Networks. IEEE Transactions on Intelligent Vehicles, 2024. DOI: 10.1109/TIV.2024.3374724
[DPRS23]
Hannah Davis, Christopher Patton, Mike Rosulek, and Phillipp Schoppmann. Verifiable Distributed Aggregation Functions. Proceedings on Privacy Enhancing Technologies, 2023(4):578–592, October 2023. DOI: 10.56553/popets-2023-0126
[DT08]
Ivan Damgard and Rune Thorbek. Efficient Conversion of Secret-shared Values Between Different Fields. Cryptology ePrint Archive, Report 2008/221. 2008.
[EG14]
Alex Escala and Jens Groth. Fine-Tuning Groth-Sahai Proofs. In Hugo Krawczyk, editor, PKC 2014: 17th International Conference on Theory and Practice of Public Key Cryptography, volume 8383 of Lecture Notes in Computer Science, pages 630–649. March 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-54631-0_36
[EPK14]
Úlfar Erlingsson, Vasyl Pihur, and Aleksandra Korolova. RAPPOR: Randomized Aggregatable Privacy-Preserving Ordinal Response. In Gail-Joon Ahn, Moti Yung, and Ninghui Li, editors, ACM CCS 2014: 21st Conference on Computer and Communications Security, pages 1054–1067. November 2014. ACM Press. DOI: 10.1145/2660267.2660348
[FKM+22]
Valerie Fetzer, Marcel Keller, Sven Maier, Markus Raiber, Andy Rupp, and Rebecca Schwerdt. PUBA: Privacy-Preserving User-Data Bookkeeping and Analytics. Proceedings on Privacy Enhancing Technologies, 2022(2):447–516, April 2022. DOI: 10.2478/popets-2022-0054
[FOSZ23]
Brett Hemenway Falk, Rafail Ostrovsky, Matan Shtepel, and Jacob Zhang. GigaDORAM: Breaking the Billion Address Barrier. In Joseph A. Calandrino and Carmela Troncoso, editors, USENIX Security 2023: 32nd USENIX Security Symposium, pages 3871–3888. August 2023. USENIX Association.
[FPE16]
Giulia C. Fanti, Vasyl Pihur, and Úlfar Erlingsson. Building a RAPPOR with the Unknown: Privacy-Preserving Learning of Associations and Data Dictionaries. Proceedings on Privacy Enhancing Technologies, 2016(3):41–61, July 2016. DOI: 10.1515/popets-2016-0015
[Gol04]
Oded Goldreich. The Foundations of Cryptography - Volume 2: Basic Applications. Cambridge University Press 2004. DOI: 10.1017/CBO9780511721656
[Gol87]
Oded Goldreich. Towards a Theory of Software Protection and Simulation by Oblivious RAMs. In Alfred Aho, editor, 19th Annual ACM Symposium on Theory of Computing, pages 182–194. May 1987. ACM Press. DOI: 10.1145/28395.28416
[Gro06]
Jens Groth. Simulation-Sound NIZK Proofs for a Practical Language and Constant Size Group Signatures. In Xuejia Lai and Kefei Chen, editors, Advances in Cryptology – ASIACRYPT 2006, volume 4284 of Lecture Notes in Computer Science, pages 444–459. December 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11935230_29
[GS08]
Jens Groth and Amit Sahai. Efficient Non-interactive Proof Systems for Bilinear Groups. In Nigel P. Smart, editor, Advances in Cryptology – EUROCRYPT 2008, volume 4965 of Lecture Notes in Computer Science, pages 415–432. April 2008. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-540-78967-3_24
[Gud14]
Ivan Gudymenko. A Privacy-Preserving E-Ticketing System for Public Transportation Supporting Fine-Granular Billing and Local Validation. In Proceedings of the 7th International Conference on Security of Information and Networks, pages 101–108, New York, NY, USA. 2014. Association for Computing Machinery. DOI: 10.1145/2659651.2659706
[HCDF06]
Thomas S. Heydt-Benjamin, Hee-Jin Chae, Benessa Defend, and Kevin Fu. Privacy for Public Transportation. In George Danezis and Philippe Golle, editors, PET 2006: 6th International Workshop on Privacy Enhancing Technologies, volume 4258 of Lecture Notes in Computer Science, pages 1–19. June 2006. Springer, Berlin, Heidelberg. DOI: 10.1007/11957454_1
[HCS+21]
Jinguang Han, Liqun Chen, Steve Schneider, Helen Treharne, and Stephan Wesemeyer. Privacy-Preserving Electronic Ticket Scheme with Attribute-Based Credentials. IEEE Transactions on Dependable and Secure Computing, 18(4):1836-1849, 2021. DOI: 10.1109/TDSC.2019.2940946
[HJ12]
Dennis Hofheinz and Tibor Jager. Tightly Secure Signatures and Public-Key Encryption. In Reihaneh Safavi-Naini and Ran Canetti, editors, Advances in Cryptology – CRYPTO 2012, volume 7417 of Lecture Notes in Computer Science, pages 590–607. August 2012. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-32009-5_35
[JJQ07]
Oliver Jorns, Oliver Jung, and Gerald Quirchmayr. A Privacy Enhancing Service Architecture for Ticket-based Mobile Applications. In The Second International Conference on Availability, Reliability and Security (ARES'07), pages 139-146. 2007. DOI: 10.1109/ARES.2007.16
[Kel20]
Marcel Keller. MP-SPDZ: A Versatile Framework for Multi-Party Computation. In Jay Ligatti, Xinming Ou, Jonathan Katz, and Giovanni Vigna, editors, ACM CCS 2020: 27th Conference on Computer and Communications Security, pages 1575–1590. November 2020. ACM Press. DOI: 10.1145/3372297.3417872
[KLG13]
Florian Kerschbaum, Hoon Wei Lim, and Ivan Gudymenko. Privacy-Preserving Billing for e-Ticketing Systems in Public Transportation. In Proceedings of the 12th ACM Workshop on Workshop on Privacy in the Electronic Society, pages 143–154, New York, NY, USA. November 2013. Association for Computing Machinery. DOI: 10.1145/2517840.2517848
[Kob87]
Neal Koblitz. Elliptic Curve Cryptosystems. Mathematics of Computation, 48(177):203, January 1987. DOI: 10.2307/2007884
[KS14]
Marcel Keller and Peter Scholl. Efficient, Oblivious Data Structures for MPC. In Palash Sarkar and Tetsu Iwata, editors, Advances in Cryptology – ASIACRYPT 2014, Part II, volume 8874 of Lecture Notes in Computer Science, pages 506–525. December 2014. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-662-45608-8_27
[LP09]
Yehuda Lindell and Benny Pinkas. Secure Multiparty Computation for Privacy-Preserving Data Mining. Journal of Privacy and Confidentiality, 1(1):59–98, April 2009. DOI: 10.29012/jpc.v1i1.566
[MDD16]
Luca Melis, George Danezis, and Emiliano De Cristofaro. Efficient Private Statistics with Succinct Sketches. In ISOC Network and Distributed System Security Symposium – NDSS 2016. February 2016. The Internet Society. DOI: 10.14722/ndss.2016.23175
[MDND15]
Milica Milutinovic, Koen Decroix, Vincent Naessens, and Bart De Decker. Privacy-Preserving Public Transport Ticketing System. In Pierangela Samarati, editor, Data and Applications Security and Privacy XXIX, pages 135–150, Cham. 2015. Springer International Publishing. DOI: 10.1007/978-3-319-20810-7_9
[MMS+24]
Aikaterini Mitrokotsa, Sayantan Mukherjee, Mahdi Sedaghat, Daniel Slamanig, and Jenit Tomy. Threshold Structure-Preserving Signatures: Strong and Adaptive Security Under Standard Assumptions. In Qiang Tang and Vanessa Teague, editors, PKC 2024: 27th International Conference on Theory and Practice of Public Key Cryptography, Part I, volume 14601 of Lecture Notes in Computer Science, pages 163–195. April 2024. Springer, Cham. DOI: 10.1007/978-3-031-57718-5_6
[MST24]
Dimitris Mouris, Pratik Sarkar, and Nektarios Georgios Tsoutsos. PLASMA: Private, Lightweight Aggregated Statistics against Malicious Adversaries. Proceedings on Privacy Enhancing Technologies, 2024(3):4–24, July 2024. DOI: 10.56553/popets-2024-0064
[RD11]
Alfredo Rial and George Danezis. Privacy-preserving smart metering. In Yan Chen and Jaideep Vaidya, editors, Proceedings of the 10th annual ACM workshop on Privacy in the electronic society, WPES 2011, Chicago, IL, USA, October 17, 2011, pages 49–60. 2011. ACM. DOI: 10.1145/2046556.2046564
[RDK18]
Alfredo Rial, George Danezis, and Markulf Kohlweiss. Privacy-preserving smart metering revisited. Int. J. Inf. Sec., 17(1):1–31, 2018. DOI: 10.1007/S10207-016-0355-8
[RHBP13]
Andy Rupp, Gesine Hinterwälder, Foteini Baldimtsi, and Christof Paar. P4R: Privacy-Preserving Pre-Payments with Refunds for Transportation Systems. In Ahmad-Reza Sadeghi, editor, FC 2013: 17th International Conference on Financial Cryptography and Data Security, volume 7859 of Lecture Notes in Computer Science, pages 205–212. April 2013. Springer, Berlin, Heidelberg. DOI: 10.1007/978-3-642-39884-1_17
[SG02]
Victor Shoup and Rosario Gennaro. Securing Threshold Cryptosystems against Chosen Ciphertext Attack. Journal of Cryptology, 15(2):75–96, March 2002. DOI: 10.1007/s00145-001-0020-9
[SNF+19]
Rebecca Schwerdt, Matthias Nagel, Valerie Fetzer, Tobias Gräf, and Andy Rupp. P6V2G: a privacy-preserving V2G scheme for two-way payments and reputation. Energy Inform., 2(S1), 2019. DOI: 10.1186/S42162-019-0075-1
[SvDS+13]
Emil Stefanov, Marten van Dijk, Elaine Shi, Christopher W. Fletcher, Ling Ren, Xiangyao Yu, and Srinivas Devadas. Path ORAM: an extremely simple oblivious RAM protocol. In Ahmad-Reza Sadeghi, Virgil D. Gligor, and Moti Yung, editors, ACM CCS 2013: 20th Conference on Computer and Communications Security, pages 299–310. November 2013. ACM Press. DOI: 10.1145/2508859.2516660
[VCPM10]
Arnau Vives-Guasch, Jordi Castellà-Roca, M. Magdalena Payeras-Capella, and Macià Mut-Puigserver. An electronic and secure automatic fare collection system with revocable anonymity for users. In Proceedings of the 8th International Conference on Advances in Mobile Computing and Multimedia, pages 387–392, New York, NY, USA. 2010. Association for Computing Machinery. DOI: 10.1145/1971519.1971585
[WMK16]
Xiao Wang, Alex J. Malozemoff, and Jonathan Katz. EMP-toolkit: Efficient MultiParty computation toolkit. https://github.com/emp-toolkit. 2016.
[WZL+22]
Zhiguo Wan, Tong Zhang, Weizhuang Liu, Mingqiang Wang, and Liehuang Zhu. Decentralized Privacy-Preserving Fair Exchange Scheme for V2G Based on Blockchain. IEEE Transactions on Dependable and Secure Computing, 19(4):2442-2456, 2022. DOI: 10.1109/TDSC.2021.3059345
[YBY+24]
Xiaohan Yue, Xue Bi, Haibo Yang, Shi Bai, and Yuan He. PAP: A Privacy-Preserving Authentication Scheme With Anonymous Payment for V2G Networks. IEEE Transactions on Smart Grid, 15(6):6092-6111, 2024. DOI: 10.1109/TSG.2024.3435028
[ZCWY14]
Tianyu Zhao, Chang Chen, Lingbo Wei, and Mengke Yu. An Anonymous Payment System to Protect the Privacy of Electric Vehicles. In 2014 Sixth International Conference on Wireless Communications and Signal Processing (WCSP), pages 1–6. October 2014. DOI: 10.1109/WCSP.2014.6992208
PDF
History
Submitted: 2025-01-14
Accepted: 2025-06-02
Published: 2025-07-07
Accepted: 2025-06-02
Published: 2025-07-07
How to cite
Dennis Faut, Valerie Fetzer, Jörn Müller-Quade, Markus Raiber, and Andy Rupp, POBA: Privacy-Preserving Operator-Side Bookkeeping and Analytics. IACR Communications in Cryptology, vol. 2, no. 2, Jul 07, 2025, doi: 10.62056/av11zo-3y.
License
Copyright is held by the author(s)
This work is licensed under a Creative Commons Attribution (CC BY) license.