CryptoDB
Threshold Private Set Intersection with Better Communication Complexity
| Authors: |
|
|---|---|
| Download: | |
| Presentation: | Slides |
| Conference: | PKC 2023 |
| Abstract: | Given $\ell$ parties with sets $X_1, \dots, X_\ell$ of size $n$, we would like to securely compute the intersection $\cap_{i=1}^\ell X_i$, if it is larger than $n-t$ for some threshold $t$, without revealing any other additional information. It has previously been shown (Ghosh and Simkin, Crypto 2019) that this function can be securely computed with a communication complexity that only depends on $t$ and in particular does not depend on $n$. For small values of $t$, this results in protocols that have a communication complexity that is sublinear in the size of the inputs. Current protocols either rely on fully homomorphic encryption or have an at least quadratic dependency on the parameter $t$. In this work, we construct protocols with a quasilinear dependency on $t$ from simple assumptions like additively homomorphic encryption and oblivious transfer. All existing approaches, including ours, rely on protocols for computing a single bit, which indicates whether the intersection is larger than $n-t$ without actually computing it. Our key technical contribution, which may be of independent interest, takes any such protocol with secret shared outputs and communication complexity $\mathcal{O}(\lambda \ell \mathsf{poly}(t))$, where $\lambda$ is the security parameter, and transforms it into a protocol with communication complexity $\mathcal{O}(\lambda^2 \ell t \mathsf{polylog}(t))$. |
BibTeX
@inproceedings{pkc-2023-32820,
title={Threshold Private Set Intersection with Better Communication Complexity},
publisher={Springer-Verlag},
doi={10.1007/978-3-031-31371-4_9},
author={Satrajit Ghosh and Mark Simkin},
year=2023
}