Post by Shannon Wireless

In this paper, the authors propose three #private #information #retrieval (#PIR) protocols for #distributed #storage #systems (#DSSs), where data is stored using an arbitrary #linear #code. The first two protocols, namely Protocol 1 and Protocol 2, achieve privacy for the scenario with #noncolluding #nodes. Protocol 1 requires a file size that is exponential in the number of files in the system, while Protocol 2 requires a file size that is independent of the number of files and is hence simpler. They prove that, for certain linear codes, Protocol 1 achieves the #maximum #distance #separable (#MDS) PIR #capacity, while Protocol 2 achieves the #asymptotic #MDS-#PIR #capacity. In particular, they provide a necessary and sufficient condition for a code to achieve the MDS-PIR capacity with Protocols 1 and 2 and prove that #cyclic #codes, #Reed-#Muller (#RM) codes, and a class of #distance-#optimal #local #reconstruction #codes achieve both the finite MDS-PIR capacity and the asymptotic MDS-PIR capacity with Protocols 1 and 2, respectively. Furthermore, they present a third protocol, Protocol 3, for the scenario with multiple #colluding #nodes, which can be seen as an improvement of a recently introduced protocol. Similar to the noncolluding case, they provide a necessary and sufficient condition to achieve the maximum possible PIR rate of Protocol 3. Moreover, they provide a particular class of codes that is suitable for this protocol and show that RM codes achieve the maximum possible PIR rate for the protocol. For all three protocols, they present an algorithm to optimize their PIR rates. ---- Kumar Siddhartha; Hsuan-Yin Lin; Eirik Rosnes; Alexandre Graell i Amat More details can be found at this link: https://lnkd.in/gn2xWUNQ