A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers

Abstract

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.

Cited by in corpus (10)

• Private Information Retrieval from MDS Coded Data in Distributed Storage Systems
• PIR with Low Storage Overhead: Coding instead of Replication
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private Information Retrieval from Transversal Designs
• Binary, Shortened Projective Reed Muller Codes for Coded Private Information Retrieval
• Private Information Retrieval from Coded Storage Systems with Colluding, Byzantine, and Unresponsive Servers
• Fast Hermite interpolation and evaluation over finite fields of characteristic two
• Weighted Lifted Codes: Local Correctabilities and Application to Robust Private Information Retrieval
• Information Sets of Multiplicity Codes