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

Date: received 31 May 2021, last revised 1 Jun 2021

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

Available format(s): PDF | BibTeX Citation

Version: 20210602:115122 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]