Experimenting with fast private set intersection

Private Set Intersection (PSI) is a useful cryptographic primitive that allows two parties (client and server) to interact based on their respective private inputs (sets), such that client learns nothing other than the set intersection, while server learns nothing beyond client set size. This paper considers one (arguably, most efficient) PSI construct and reports on its optimized implementation and performance evaluation. Several key implementation choices that significantly impact real-life performance are identified and a comprehensive experimental analysis (including micro-benchmarking, with various input sizes) is presented. Finally, it is shown that our optimized implementation of this RSA-OPRF based PSI protocol from [DT10] markedly outperforms the one presented in [HEK12].

Citation

De Cristofaro, E.; Tsudik, G. Experimenting with fast private set intersection. Fifth International Conference on Trust and Trustworthy Computing; 2012 June 13-15; Vienna, Austria.