A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers
This work addresses storage efficiency and robustness in PIR schemes for secure data retrieval, representing an incremental improvement by applying known codes to a specific bottleneck.
The paper tackles the problem of building a Byzantine robust private information retrieval (PIR) scheme with reduced storage redundancy and lower locality by using multiplicity codes, achieving significant reductions in global redundancy and demonstrating a distinction between LDC-locality and PIR-locality.
Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000, it is well-known that information the-oretically secure private information retrieval schemes can be built using locally decodable codes. In this paper, we construct a Byzantine ro-bust PIR scheme using the multiplicity codes introduced by Kopparty et al. Our main contributions are on the one hand to avoid full replica-tion of the database on each server; this significantly reduces the global redundancy. On the other hand, to have a much lower locality in the PIR context than in the LDC context. This shows that there exists two different notions: LDC-locality and PIR-locality. This is made possible by exploiting geometric properties of multiplicity codes.