Private information retrieval from coded databases with colluding servers

DOI10.1137/16M1102562MaRDI QIDQ4603025zbMATH OpenOpenAlexFDO

Authors Oliver Wilhelm Gnilke, David A. Karpuk, Ragnar Freij-Hollanti, Camilla Hollanti

Publication date 14 February 2018

Published in SIAM Journal on Applied Algebra and Geometry (Search for Journal in Brave)

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

zbMATH Keywords

generalized Reed-Solomon codesprivate information retrievaldistributed storage systems

Mathematics Subject Classification ID

Information storage and retrieval of data (68P20) Coding and information theory (compaction, compression, models of communication, encoding schemes, etc.) (aspects in computer science) (68P30) Applications to coding theory and cryptography of arithmetic geometry (14G50) Distributed systems (68M14) Geometric methods (including applications of algebraic geometry) applied to coding theory (94B27)

Abstract: We present a general framework for Private Information Retrieval (PIR) from arbitrary coded databases, that allows one to adjust the rate of the scheme according to the suspected number of colluding servers. If the storage code is a generalized Reed-Solomon code of length n and dimension k, we design PIR schemes which simultaneously protect against t colluding servers and provide PIR rate 1-(k+t-1)/n, for all t between 1 and n-k. This interpolates between the previously studied cases of t=1 and k=1 and asymptotically achieves the known capacity bounds in both of these cases, as the size of the database grows.

Recommendations

• A general private information retrieval scheme for MDS coded databases with colluding servers
• General constructions for information-theoretic private information retrieval
• Private information retrieval schemes with erasure-correcting or error-correcting properties
• scientific article; zbMATH DE number 1754644
• Improved upper bounds on information-theoretic private information retrieval (extended abstract)

Cites work

• scientific article; zbMATH DE number 1261806 (Why is no real title available?)
• A general private information retrieval scheme for MDS coded databases with colluding servers
• An Upper Bound of Singleton Type for Componentwise Products of Linear Codes
• Critical Pairs for the Product Singleton Bound
• Maximum distance<tex>q</tex>-nary codes
• On the minimum distance of cyclic codes
• PIR Schemes With Small Download Complexity and Low Storage Requirements
• 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.
• Private information retrieval
• 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

Cited in

(12)

• A survey on single server private information retrieval in a coding theory perspective
• Symmetric Private Information Retrieval from MDS Coded Distributed Storage With Non-Colluding and Colluding Servers
• Squares of matrix-product codes
• Theory of supports for linear codes endowed with the sum-rank metric
• Capacity-achieving private information retrieval scheme with a smaller sub-packetization
• Private information retrieval schemes using cyclic codes
• The Capacity of Private Information Retrieval Under Arbitrary Collusion Patterns for Replicated Databases
• A general private information retrieval scheme for MDS coded databases with colluding servers
• Private information retrieval schemes with erasure-correcting or error-correcting properties
• Multi-value private information retrieval with colluding databases via trace functions
• scientific article; zbMATH DE number 5009196 (Why is no real title available?)
• Private information retrieval from locally repairable databases with colluding servers

This page was built for publication: Private information retrieval from coded databases with colluding servers

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