CISPA
Browse

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 PuSihang 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.

History

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

2022-05-02

Open Access Type

  • Unknown

BibTeX

@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

    Categories

    No categories selected

    Exports

    RefWorks
    BibTeX
    Ref. manager
    Endnote
    DataCite
    NLM
    DC