Streaming and~Unbalanced PSI from~Function Secret Sharing

Original paper: [1]

Summary

  • Here, streaming means updateable. In this context, this work can realize the addition-only and weak-deletion.
  • Setting is semi-honest client and two non-colluding servers.
  • They present 4 PSI-WCA protocols: 2 for one-shot, 2 for streaming. The 2 streaming are:
    • Baseline: ?
    • Greedy scheduling: "To maximize performance while avoiding leakage, our solution flattens the histogram by deferring keywords from over-populated buckets to be processed with high priority in the next batch of queries, using a technique we call greedy scheduling."
  • They use FSS for point functions. They use a DPF to implement the FSS for point function.

Notes

References

[1] Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, and Angelos Stavrou. 2022. “Streaming and Unbalanced PSI from Function Secret Sharing.”