FlashPIR: low-latency FHE-based single-server PIR with low client overhead

Abstract Toward practical and client-friendly single-server private information retrieval, we introduce FlashPIR, a scheme achieving both low client overhead and high server throughput. Constructed based on fully homomorphic encryption, our protocol possesses two distinct advantages: First, a majority of the resource-intensive computations can be performed in an offline phase, prior to query reception, significantly reducing the online response time. Second, database updates operate independently of clients, with low client computational overhead remaining nearly constant regardless of the database scale. We conducted comprehensive experiments to evaluate the performance of FlashPIR. The results demonstrate that for database sizes of 256 MB, our scheme achieves a throughput $$2.6\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>2.6</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> greater than KsPIR (Luo et al., CCS 2024) and $$18.5\times$$ <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML"> <mml:mrow> <mml:mn>18.5</mml:mn> <mml:mo>×</mml:mo> </mml:mrow> </mml:math> greater than Spiral (Menon and Wu, S&amp;P 2022).