International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

Laconic Private Set Intersection and Applications

Authors:
Navid Alamati
Pedro Branco
Nico Döttling
Sanjam Garg
Mohammad Hajiabadi
Sihang Pu
Download:
DOI: 10.1007/978-3-030-90456-2_4
Search ePrint
Search Google
Abstract: Consider a server with a \emph{large} set S of strings {x1,x2…,xN} 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∈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 (ℓ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 ℓ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 ℓ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 ϕ-hiding, decisional composite residuosity and subgroup decision assumptions. Finally, we show natural applications of ℓ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
}