PSI from Ring-OLE

Fuzzy-labeled private set intersection (PSI) outputs the corresponding label if there is a "fuzzy" match between two items, for example when the Hamming distance is low between the two items. Such protocols can be applied in privacy-preserving biometric authentication, proximity testing, and so on. The only fuzzy-labeled PSI protocol designed for practical purposes is by Uzun et al. (USENIX'21), which is based on homomorphic encryption. This design puts constraints on the item size, label size, and communication cost since it is difficult for homomorphic encryption to support large plaintext space and it is well-known that the ciphertext-expansion factor is large. Our construction begins with a new primitive which we call vector ring-oblivious linear evaluation (vector ring-OLE). This primitive does not rely on existing instantiations of ring-OLE over the quotient ring, but leverages the more efficient vector-OLE. It is ideal for building unbalanced threshold-labeled PSI and is also of independent interest. Our main contribution, fuzzy-labeled PSI, is bootstrapped from our threshold-labeled PSI protocol. Through a prototype implementation, we demonstrate our communication cost is up to 4.6× better than the prior state-of-the-art with comparable end-to-end latency while supporting a significantly higher label size. assumption (DDH) for general L p distances, but with high cost for large d. Recently, [GQL + 24] introduced Fuzzy mapping, a new primitive supporting Hamming distance with linear complexity based on AHE and DDH. The details of related works can be found in Section 1.2. Our Contribution Vector ring-OLE. We propose a new primitive called vector ring-oblivious linear function evaluation (vector ring-OLE) in Section 4 where we achieve a batch of m instances of ring-OLE of degree d (m ≫ d). This primitive is used to construct our fuzzy-labeled PSI protocols and it may be of independent interest. Using the chosen ring-OLE in previous works [GN19, CILO22], it is possible to obtain vector ring-OLE correlations of length m of degree d over a field F from O(md) random OLEs. But the communication cost is at least 6md log |F| (online and offline cost) [CILO22]. We compare with [GN19, CILO22] in the same setting and present the results in Table 1. Compared to the stateof-art of chosen ring-OLE [GN19, CILO22], our vector ring-OLE enjoys two main advantages: 1. Our protocol achieves the same functionality, for the same parameters with a communication cost that is over 50% smaller compared to prior work [GN19, CILO22]. 2. Our protocol has a faster setup phase using vector-OLE (VOLE) while prior work needs OLE [GN19, CILO22]. When we cast their constructions to follow our functionality, [GN19] needs 4md OLEs and it is instantiated from homomorphic encryption. Chongchitmate et al. [CILO22] need 2md OLEs, which is instantiated from ring-OLE. The setup cost of VOLE setup is much faster (less than a second [WYKW21]) when compared to ring OLE or OLE (10-20 seconds [BCG + 20]). Fuzzy-labeled PSI. Our primary contribution is a fuzzy-labeled PSI protocol (Section 5) that is built on top of our threshold-labeled PSI protocol (Section 5.1). Our fuzzy-labeled PSI improves over the state of the art and other related works [UCK + 21, CILO22, GRS22, CFR23, vBP24, GGM24] in the following aspects: -Our fuzzy-labeled PSI focuses on the Hamming distance and supports a high dimension (up to κ bits) efficiently as opposed to [GRS22, vBP24, GGM24], which only support less than 10 dimensions efficiently. -The asymptotic online communication complexity does not depend on the computational security parameter κ. -We support a label space that is not fixed in bit-length size and can go up to κ bits, which was not possible in prior works [GRS22, CILO22, CFR23, GGM24, GQL + 24]. The works of [vBP24, GQL + 24] also support labels as an extension of their constructions; however, labeled PSI in [vBP24] relies on ElGamal encryption, whereas [GQL + 24] uses both ElGamal and AHE, resulting in poor performance. -We implemented our protocol and it outperforms the state-of-the-art [UCK + 21] for database sizes of up to 1 million in both computation and communication. For smaller database sizes, we achieve 4.6× improvement in communication. 1.2 Related Work PCG-based PSI. At the time of writing, PCG-based PSI protocols [RS21, RR22, CILO22, BC23] are the top-performing PSI protocols in terms of both communication and computation costs. The idea of using PCG to improve PSI was first introduced by Rindal and Schoppmann [RS21], which combines oblivious key value store (OKVS) and vector-OLE (a concrete type of PCG). Later, two concurrent works [RR22, BC23] introduced various optimizations (subfield) vector-OLE instead of vector-OLE to reduce the communication cost. While [RR22] uses the same framework of [RS21], the authors designed a better construction for OKVS, giving a reduction of encoding parameter from 1.3n to 1.23n. The work of Bui and Couteau [BC2