Technical Program

Paper Detail

Paper Title Private Information Retrieval from Locally Repairable Databases with Colluding Servers
Paper IdentifierTU3.R3.4
Authors Umberto Martinez-Penas, University of Toronto, Canada
Session Private Information Retrieval II
Location Monge, Level 3
Session Time Tuesday, 09 July, 14:30 - 16:10
Presentation Time Tuesday, 09 July, 15:30 - 15:50
Manuscript  Click here to download the manuscript
Abstract Information-theoretical private information retrieval (PIR) is considered from a coded database with colluding servers. The storage code is a locally repairable code (LRC) with maximal recoverability (MR), and in particular, with optimal global minimum distance, for arbitrary code parameters: Number of local groups $ g $, locality $ r $, local distance $ \delta $, dimension $ k \leq gr $ and length $ n = g(r + \delta - 1) $. Servers are identified bijectively with local groups, and only locally non-redundant information is considered and downloaded from each server, that is, only $ r $ nodes (out of $ r+\delta-1 $) are considered per server. When the remaining MDS code, after removing all locally redundant nodes, is a linearized Reed-Solomon code, a PIR scheme is provided achieving the (download) rate $ R = (N - k - rt + 1)/N $, where $ N = gr = n - g(\delta - 1) $ is the length of the restricted MDS code, for any $ t $ colluding servers such that $ k + rt \leq N $. The field size is roughly $ g^r $, polynomial in the number of servers $ g $. Assume an arbitrarily large number of stored files. If $ N - k - rt = 0 $, the rate $ R = 1/N $ is the highest known and coincides with that of previous PIR schemes that work for any MDS storage code. If $ N - k - rt > 0 $, the achieved rate $ R > 1/N $ coincides with the best known rate of PIR schemes for MDS storage codes (but which do not work for LRCs or linearized Reed-Solomon storage codes) and is always strictly higher than that of known PIR schemes that work for arbitrary MDS storage codes.