Private information retrieval from coded databases with colluding servers

DOI10.1137/16M1102562zbMATH Open1386.68049arXiv1611.02062OpenAlexW2963413537MaRDI QIDQ4603025FDOQ4603025

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)

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.

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

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)

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)

Cites Work

• Critical Pairs for the Product Singleton Bound
• An Upper Bound of Singleton Type for Componentwise Products of Linear Codes
• Maximum distance<tex>q</tex>-nary codes
• On the minimum distance of cyclic codes
• Title not available (Why is that?)
• Private information retrieval
• The Capacity of Robust Private Information Retrieval With Colluding Databases
• The Capacity of Private Information Retrieval
• A general private information retrieval scheme for MDS 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 From Coded Databases
• PIR Schemes With Small Download Complexity and Low Storage Requirements

Cited In (12)

• 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
• Title not available (Why is that?)
• Private information retrieval from locally repairable databases with colluding servers
• 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

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)