Paper 2012/054

On the performance of certain Private Set Intersection protocols

Emiliano De Cristofaro and Gene Tsudik

Abstract

Private Set Intersection (PSI) is a useful cryptographic primitive that allows two parties (client and server) to interact based on their respective (private) input sets, in such a way that client obtains nothing other than the set intersection, while server learns nothing beyond client set size. This paper considers one PSI construct from [DT10] 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 markedly outperforms the one presented in [HEK12].

Note: This report include work-in-progress and may be occasionally updated.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. A shorter version of this report, titled "Experimenting with Fast Private Set Intersection", appears in the 5th International Conference on Trust and Trustworthy Computing (TRUST 2012).
Contact author(s)
me @ emilianodc com
History
2012-04-07: last of 6 revisions
2012-02-06: received
See all versions
Short URL
https://ia.cr/2012/054
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2012/054,
      author = {Emiliano De Cristofaro and Gene Tsudik},
      title = {On the performance of certain Private Set Intersection protocols},
      howpublished = {Cryptology ePrint Archive, Paper 2012/054},
      year = {2012},
      note = {\url{https://eprint.iacr.org/2012/054}},
      url = {https://eprint.iacr.org/2012/054}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.