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 all desired qualities and free from any undesirable attributes may be a bit idealistic. Meanwhile, the criteria should be expressed in a succinct form. 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. 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 executing a highly-interactive PSI directly with each other. Outsourcing our two protocols are arguably optimal, namely, the two users perform $O(|C|)$ and $O(1)$ decryptions, for unlocking the private set $C$ and the outcome whether a match has been found.