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.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Privately Compute the Item with Maximal Weight Sum in Set Intersection

  • Hongyuan Cai,
  • Xiaodong Wang,
  • Zijie Lu,
  • Bei Liang

摘要

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.