Privacy-Preserving Bartering

• Applicant: Professorin Dr.-Ing. Ulrike Meyer
• Subject Area: Security and Dependability, Operating-, Communication- and Distributed Systems
• Term: from 2015 to 2020
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 279353706

• Final Report Year: 2020

Final Report Abstract

This project was carried out jointly between RWTH Aachen University and Stevens Institute of Technology and was independently funded by the DFG and the NSF. In the project, we designed, implemented, and evaluated privacy-preserving bartering protocols in a two-party as well as a multi-party setting. In addition, we designed and simulated a bartering system that is able to make use of these protocols in a privacy-enhancing fashion. In our bartering protocols, each party specifies (one or more) private input quotes consisting of an offered and a demanded commodity and an upper or lower limit on the quantities thereof. The desired output of a distributed privacy-preserving bartering protocol then is a list of trade partners for each party including the commodities and quantities to receive from or give to these trade partners. The protocols are not to reveal anything but this desired output (and what can be deduced from the combination of own private input and desired output) to the parties and do not involve any trusted third party. Within the project we developed privacy-preserving bartering protocols that are able to maximize any welfare function and are able to support any probability distributions on the quantities to trade. We developed two-party, as well as multi-party protocols secure in the semi-honest, as well as protocols secure in the malicious adversary model, supporting single as well as multiple non-competing quotes. Our protocols make use of existing and novel privacy-preserving building blocks. These include various protocols for conditional random selection in the two-party as well as the multiparty setting, a two-party protocol that allows for performing a less-than operation on two encrypted bits while providing XOR-shared output, a multi-party protocol that allows for random sampling from an interval according to an arbitrary discrete probability distribution (secure in the malicious model), and a protocol that allows for oblivious shrinking of an interval if the width of the interval is beyond a certain threshold (secure in the malicious model). These building blocks are of interest independent of the bartering context. All protocols and building blocks designed have been proven to be secure in the respective security model. Each of the protocols and building blocks were implemented as part of a large library, which by now contains implementations of cryptographic primitives (in particular homomorphic cryptosystems, zero-knowledge proofs, and commitment schemes), privacy-preserving building blocks, as well as the implementations of our newly developed privacypreserving bartering protocols. In addition, we designed a privacy-preserving bartering system and implemented a simulation model for this system which allows us to estimate the cost induced by adding privacy to a bartering system. In a follow-up project we now explore how we can build on top of the newly designed protocols and the new bartering system developed as part of this project to introduce privacy in the context of organ donor exchanges.

Publications

• Privacy-Preserving Two-Party Bartering Secure Against Active Adversaries. 14th Annual Conference on Privacy, Security and Trust (PST), IEEE, 2016
  S. Wüller, W. Pessin, U. Meyer, S. Wetzel
  
• Designing Privacy-Preserving Interval Operations Based on Homomorphic Encryption and Secret Sharing. Journal of Computer Security, IOS Press, 2017
  S. Wüller, D. Mayer, F. Förg, S. Schüppen, B. Assadsolimani, U. Meyer, S. Wetzel
  
• Privacy-Preserving Multi-Party Bartering Secure Against Active Adversaries. 15th Annual Conference on Privacy, Security and Trust (PST), IEEE, 2017
  S. Wüller, U. Meyer, S. Wetzel
  
• Towards Privacy-Preserving Multi-Party Bartering. 5th Workshop on Encrypted Computing and Applied Homomorphic Cryptography (WAHC), ACM, 2017
  S. Wüller, U. Meyer, S. Wetzel
  
• Using Secure Graph Algorithms for the Privacy-Preserving Identification of Optimal Bartering Opportunities. Workshop on Privacy in the Electronic Society (WPES), ACM, 2017
  S. Wüller, M. Vu, U. Meyer, S. Wetzel
  
• Privacy-Preserving Subgraph Checking. 16th Annual Conference on Privacy, Security and Trust (PST), IEEE, 2018
  S. Wüller, B. Assadsolimani, U. Meyer, and S. Wetzel
  
• Privacy-Preserving Trade Chain Detection. 13th International Workshop on Data Privacy Management (DPM), co-located with 23rd European Symposium on Research in Computer Security (ESORICS), LNCS 11025, Springer, 2018
  S. Wüller, M. Breuer, U. Meyer, S. Wetzel
  
• Privacy-Preserving Multi-Party Conditional Random Selection. 17th Annual Conference on Privacy, Security and Trust (PST), Fredericton, Canda, IEEE, 2019
  S. Wüller, F. Förg, B. Assadsolimani, U. Meyer, S. Wetzel