CryptoDB
Laconic Private Set Intersection and Applications
| Authors: | |
|---|---|
| Download: | |
| Abstract: | Consider a server with a \emph{large} set $S$ of strings $\{x_1,x_2\ldots,x_N\}$ that would like to publish a \emph{small} hash $h$ of its set $S$ such that any client with a string $y$ can send the server a \emph{short} message allowing it to learn $y$ if $y \in S$ and nothing otherwise. In this work, we study this problem of two-round private set intersection (PSI) with low (asymptotically optimal) communication cost, or what we call \emph{laconic} private set intersection ($\ell$PSI) and its extensions. This problem is inspired by the recent general frameworks for laconic cryptography [Cho et al. CRYPTO 2017, Quach et al. FOCS'18]. We start by showing the first feasibility result for realizing $\ell$PSI~ based on the CDH assumption, or LWE with polynomial noise-to-modulus ratio. However, these feasibility results use expensive non-black-box cryptographic techniques leading to significant inefficiency. Next, with the goal of avoiding these inefficient techniques, we give a construction of $\ell$PSI~schemes making only black-box use of cryptographic functions. Our construction is secure against semi-honest receivers, malicious senders and reusable in the sense that the receiver's message can be reused across any number of executions of the protocol. The scheme is secure under the $\phi$-hiding, decisional composite residuosity and subgroup decision assumptions. Finally, we show natural applications of $\ell$PSI~to realizing a semantically-secure encryption scheme that supports detection of encrypted messages belonging to a set of ``illegal'' messages (e.g., an illegal video) circulating online. Over the past few years, significant effort has gone into realizing laconic cryptographic protocols. Nonetheless, our work provides the first black-box constructions of such protocols for a natural application setting. |
Video from TCC 2021
BibTeX
@article{tcc-2021-31529,
title={Laconic Private Set Intersection and Applications},
booktitle={Theory of Cryptography;19th International Conference},
publisher={Springer},
doi={10.1007/978-3-030-90456-2_4},
author={Navid Alamati and Pedro Branco and Nico Döttling and Sanjam Garg and Mohammad Hajiabadi and Sihang Pu},
year=2021
}