Efficient Batched Oblivious PRF with Applications to Private Set Intersection

Paper: Efficient Batched Oblivious PRF with Applications to Private Set Intersection. Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. 2016

Summary

  • This paper presents a new lightweight OPRF for semi-honest adversaries.
  • They show how to perform \(m\) OPRF evaluations with \(3.5m\) instances of 1-out-of-2 OT.
  • They use two baselines:
    • Pinkas USENIX PSI, \(3.1-3.6\times\) faster for PSI of 128 bit strings for $220$-size sets.
    • Naive hashing (insecure): \(4.3\times\) slower.

Recommended Videos

References

Vladimir Kolesnikov, Ranjit Kumaresan, Mike Rosulek, and Ni Trieu. 2016. “Efficient Batched Oblivious PRF with Applications to Private Set Intersection.” https://dl.acm.org/doi/10.1145/2976749.2978381.