## Cryptology ePrint Archive: Report 2021/728

Laconic Private Set Intersection and Applications

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

Abstract: 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.

Category / Keywords: public-key cryptography / Laconic oblivious transfer, private set intersection

Original Publication (with minor differences): IACR-TCC-2021

Date: received 31 May 2021, last revised 17 Sep 2021

Contact author: pmbranco at math tecnico ulisboa pt, alamati at gmail com, nico doettling at gmail com, sanjamg at berkeley edu, mdhajiabadi at uwaterloo ca, push beni at gmail com

Available format(s): PDF | BibTeX Citation

Short URL: ia.cr/2021/728

[ Cryptology ePrint archive ]