Streaming and Unbalanced PSI from Function Secret Sharing
Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, Angelos Stavrou
Abstract:
Private Set Intersection (PSI) is one of the most useful and well-studied instances of secure computation, with many variants and applications. In this work, we present new solutions to PSI and a weighted variant in which the output is the sum of the weights of keywords in the intersection. Our protocols apply to the semi-honest, two-server model and are optimized for the unbalanced case, where one of the sets is much larger than the other, and for a dynamic streaming setting, in which sets can evolve over time.
Our protocols make use of Function Secret Sharing (FSS) to aggregate numerical payloads associated with the intersection while minimizing interaction and computational overhead. They avoid the use of public-key cryptography, giving simple and concretely efficient protocols for unbalanced PSI. In the dynamic setting, we use queuing theory to eliminate leakage with minimal overhead while ensuring low wait times, giving efficient streaming unbalanced PSI.
comment:
SCN 2022: 564-587
Fetch PDF file of the paper