Implementation and performance evaluation of privacy-preserving fair reconciliation protocols on ordered sets

Recently, new protocols were proposed which allow two parties to reconcile their ordered input sets in a fair and privacy-preserving manner. In this paper we present the design and implementation of these protocols on different platforms and extensively study their performance. In particular, we present the design of a library for privacy-preserving reconciliation protocols and provide details on an efficient C++ implementation of this design. Furthermore, we present details on the implementation of a privacy-preserving iPhone application built on top of this library. The performance of both the library and the iPhone application are comprehensively analyzed. Our performance tests show that it is possible to efficiently implement private set intersection as a generic component on a desktop computer. Furthermore, the tests confirm the theoretically determined quadratic worst-case behavior of the privacy-preserving reconciliation protocols on the desktop as well as the iPhone platform. The main result of the performance analysis is that the protocols show linear runtime performance for average-case inputs. This is a significant improvement over the worst-case and is key for making these protocols highly viable for a wider range of applications in practice.