Paper 2018/120

Efficient Circuit-based PSI via Cuckoo Hashing

Benny Pinkas, Thomas Schneider, Christian Weinert, and Udi Wieder


While there has been a lot of progress in designing efficient custom protocols for computing Private Set Intersection (PSI), there has been less research on using generic Multi-Party Computation (MPC) protocols for this task. However, there are many variants of the set intersection functionality that are not addressed by the existing custom PSI solutions and are easy to compute with generic MPC protocols (e.g., comparing the cardinality of the intersection with a threshold or measuring ad conversion rates). Generic PSI protocols work over circuits that compute the intersection. For sets of size $n$, the best known circuit constructions conduct $O(n \log n)$ or $O(n \log n / \log\log n)$ comparisons (Huang et al., NDSS'12 and Pinkas et al., USENIX Security'15). In this work, we propose new circuit-based protocols for computing variants of the intersection with an almost linear number of comparisons. Our constructions are based on new variants of Cuckoo hashing in two dimensions. We present an asymptotically efficient protocol as well as a protocol with better concrete efficiency. For the latter protocol, we determine the required sizes of tables and circuits experimentally, and show that the run-time is concretely better than that of existing constructions. The protocol can be extended to a larger number of parties. The proof technique for analyzing Cuckoo hashing in two dimensions is new and can be generalized to analyzing standard Cuckoo hashing as well as other new variants of it.

Note: Fix description of private intersection-sum protocol (Ion et al., Cryptology ePrint Report 2017/738).

Available format(s)
Cryptographic protocols
Publication info
A major revision of an IACR publication in EUROCRYPT 2018
Private Set IntersectionSecure Computation
Contact author(s)
weinert @ encrypto cs tu-darmstadt de
2019-01-24: last of 2 revisions
2018-01-31: received
See all versions
Short URL
Creative Commons Attribution


      author = {Benny Pinkas and Thomas Schneider and Christian Weinert and Udi Wieder},
      title = {Efficient Circuit-based PSI via Cuckoo Hashing},
      howpublished = {Cryptology ePrint Archive, Paper 2018/120},
      year = {2018},
      doi = {10.1007/978-3-319-78372-7_5},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.