Welcome to the resource topic for 2022/320
Title:
Blazing Fast PSI from Improved OKVS and Subfield VOLE
Authors: Srinivasan Raghuraman and Peter Rindal
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). Additionally, we apply our new techniques to the circuit PSI protocol of Rindal et al. and 6\times improvement in running time. 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 \mathcal{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.
ePrint: https://eprint.iacr.org/2022/320
See all topics related to this paper.
Feel free to post resources that are related to this paper below.
Example resources include: implementations, explanation materials, talks, slides, links to previous discussions on other websites.
For more information, see the rules for Resource Topics .