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

DOI10.1007/978-3-319-12280-9_15zbMATH Open1436.94034arXiv1412.5012OpenAlexW2161788512MaRDI QIDQ5498730FDOQ5498730

Authors: Daniel Augot, Françoise Levy-dit-Vehel, Abdullatif Shikfa 

Publication date: 10 February 2015

Published in: Cryptology and Network Security (Search for Journal in Brave)

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.

Full work available at URL: https://arxiv.org/abs/1412.5012

Recommendations

• A new multi-server scheme for private information retrieval
• Verifiable multi-server private information retrieval
• On the Storage Cost of Private Information Retrieval
• Private Information Retrieval From Coded Storage Systems With Colluding, Byzantine, and Unresponsive Servers
• Multiround Private Information Retrieval: Capacity and Storage Overhead
• Verifiable single-server private information retrieval
• Multi-Server Weakly-Private Information Retrieval
• Towards doubly efficient private information retrieval
• Private information retrieval with result verification for more servers

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Cryptography (94A60) Privacy of data (68P27)

Cited In (7)

• Fast Hermite interpolation and evaluation over finite fields of characteristic two
• On the Storage Cost of Private Information Retrieval
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Efficient and generic methods to achieve active security in private information retrieval and more advanced database search
• Verifiable single-server private information retrieval
• Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers
• Fast systematic encoding of multiplicity codes

This page was built for publication: A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5498730)