Paper 2022/320

Blazing Fast PSI from Improved OKVS and Subfield VOLE

Peter Rindal and Srinivasan Raghuraman

Abstract

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.

Metadata
Available format(s)
PDF
Publication info
Preprint. Minor revision.
Keywords
Private Set IntersectionJoinVOLEOLE
Contact author(s)
peterrindal @ gmail com
History
2022-03-08: received
Short URL
https://ia.cr/2022/320
License
Creative Commons Attribution-NonCommercial
CC BY-NC

BibTeX

@misc{cryptoeprint:2022/320,
      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{https://eprint.iacr.org/2022/320}},
      url = {https://eprint.iacr.org/2022/320}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.