Welcome to the resource topic for 2024/1494
Title:
Concretely Efficient Private Set Union via Circuit-based PSI
Authors: Gowri R Chandran, Thomas Schneider, Maximilian Stillger, Christian Weinert
Abstract:Private set intersection (PSI) is a type of private set operation (PSO) for which concretely efficient linear-complexity protocols do exist.
However, the situation is currently less satisfactory for other relevant PSO problems such as private set union (PSU):
For PSU, the most promising protocols either rely entirely on computationally expensive public-key operations or suffer from substantial communication overhead.
In this work, we present the first PSU protocol that is mainly based on efficient symmetric-key primitives yet enjoys comparable communication as public-key-based alternatives.
Our core idea is to re-purpose state-of-the-art circuit-based PSI to realize a multi-query reverse private membership test (mq-RPMT), which is instrumental for building PSU.
We carefully analyze a privacy leakage issue resulting from the hashing paradigm commonly utilized in circuit-based PSI and show how to mitigate this via oblivious pseudorandom function (OPRF) and new shuffle sub-protocols.
Our protocol is modularly designed as a sequential execution of different building blocks that can be easily replaced by more efficient variants in the future, which will directly benefit the overall performance.
We implement our resulting PSU protocol, showing a run-time improvement of 10% over the state-of-the-art public-key-based protocol of Chen et al. (PKC’24) for input sets of size 2^{20}.
Furthermore, we improve communication by 1.6\times over the state-of-the-art symmetric-key-based protocol of Zhang et al. (USENIX Sec’23).
ePrint: https://eprint.iacr.org/2024/1494
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 .