Distributed Privacy-Preserving Policy Reconciliation
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 (policy) reconciliation protocols. In such a protocol, two or more parties each have private inputs ordered according to their individual preferences. The desired output of a distributed privacypreserving reconciliation protocol then is a set of common elements that maximize the joint preferences without revealing anything but the desired output to the parties and without involving any trusted third party. Joining the individual preferences here means combining the individual orders on the input sets to a pre-order on the intersection of input sets. Applications of privacy-preserving reconciliation protocols include policy reconciliation, electronic voting, auctions, and scheduling applications. Within the project we developed privacy-preserving reconciliation protocols for different ways to join the individual preferences of the users. We developed two-party, as well as multiparty protocols secure in the semi-honest, as well as the malicious adversary model. Our protocols make use of privacy-preserving (multi-)set operations as building blocks. All of our protocols were implemented as part of a large library, which by know contains implementations of cryptographic primitives (in particular homomorphic cryptosystems, zero-knowledge proofs, and commitment schemes) privacy-preserving building blocks (e.g., privacy-preserving twoparty and multi-party (multi-)set operations, oblivious transfer protocols), as well as the implementations of our newly developed privacy-preserving reconciliation protocols and scheduling applications built on top of our protocols. In addition, we designed and implemented a support infrastructure for secure multi-party computation that facilitates key distribution and the coordination of communication between the participating parties, while keeping their inputs and computations private. In order be able to comprehensively evaluate our implementations in a structured way, we developed CaPTIF (Comprehensive Performance TestIng Framework) a framework that allows for the specification of well-defined test inputs, the scheduling and execution, as well as the plotting, browsing and analysis of comprehensive performance tests. We also developed novel privacy-preserving building blocks for new set operations as well as interval operations: In particular this includes a multiset membership test, a submultiset test, and a difference operation. The new interval operations are: privacy-preserving protocols for determining whether two intervals overlap, computing the boundaries of the overlap interval, calculating (only) the size of the overlap, determining if the overlap has at least a certain size, and determining a random subintervall of a specific size within the overlap. During our work on reconciliation protocols we recognized the importance of the end users’ attitude towards privacy and in particular towards what should be kept private and how much convenience users are willing to sacrifice for more privacy. We therefore conducted a pilot user study on privacy-preserving reconciliation on the example of scheduling appointments and electronic auctions. We redesigned the user study after evaluating the initial results. This revised user study provides us with very valuable feedback on our work.
Publications
- Fair and Privacy-Preserving Multi-Party Protocols for Reconciling Ordered Input Sets. In Information Security Conference (ISC), volume 6531 of LNCS. Springer, 2010
G. Neugebauer, U. Meyer, and S. Wetzel
- Enabling Fair and Privacy-Preserving Applications Using Reconciliation Protocols on Ordered Sets. In Sarnoff Symposium. IEEE, 2011
D. A. Mayer, G. Neugebauer, U. Meyer, and S. Wetzel
- Design and Implementation of Privacy- Preserving Reconciliation Protocols. In International Workshop on Privacy and Anonymity in the Information Society (PAIS). ACM, 2013
G. Neugebauer, L. Brutschy, U. Meyer, and S. Wetzel
- Privacy-Preserving Multi-Party Reconciliation Secure in the Malicious Model. In International Workshop on Data Privacy Management (DPM). ACM, 2013
G. Neugebauer, L. Brutschy, U. Meyer, and S. Wetzel
- Privacy-Preserving Multi-Party Reconciliation using Fully Homomorphic Encryption. In International Conference on Network and System Security (NSS), volume 7645 of LNCS. Springer, 2013
F. Weingarten, G. Neugebauer, U. Meyer, and S. Wetzel
- Design and Implementation of Efficient Multi-Party Protocols for Privacy-Preserving Reconciliation. PhD Thesis, RWTH Aachen University, Aaachen, 2014
G. Neugebauer
