File(s) not publicly available

Laconic Private Set Intersection and Applications

conference contribution
posted on 2023-11-29, 18:18 authored by Navid Alamati, Pedro Branco, Nico DöttlingNico Döttling, Sanjam Garg, Mohammad Hajiabadi, Sihang Pu
Consider a server with a large set S of strings {????1,????2…,????????} 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 ????∈???? 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 (ℓ 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.


Preferred Citation

Navid Alamati, Pedro Branco, Nico Döttling, Sanjam Garg, Mohammad Hajiabadi and Sihang Pu. Laconic Private Set Intersection and Applications. In: Theory of Cryptography Conference (TCC). 2021.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Theory of Cryptography Conference (TCC)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3632, title = "Laconic Private Set Intersection and Applications", author = "Alamati, Navid and Branco, Pedro and Döttling, Nico and Garg, Sanjam and Hajiabadi, Mohammad and Pu, Sihang", booktitle="{Theory of Cryptography Conference (TCC)}", year="2021", }

Usage metrics


    No categories selected


    Ref. manager