RT info:eu-repo/semantics/article
T1 Private information retrieval from locally repairable databases with colluding servers
A1 Martínez Peñas, Umberto
K1 Distributed storage
K1 Linearized Reed-Solomon codes
K1 Locally repairable codes
K1 Network coding
K1 Private information retrieval
AB We consider information-theoretical private information retrieval (PIR) from a coded database with colluding servers.We target, for the first time, locally repairable storage codes(LRCs). We consider any number of local groups g, localityr, local distance δ and dimension k. Our main contribution isa PIR scheme for maximally recoverable (MR) LRCs basedon linearized Reed–Solomon codes, which achieve the smallest field sizes among MR-LRCs for many parameter regimes.In our scheme, nodes are identified with codeword symbolsand servers are identified with local groups of nodes. Onlylocally non-redundant information is downloaded from eachserver, that is, only r nodes (out of r + δ − 1) are downloaded per server. The PIR scheme achieves the (download)rate R = (N −k−rt+1)/N, where N = gr is the length of theMDS code obtained after removing the local parities, and forany t colluding servers such that k+rt ≤ N. For an unboundednumber of stored files, the obtained rate is strictly larger thanthose of known PIR schemes that work for any MDS code.Finally, the obtained PIR scheme can also be adapted whencommunication between the user and each server is performedvia linear network coding, achieving the same rate as previous PIR schemes for this scenario but with polynomial finitefield sizes, instead of exponential. Our rates are equal to thoseof PIR schemes for Reed–Solomon codes, but Reed–Solomoncodes are incompatible with the MR-LRC property or linearnetwork coding, thus our PIR scheme is less restrictive in itsapplications.
PB Elsevier
SN 1071-5797
YR 2024
FD 2024
LK https://uvadoc.uva.es/handle/10324/72945
UL https://uvadoc.uva.es/handle/10324/72945
LA eng
NO Finite Fields and Their Applications, 2024, vol. 96, 102421
NO Producción Científica
DS UVaDOC
RD 23-dic-2024