Welcome to the resource topic for 2023/1636
Title:
Unbalanced Circuit-PSI from Oblivious Key-Value Retrieval
Authors: Meng Hao, Weiran Liu, Liqiang Peng, Hongwei Li, Cong Zhang, Hanxiao Chen, Tianwei Zhang
Abstract:Circuit-based Private Set Intersection (circuit-PSI) enables two parties, a client and a server, with their input sets X and Y respectively, to securely compute a function f on the intersection X \cap Y, while keeping X \cap Y secret from both parties. Although several computationally efficient circuit-PSI protocols have been proposed recently, they most focus on the balanced scenario where |X| is similar to |Y|. However, in many realistic scenarios, a circuit-PSI protocol may be performed in the unbalanced case where |X| is remarkably smaller than |Y| (e.g., the client is a constrained device holding a small set, while the server is a service provider holding a large set). Directly applying existing protocols to this scenario will lead to significant efficiency issues because the communication complexity of the protocols scales 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 with sublinear communication complexity in the size of the larger set. The main insight is that we formalize unbalanced circuit-PSI as obliviously retrieving values corresponding to keys from a set of key-value pairs. To this end, we present a new functionality called Oblivious Key-Value Retrieval (OKVR) and design the OKVR protocol from a new notion called sparse Oblivious Key-Value Stores (sparse OKVS). We conduct extensive experiments and the results show that our constructions remarkably outperform the state-of-the-art circuit-PSI schemes (EUROCRYPT’19, PETs’22, CCS’22), i.e., 1.84 \sim 48.86 \times communication improvement and 1.50 \sim39.81 \times faster computation. Very recently, Son and Jeong (AsiaCCS’23) also present unbalanced circuit-PSI protocols, and our constructions outperform them by 1.18 \sim 15.99 \times and 1.22 \sim 10.44 \times in communication and computation overhead, respectively, depending on set sizes and network environments.
ePrint: https://eprint.iacr.org/2023/1636
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .