Paper 2021/728

Laconic Private Set Intersection and Applications

Navid Alamati, Pedro Branco, Nico Döttling, Sanjam Garg, Mohammad Hajiabadi, and Sihang Pu


Consider a server with a large set $S$ of strings $\{x_1,x_2, \dots,x_N\}$ that would like to publish a small hash $h$ of its set $S$ such that any client with a string $y$ can send the server a 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 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.

Available format(s)
Public-key cryptography
Publication info
A minor revision of an IACR publication in TCC 2021
Laconic oblivious transferprivate set intersection
Contact author(s)
pmbranco @ math tecnico ulisboa pt
alamati @ gmail com
nico doettling @ gmail com
sanjamg @ berkeley edu
mdhajiabadi @ uwaterloo ca
push beni @ gmail com
2021-09-17: revised
2021-06-02: received
See all versions
Short URL
Creative Commons Attribution


      author = {Navid Alamati and Pedro Branco and Nico Döttling and Sanjam Garg and Mohammad Hajiabadi and Sihang Pu},
      title = {Laconic Private Set Intersection and Applications},
      howpublished = {Cryptology ePrint Archive, Paper 2021/728},
      year = {2021},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.