Paper 2024/1973

Privately Compute the Item with Maximal Weight Sum in Set Intersection

Abstract

Private Set Intersection (PSI) is a cryptographic primitive that allows two parties to obtain the intersection of their private input sets while revealing nothing more than the intersection. PSI and its numerous variants, which compute on the intersection of items and their associated weights, have been widely studied. In this paper, we revisit the problem of finding the best item in the intersection according to weight sum introduced by Beauregard et al. (SCN '22), which is a special variant of PSI. We present two new protocols that achieve the functionality. The first protocol is based on Oblivious Pseudorandom Function (OPRF), additively homomorphic encryption and symmetric-key encryption, while the second one is based on Decisional Diffie-Hellman (DDH) assumption, additively homomorphic encryption and symmetric-key encryption. Both protocols are proven to be secure against semi-honest adversaries. Compared with the original protocol proposed by Beauregard et al. (abbreviated as the FOCI protocol), which requires all weights in the input sets to be polynomial in magnitude, our protocols remove this restriction. We compare the performance of our protocols with the FOCI protocol both theoretically and empirically. We find out that the performance of FOCI protocol is primarily affected by the size of the intersection and the values of elements’ weights in intersection when fixing set size, while the performance of ours is independent of these two factors. In particular, in the LAN setting, when the set sizes are $n=10000$, intersection size of $\frac{n}{2}$, the weights of the elements are uniformly distributed as integers from $\left[0, n-1\right]$, our DDH-based protocol has a similar run-time to the FOCI protocol. However, when the weights of the elements belonging to $\left[0, 10n-1\right]$ and $\left[0, 100n-1\right]$, our DDH-based protocol is between a factor $2\times$ and $5\times$ faster than the FOCI protocol.