A general private information retrieval scheme for MDS coded databases with colluding servers

DOI10.1007/S10623-019-00640-XMaRDI QIDQ2329401zbMATH OpenOpenAlexWikidataFDO

Authors Yiwei Zhang, Gennian Ge

Publication date 17 October 2019

Published in Designs, Codes and Cryptography (Search for Journal in Brave)

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

zbMATH Keywords

distributed storage systemPIR capacityprivate information retrieval

Mathematics Subject Classification ID

Database theory (68P15) Information storage and retrieval of data (68P20) Privacy of data (68P27) Information theory (general) (94A15)

Abstract: The problem of private information retrieval gets renewed attentions in recent years due to its information-theoretic reformulation and applications in distributed storage systems. PIR capacity is the maximal number of bits privately retrieved per one bit of downloaded bit. The capacity has been fully solved for some degenerating cases. For a general case where the database is both coded and colluded, the exact capacity remains unknown. We build a general private information retrieval scheme for MDS coded databases with colluding servers. Our scheme achieves the rate $(1+R+R^2+cdots+R^{M-1})$, where $R=1-fracN-TchooseKNchooseK$. Compared to existing PIR schemes, our scheme performs better for a certain range of parameters and is suitable for any underlying MDS code used in the distributed storage system.

Recommendations

• Private information retrieval from coded databases with colluding servers
• Private information retrieval schemes with erasure-correcting or error-correcting properties
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Multi-value private information retrieval with colluding databases via trace functions
• General constructions for information-theoretic private information retrieval

Cites work

• 3-query locally decodable codes of subexponential length
• A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers
• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• Nearly Optimal Constructions of PIR and Batch Codes
• On Private Information Retrieval Array Codes
• PIR Array Codes With Optimal Virtual Server Rate
• Private information retrieval
• Private information retrieval from coded databases with colluding servers
• Private Information Retrieval From MDS Coded Data in Distributed Storage Systems
• Private Information Retrieval from MDS Coded Data With Colluding Servers: Settling a Conjecture by Freij-Hollanti et al.
• The Capacity of Private Information Retrieval
• The Capacity of Private Information Retrieval From Coded Databases
• The Capacity of Robust Private Information Retrieval With Colluding Databases
• Towards 3-query locally decodable codes of subexponential length

Cited in

(6)

• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Multi-value private information retrieval with colluding databases via trace functions
• Private information retrieval schemes with erasure-correcting or error-correcting properties
• Private information retrieval from coded databases with colluding servers
• Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers
• Private information retrieval schemes using cyclic codes

This page was built for publication: A general private information retrieval scheme for MDS coded databases with colluding servers

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