Welcome to the resource topic for 2023/919
Title:
Threshold Private Set Intersection with Better Communication Complexity
Authors: Satrajit Ghosh, Mark Simkin
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 \cdot\mathrm{poly}(t)), where \lambda is the security parameter, and transforms it into a protocol with communication complexity \mathcal{O}(\lambda^2 \ell t \cdot\mathrm{polylog}(t)).
ePrint: https://eprint.iacr.org/2023/919
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .