t-Private Information Retrieval Schemes Using Transitive Codes

2017/12/07 by Ragnar Freij-Hollanti, Oliver W. Gnilke, Freij-Hollanti, Ragnar +9 · 2 citations
Computer Science · #Advanced Data Storage Technologies #Coding theory and cryptography #Cooperative Communication and Network Coding #FOS: Computer and information sciences #Information Theory (cs.IT)

paper · pdf · doi:10.48550/arxiv.1712.02850

openalex publication_date 2017/12/07 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

This paper presents private information retrieval (PIR) schemes for coded storage with colluding servers, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. This rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems without collusion. While many PIR schemes in the literature require field sizes that grow with the number of servers and files in the system, we focus especially on the case of a binary base field, for which Reed- Muller codes serve as an important and explicit class of examples.

Cited by

• The Star Product of Uniformly Random Codes
• The Schur product of evaluation codes and its application to CSS-T quantum codes and private information retrieval

Related

• An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes
• t-PIR Schemes with Flexible Parameters via Star Products of Berman Codes
• On the Fundamental Limit of Private Information Retrieval for Coded Distributed Storage
• Storage and Retrieval Codes in PIR Schemes with Colluding Servers
• Private Information Retrieval from Colluding and Byzantine Servers with Binary Reed-Muller Codes