Verifiable PIR with Small Client Storage

Abstract 
Efficient Verifiable Private Information Retrieval (vPIR) protocols, and more generally Verifiable Linearly Homomorphic Encryption (vLHE), suffer from high client storage. VeriSimplePIR (USENIX Security 2024), the state-of-the-art vPIR protocol, requires clients to persistently maintain over 1 GiB of local storage to privately access an 8 GiB remote database. We present a new vPIR protocol that reduces the client state by orders of magnitude while preserving online latency. In our protocol, clients only need to store 512 KiB for an 8 GiB database, achieving a 2000× improvement. Our vPIR protocol is built over our new vLHE scheme. Unlike VeriSimplePIR, our scheme doesn’t use random oracles and relies only on standard lattice assumptions - (R)LWE and SIS. With an optimized implementation, we additionally observe significant improvement in online latency over VeriSimplePIR. Moreover, the cost of verifiability in our protocol is minimal, with only a 1.1-1.4× overhead in overall time per query compared to the state-of-the-art non-verifiable HintlessPIR (CRYPTO 2024). We also introduce the notion of covert vPIR (cvPIR), where stateful clients enjoy full vPIR security, while even stateless clients benefit from covert security against a malicious server. 

This is joint work with Keewoo Lee and Raluca Ada Popa.