Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval


Meng Hao, Nanyang Technological University; Weiran Liu and Liqiang Peng, Alibaba Group; Hongwei Li, Peng Cheng Laboratory; Cong Zhang, Institute for Advanced Study, BNRist, Tsinghua University; Hanxiao Chen and Tianwei Zhang, Nanyang Technological University


Circuit-based Private Set Intersection (circuit-PSI) empowers two parties, a client and a server, each with input sets X and Y, to securely compute a function f on the intersection X∩Y while preserving the confidentiality of X∩Y from both parties. Despite the recent proposals of computationally efficient circuit-PSI protocols, they primarily focus on the balanced scenario where |X| is similar to |Y|. However, in many practical situations, a circuit-PSI protocol may be applied in an unbalanced context, where |X| is significantly smaller than |Y|. Directly applying existing protocols to this scenario poses notable efficiency challenges due to the communication complexity of these protocols scaling at least linearly with the size of the larger set, i.e., max(|X|,|Y|).

In this work, we put forth efficient constructions for unbalanced circuit-PSI, demonstrating sublinear communication complexity in the size of the larger set. Our key insight lies in formalizing unbalanced circuit-PSI as the process of obliviously retrieving values corresponding to keys from a set of key-value pairs. To achieve this, we propose a new functionality named Oblivious Key-Value Retrieval (OKVR) and design the OKVR protocol based on a new notion termed sparse Oblivious Key-Value Store (sparse OKVS). We conduct comprehensive experiments and the results showcase substantial improvements over the state-of-the-art circuit-PSI schemes, i.e., 1.84∼48.86x communication improvement and 1.50∼39.81x faster computation. Compared to a very recent unbalanced circuit-PSI work, our constructions outperform them by 1.18∼15.99x and 1.22∼10.44x in communication and computation overhead, respectively, depending on set sizes and network environments.

Open Access Media

USENIX is committed to Open Access to the research presented at our events. Papers and proceedings are freely available to everyone once the event begins. Any video, audio, and/or slides that are posted after the event are also free and open to everyone. Support USENIX and our commitment to Open Access.