Labeled Private Set Intersection From Distributed Point Function

Qi Liu

doi:10.1109/tifs.2025.3550059

Labeled Private Set Intersection From Distributed Point Function

2025-01-01

0

PRE

AI

DOI：10.1109/tifs.2025.3550059

原文链接

摘要

En 中文

Private Set Intersection (PSI) allows two mutually distrusting parties to compute the intersection of their sets without revealing any additional information, and has found numerous applications. A part of applications require labeled PSI in the unbalanced setting, where a server holds a label for each item in a set that is much larger than the set held by a client, and the client obtains the intersection and the corresponding labels. In this paper, we present a new concretely efficient labeled PSI protocol in the unbalanced setting, without using computation-heavy homomorphic encryption. Our protocol is based on Distributed Point Function (DPF) with hardware acceleration from fixed-key AES-NI, and has communication complexity linear in the size of a small set of the client and sublinear in the size of a large set of the server. Our protocol exploits two Oblivious Pesudorandom Function (OPRF) protocols, based on Diffle-Hellman PRFs or block ciphers, to achieve a trade-off between computation and communication. Our implementation demonstrates that our protocol outperforms the previous labeled and unbalanced PSI protocols. In particular, for two sets with respective$2^{24}$and 1 items, where each item has a 32-byte label, our protocol takes 1.19 seconds for an end-to-end performance, resulting in$26 \times $improvement compared to the state-of-the-art protocol by Cong et al. (CCS 2021). In terms of the cost of the one-time initialization, we speed up the computations more than$325\times $in the above comparison.

Labeled Private Set Intersection From Distributed Point Function

摘要

期刊

机构

引用论文