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

DOI10.1007/978-3-319-12280-9_15MaRDI QIDQ5498730zbMATH OpenOpenAlexFDO

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)

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

Mathematics Subject Classification ID

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

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.

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

Cited in

(7)

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

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)