Element Distinctness and Bounded Input Size in Private Set Intersection and Related Protocols

Carpent, Xavier; Hwang, Seoyeon; Tsudik, Gene

Abstract

This paper considers Private Set Intersection (PSI) protocols where one party (server) imposes a minimum input size (lower bound) on the other party (client), and the latter wants to keep its input size private. This entails tackling two types of possible client misbehavior: (1) using fake/frivolous elements, and (2) duplicating genuine elements. The former can be addressed by pre-authorizing all client elements by a mutually trusted party, which translates into so-called Authorized PSI (APSI). However, the latter is more challenging. To this end, we construct a protocol for Proof of Element-Distinctness (PoED), wherein one party convinces the other that all of its input elements are distinct, without revealing any information about them. Using this as a building block, we then construct a PSI variant, called All-Distinct Private Set Intersection (AD-PSI), that outputs the intersection only when client input contains all distinct elements. We also present some AD-PSI variants where using duplicates can cause unexpected information leakage. Combining the AD-PSI with previous work for upper-bounded-input PSI, we construct a Bounded-Size-Hiding-PSI (B-SH-PSI) that outputs the intersection only if client’s input size satisfies server’s requirement on both lower and upper bounds, while keeping that size private. Finally, we present a protocol that prevents both types of misbehavior, called All-Distinct Authorized PSI (AD-APSI).

Citation

Carpent, X., Hwang, S., & Tsudik, G. (2024, March). Element Distinctness and Bounded Input Size in Private Set Intersection and Related Protocols. Presented at Applied Cryptography and Network Security, Abu Dhabi

• Presentation Conference Type: Conference Paper (published)
• Conference Name: Applied Cryptography and Network Security
• Start Date: Mar 5, 2024
• End Date: Mar 8, 2024
• Online Publication Date: Mar 1, 2024
• Publication Date: Mar 1, 2024
• Deposit Date: Jan 29, 2025
• Publicly Available Date: Mar 2, 2025
• Peer Reviewed: Peer Reviewed
• Volume: 14583 LNCS
• Pages: 26-57
• Series Title: Lecture Notes in Computer Science
• Series Number: 14583
• Series ISSN: 1611-3349
• Book Title: Applied Cryptography and Network Security
• ISBN: 9783031547690
• DOI: https://doi.org/10.1007/978-3-031-54770-6_2
• Public URL: https://nottingham-repository.worktribe.com/output/44689103
• Publisher URL: https://link.springer.com/chapter/10.1007/978-3-031-54770-6_2