A new Capacity-Achieving Private Information Retrieval Scheme with (Almost) Optimal File Length for Coded Servers

2019/03/16 by Jinbao Zhu, Zhu, Jinbao, Qifa Yan +5 · 1 citation
Computer Science · #Cryptography and Data Security #Advanced Data Storage Technologies #Caching and Content Delivery

paper · pdf · doi:10.48550/arxiv.1903.06921

Abstract

In a distributed storage system, private information retrieval (PIR) guarantees that a user retrieves one file from the system without revealing any information about the identity of its interested file to any individual server. In this paper, we investigate (N,K,M) coded sever model of PIR, where each of M files is distributed to the N servers in the form of (N,K) maximum distance separable (MDS) code for some N>K and M>1. As a result, we propose a new capacity-achieving (N,K,M) coded linear PIR scheme such that it can be implemented with file length (K(N-K))/(gcd(N,K)), which is much smaller than the previous best result K((N)/(gcd(N,K)))^M-1. Notably, among all the capacity-achieving coded linear PIR schemes, we show that the file length is optimal if M>\lfloor (K)/(gcd(N,K))-(K)/(N-K)\rfloor+1, and within a multiplicative gap (K)/(gcd(N,K)) of a lower bound on the minimum file length otherwise.

Cited by

• A General Coding Framework for Adaptive Private Information Retrieval

Related

• Achieving Maximum Distance Separable Private Information Retrieval Capacity With Linear Codes
• On the Fundamental Limit of Private Information Retrieval for Coded Distributed Storage
• The Capacity of Private Information Retrieval from Coded Databases
• Capacity-Achieving Private Information Retrieval Codes from MDS-Coded Databases with Minimum Message Size
• Private Information Retrieval from MDS Coded Databases with Colluding Servers under Several Variant Models