Paper 2018/184

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

Yongjun Zhao and Sherman S. M. Chow

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Published elsewhere. Minor revision. Workshop on Privacy in the Electronic Society (WPES 2018)
DOI
10.1145/3267323.3268965
Keywords
cryptographic protocolsthreshold cryptographythreshold private set intersectionapplications
Contact author(s)
foreverjun zhao @ gmail com
History
2018-08-24: last of 2 revisions
2018-02-20: received
See all versions
Short URL
https://ia.cr/2018/184
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2018/184,
      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{https://eprint.iacr.org/2018/184}},
      url = {https://eprint.iacr.org/2018/184}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.