Cryptology ePrint Archive: Report 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.

Category / Keywords: cryptographic protocols, threshold private set intersection

Date: received 14 Feb 2018, last revised 18 Apr 2018

Contact author: zy113 at ie cuhk edu hk

Available format(s): PDF | BibTeX Citation

Version: 20180418:112629 (All versions of this report)

Short URL:

Discussion forum: Show discussion | Start new discussion

[ Cryptology ePrint archive ]