Ultra-Fast Private Set Intersection From Efficient Oblivious Key-Value Stores

Private Set Intersection (PSI) enables us to compute the intersection of private sets without leaking additional data. The state-of-the-art PSI protocol <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {RR22}$</tex-math></inline-formula> (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CCS 2022</i>) is derived from an Oblivious Pseudo-Random Function (OPRF) protocol based on Oblivious Key-Value Stores (OKVS). However, the existing OKVS suffers either low computation efficiency or high encoding redundancy. In this work, we propose a new efficient bucket-based OKVS with only 1% redundancy. The encoding algorithm of our OKVS is 4 to 15 times faster than the recent state-of-the-art OKVS (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">USENIX Security 2023</i>). Specifically, our OKVS can encode <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$2^{24}$</tex-math></inline-formula> key-value pairs in only 2.1 to 8.5 seconds, corresponding to 30% to 1% redundancy, while the latter takes about 30 seconds with at least 3%. We can then obtain a new ultra-fast PSI protocol with lower communication from our OKVS in both semi-honest and malicious settings. Furthermore, we implemented our PSI protocol and conducted an extensive evaluation, which shows that it outperforms the existing PSI protocols, such as <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {KKRT16}$</tex-math></inline-formula> (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CCS 2016</i>), <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {CM20}$</tex-math></inline-formula> (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">Crypto 2020</i>), <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {RS21}$</tex-math></inline-formula> (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">EuroCrypt 2021</i>), <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {RR22}$</tex-math></inline-formula> (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">CCS 2022</i>), and <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {KBM23}$</tex-math></inline-formula> (<italic xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">NDSS 2023</i>). Since our PSI features an ultra-low communication overhead, it has overall advantages for the network environment with a small bandwidth. For example, our PSI takes only about 468 and 476 seconds in semi-honest and malicious settings with the input size of <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$2^{24}$</tex-math></inline-formula> when the bandwidth is 10 Mbps, while the state-of-the-art <inline-formula xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink"><tex-math notation="LaTeX">$\mathsf {RR22}$</tex-math></inline-formula> requires about 541 and 625 seconds. Our implementation is available on <uri xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">https://github.com/ShallMate/fastpsi</uri>.