Paper 2023/1733

Hintless Single-Server Private Information Retrieval

Baiyu Li, Google (United States)
Daniele Micciancio, University of California, San Diego
Mariana Raykova, Google (United States)
Mark Schultz-Wu, University of California, San Diego
Abstract

We present two new constructions for private information retrieval (PIR) in the classical setting where the clients do not need to do any preprocessing or store any database dependent information, and the server does not need to store any client-dependent information. Our first construction (HintlessPIR) eliminates the client preprocessing step from the recent LWE-based SimplePIR (Henzinger et. al., USENIX Security 2023) by outsourcing the "hint" related computation to the server, leveraging a new concept of homomorphic encryption with composable preprocessing. We realize this concept with RLWE encryption schemes, and by leveraging the composibility of this technique we are able to preprocess almost all the expensive parts of the homomorphic computation and reuse them across multiple protocol executions. As a concrete application, we propose highly efficient matrix vector multiplication that allows us to build HintlessPIR. For a database of size 8GB, HintlessPIR achieves throughput about 6.37GB/s without requiring transmission of any client or server state. We additionally formalize the matrix vector multiplication protocol as a novel primitive that we call LinPIR, which may be of independent interest. In our second construction (TensorPIR) we reduce the communication of HintlessPIR from square root to cubic root in the database size. For this purpose we extend our HE with preprocessing techniques to composition of key-switching keys and the query expansion algorithm. We show how to use RLWE encryption with preprocessing to outsource LWE decryption for ciphertexts generated by homomorphic multiplications. This allows the server to do more complex processing using a more compact query under LWE. We implement and benchmark HintlessPIR which achieves better concrete costs than TensorPIR for a large set of databases of interest. We show that it improves the communication of recent preprocessing constructions when clients do not have large numbers of queries or the database updates frequently. The computation cost for removing the hint is small and decreases as the database becomes larger, and it is always more efficient than other constructions with client hints such as Spiral PIR (Menon and Wu, S&P 2022). In the setting of anonymous queries we also improve on Spiral's communication.

Metadata
Available format(s)
PDF
Category
Applications
Publication info
A minor revision of an IACR publication in CRYPTO 2024
Keywords
PIRRLWEFHE
Contact author(s)
baiyuli @ google com
daniele @ cs ucsd edu
marianar @ google com
mdschultz @ eng ucsd edu
History
2024-06-14: revised
2023-11-09: received
See all versions
Short URL
https://ia.cr/2023/1733
License
Creative Commons Attribution
CC BY

BibTeX

@misc{cryptoeprint:2023/1733,
      author = {Baiyu Li and Daniele Micciancio and Mariana Raykova and Mark Schultz-Wu},
      title = {Hintless Single-Server Private Information Retrieval},
      howpublished = {Cryptology {ePrint} Archive, Paper 2023/1733},
      year = {2023},
      url = {https://eprint.iacr.org/2023/1733}
}
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.