Private Information Retrieval in Distributed Storage Systems Using an\n Arbitrary Linear Code

2016/12/21 by Siddhartha Kumar, Kumar, Siddhartha, Eirik Rosnes +3
Computer Science · #Advanced Data Storage Technologies #Cryptography and Data Security #Privacy-Preserving Technologies in Data

paper · pdf · doi:10.48550/arxiv.1612.07084

Abstract

We propose an information-theoretic private information retrieval (PIR)\nscheme for distributed storage systems where data is stored using a linear\nsystematic code of rate R > 1/2. The proposed scheme generalizes the PIR\nscheme for data stored using maximum distance separable codes recently proposed\nby Tajeddine and El Rouayheb for the scenario of a single spy node. We further\npropose an algorithm to optimize the communication price of privacy (cPoP)\nusing the structure of the underlying linear code. As an example, we apply the\nproposed algorithm to several distributed storage codes, showing that the cPoP\ncan be significantly reduced by exploiting the structure of the distributed\nstorage code.\n

Related

• On the Fundamental Limit of Private Information Retrieval for Coded Distributed Storage
• Achieving Maximum Distance Separable Private Information Retrieval Capacity With Linear Codes
• An MDS-PIR Capacity-Achieving Protocol for Distributed Storage Using Non-MDS Linear Codes
• Asymmetry Helps: Improved Private Information Retrieval Protocols for Distributed Storage
• The Capacity of Private Information Retrieval from Coded Databases