Paper 2022/320

Blazing Fast PSI from Improved OKVS and Subfield VOLE

Peter Rindal and Srinivasan Raghuraman


We present new semi-honest and malicious secure PSI protocols that outperform all prior works by several times in both communication and running time. For example, our semi-honest protocol for $n = 2^{20}$ can be performed in 0.37 seconds compared to the previous best of 2 seconds (Kolesnikov et al., CCS 2016 ). This can be further reduced to 0.16 seconds with 4 threads, a speedup of $12\times$. Similarly, our protocol sends $187n$ bits compared to $426n$ bits of the next most communication efficient protocol (Rindal et al., Eurocrypt 2021 ). These performance results are obtained by two types of improvements. The first is an optimization to the protocol of Rindal et al. to utilize sub-field vector oblivious linear evaluation. This optimization allows our construction to be the first to achieve a communication complexity of $O(n\lambda + n \log n)$ where $\lambda$ is the statistical security parameter. In particular, the communication overhead of our protocol does not scale with the computational security parameter times $n$. Our second improvement is to the OKVS data structure which our protocol crucially relies on. In particular, our construction improves both the computation and communication efficiency as compared to prior work (Garimella et al., Crypto 2021 ). These improvements stem from algorithmic changes to the data structure along with new techniques for obtaining both asymptotic and tight concrete bounds on its failure probability. This in turn allows for a highly optimized parameter selection and thereby better performance.

Available format(s)
Publication info
Preprint. Minor revision.
Private Set IntersectionJoinVOLEOLE
Contact author(s)
peterrindal @ gmail com
2022-03-08: received
Short URL
Creative Commons Attribution-NonCommercial


      author = {Peter Rindal and Srinivasan Raghuraman},
      title = {Blazing Fast PSI from Improved OKVS and Subfield VOLE},
      howpublished = {Cryptology ePrint Archive, Paper 2022/320},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.