You are looking at a specific version 20210602:115122 of this paper. See the latest version.

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

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
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
History
2021-09-17: revised
2021-06-02: received
See all versions
Short URL
https://ia.cr/2021/728
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.