Streaming and~Unbalanced PSI from~Function Secret Sharing

Original paper: Streaming and Unbalanced PSI from Function Secret Sharing. Samuel Dittmer, Yuval Ishai, Steve Lu, Rafail Ostrovsky, Mohamed Elsabagh, Nikolaos Kiourtis, Brian Schulte, and Angelos Stavrou. 2022

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

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.”