Scalable Multi-Server Private Information Retrieval
Ashrujit Ghoshal, Carnegie Mellon University
Baitian Li, Tsinghua IIIS and Columbia
Yaohua Ma, Tsinghua IIIS and CMU
Chenxin Dai, Tsinghua IIIS and CMU
Elaine Shi, Carnegie Mellon University
Abstract
We revisit multi-server Private Information Retrieval (PIR), where the client interacts with non-colluding servers. Ideally, we want a *scalable* family of multi-server PIR schemes where all the performance metrics of the scheme decrease as increases. However, no prior work achieved scalability under any setting, and any hardness assumption.
In this paper we construct new multi-server, information-theoretically secure *scalable* PIR schemes for three natural settings. First, we give a construction where all the performance metrics scale at equal rate. Second, we give a scalable construction that minimizes the per-query bandwidth. Third, we give a scalable construction that minimizes the per-query online bottleneck cost (the maximum of the bandwidth and computation). For the first two settings, our constructions are *doubly efficient* with only a super-constant number of servers. In comparison, the best known prior works in the information-theoretic setting required super-logarithmically many servers to achieve the doubly efficient notion.
Our techniques for achieving scalable PIR also enable us to advance the state of the art in the polynomial space setting. In this setting, we show how to improve the space consumption of prior works by a polynomial factor while preserving all other metrics. Further, we show a new balancing technique that allows us to further minimize the bandwidth per query by trading off the computation and server space, thus enabling a more smooth tradeoff between the metrics and generalizing the design space.
@misc{cryptoeprint:2024/765,
author = {Ashrujit Ghoshal and Baitian Li and Yaohua Ma and Chenxin Dai and Elaine Shi},
title = {Scalable Multi-Server Private Information Retrieval},
howpublished = {Cryptology {ePrint} Archive, Paper 2024/765},
year = {2024},
url = {https://eprint.iacr.org/2024/765}
}
Note: In order to protect the privacy of readers, eprint.iacr.org
does not use cookies or embedded third party content.