Summation-based Private Segmented Membership Test from Threshold-Fully Homomorphic Encryption.

Area of Science:

• Cryptography and Security
• Distributed Systems
• Privacy-Preserving Technologies

Background:

• Existing privacy protocols like PSI, MPSI, PMT, and ORAM have limitations in scenarios requiring encrypted data membership checks across numerous data holders.
• Challenges include plaintext data requirements, high latency, information leakage about data ownership, and unacceptable false positive rates.
• A need exists for a scalable and secure solution for private membership testing in segmented, encrypted datasets.

Purpose of the Study:

• To introduce and construct a novel primitive called Private Segmented Membership Test (PSMT).
• To develop a PSMT protocol that ensures user privacy by keeping data encrypted throughout the process.
• To overcome limitations of prior work by enhancing scalability, reducing latency, and eliminating information leakage and false positives.

Main Methods:

• Developed a PSMT protocol utilizing a threshold variant of approximate-arithmetic homomorphic encryption.
• Implemented a novel summation-based homomorphic membership check, differing from traditional product-based approaches.
• Ensured IND-CPA ^D security against privacy breaches.

Main Results:

• The PSMT protocol demonstrates superior scalability, supporting up to 4096 data holders, significantly more than prior methods (approx. 100).
• Experimental results show efficient aggregation, with a 1024-data holder scenario completing in 92.5 seconds for a set size of 2²⁵.
• Overhead increases minimally with the number of data holders, confirming excellent scalability.

Conclusions:

• The proposed PSMT protocol offers a significant advancement in privacy-preserving data analysis for large-scale, segmented datasets.
• It provides a more usable and secure alternative to existing PSI and MPSI protocols, particularly concerning the number of supported parties and privacy guarantees.
• The novel summation-based approach and technical innovations enable efficient and private membership testing across a vast number of data holders.