Efficient private set intersection

Abstract

Private set intersection (PSI) is a special kind of secure computation. It enables n parties to securely get the intersection of their sets. In this thesis, we first propose an oblivious key-value store (OKVS) Multi-PGBF, which is a data structure that can obliviously encode key-value pairs. Multi-PGBF has many advantages compared with existing OKVSs. For example, compared with PaXoS (Eurocrypt’20) and 3H-GCT (Crypto’21), it has faster encoding and decoding efficiency by using smaller storage. Then we combine Multi-PGBF with a cryptographic primitive called Vector Oblivious Linear function Evaluation (VOLE) to design our first two-party unfair PSI protocol that can achieve the lowest communication costs and computation costs. We also combine cuckoo hashing with VOLE to design another two-party unfair PSI protocol. As a result, it can run comparably as fast as our first unfair PSI protocol in the LAN network setting.

In unfair PSI, only one party gets the intersection while the other parties learn nothing. However, there are needs in real-world applications where two parties both want to know the intersection. Therefore, we propose the first two-party fair PSI protocol by combining our two-party unfair PSI protocol and PSI-Cardinality (PSI-CA) protocol. Two-party unfair PSI-CA is a variant of PSI, in which one party knows the intersection cardinality rather than the intersection in PSI. We propose a computationally friendly two-party unfair PSI-CA protocol.

There is also a kind of PSI(-CA) called unbalanced PSI(-CA), in which one party has a set with a size much smaller than the other party. The focus of unbalanced PSI(-CA) protocols is the low communication cost. We propose the most efficient unbalanced PSI-CA protocols with the lowest communication complexity O(ny log(nx)), where ny and nx are respectively the small set size and large set size. Our unbalanced PSI-CA protocols can be easily modified into unbalanced PSI protocols. Compared with the state-of-the-art unbalanced PSI work (Cong et al., CCS’21), one of our unbalanced PSI protocols can save 42%~59% communication costs and accelerate the running time. We apply one of our lightweight unbalanced PSI-CA protocols to design a privacy-preserving contact tracing system, which shows obvious advantages against related designs.

We also design a multi-party unfair PSI protocol by utilizing OKVS and a cryptographic primitive called oblivious pseudorandom function. It is the first ring-based multi-party PSI protocol that can balance the communication and computation costs between the parties. We also design a star-based multi-party PSI protocol. As a result, our multi-party protocols are respectively 3.69%~51.15% and 5.24%~105.84% cheaper than the state-of-the-art counterparts KMPRT (CCS’17) and CDGOSS (CCS’21) in the total communication costs.