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

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).