Paper 2018/184

Can you find the one for me? Privacy-Preserving Matchmaking via Threshold PSI

Yongjun Zhao and Sherman S. M. Chow


Private set-intersection (PSI) allows a client to only learn the intersection between his/her set $C$ and the set $S$ of another party, while this latter party learns nothing. We aim to enhance PSI in different dimensions, motivated by the use cases of increasingly popular online matchmaking --- Meeting ``the one'' who possesses \emph{all} desired qualities and \emph{free from any} undesirable attributes may be a bit idealistic. In this paper, we realize \emph{over-} (resp. \emph{below-}) threshold PSI, such that the client learns the intersection (or other auxiliary private data) only when $|C \cap S| > t$ (resp. $\leq t$). The threshold corresponds to tunable criteria for (mis)matching, without marking all possible attributes as desired or not. In other words, the matching criteria are in a succinct form and the matching computation does not exhaust the whole universe of attributes. To the best of our knowledge, our constructions are the very first solution for these two open problems posed by Bradley~\etal (SCN~'16) and Zhao and Chow (PoPETS~'17), without resorting to the asymptotically less efficient generic approach from garbled circuits. Moreover, we consider an ``outsourced'' setting with a service provider coordinating the PSI execution, instead of having two strangers to be online simultaneously for running a highly-interactive PSI directly with each other. Outsourcing our protocols are arguably optimal --- the two users perform $O(|C|)$ and $O(1)$ decryptions, for unlocking the private set $C$ and the outcome of matching.

Note: This is the full version of the paper.

Available format(s)
Publication info
Published elsewhere. MINOR revision.Workshop on Privacy in the Electronic Society (WPES 2018)
cryptographic protocolsthreshold cryptographythreshold private set intersectionapplications
Contact author(s)
foreverjun zhao @ gmail com
2018-08-24: last of 2 revisions
2018-02-20: received
See all versions
Short URL
Creative Commons Attribution


      author = {Yongjun Zhao and Sherman S.  M.  Chow},
      title = {Can you find the one for me? Privacy-Preserving Matchmaking via Threshold PSI},
      howpublished = {Cryptology ePrint Archive, Paper 2018/184},
      year = {2018},
      doi = {10.1145/3267323.3268965},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.