Welcome to the resource topic for 2024/753
Title:
Summation-based Private Segmented Membership Test from Threshold-Fully Homomorphic Encryption
Authors: Nirajan Koirala, Jonathan Takeshita, Jeremy Stevens, Taeho Jung
Abstract:In many real-world scenarios, there are cases where a client wishes
to check if a data element they hold is included in a set segmented
across a large number of data holders. To protect user privacy, the
client’s query and the data holders’ sets should remain encrypted
throughout the whole process. Prior work on Private Set Intersection (PSI), Multi-Party PSI (MPSI), Private Membership Test (PMT),
and Oblivious RAM (ORAM) falls short in this scenario in many
ways. They either require data holders to possess the sets in plain-
text, incur prohibitively high latency for aggregating results from a
large number of data holders, leak the information about the party
holding the intersection element, or induce a high false positive.
This paper introduces the primitive of a Private Segmented Mem-
bership Test (PSMT). We give a basic construction of a protocol to
solve PSMT using a threshold variant of approximate-arithmetic
homomorphic encryption and show how to overcome existing
challenges to construct a PSMT protocol without leaking information about the party holding the intersection element or false
positives for a large number of data holders ensuring IND-CPA^𝐷
security. Our novel approach is superior to existing state-of-the-art
approaches in scalability with regard to the number of supported
data holders. This is enabled by a novel summation-based homo-
morphic membership check rather than a product-based one, as
well as various novel ideas addressing technical challenges. Our
PSMT protocol supports many more parties (up to 4096 in experiments) compared to prior related work that supports only around
100 parties efficiently. Our experimental evaluation shows that our
method’s aggregation of results from data holders can run in 92.5s
for 1024 data holders and a set size of 2^25, and our method’s over-
head increases very slowly with the increasing number of senders.
We also compare our PSMT protocol to other state-of-the-art PSI
and MPSI protocols and discuss our improvements in usability with
a better privacy model and a larger number of parties
ePrint: https://eprint.iacr.org/2024/753
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 .