TY - JOUR
T1 - t-Private Information Retrieval Schemes Using Transitive Codes
AU - Freij-Hollanti, R.
AU - Gnilke, O. W.
AU - Hollanti, C.
AU - Horlemann-Trautmann, A.
AU - Karpuk, D.
AU - Kubjas, Ivo
PY - 2019/4
Y1 - 2019/4
N2 - Private information retrieval (PIR) schemes for coded storage with colluding servers are presented, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed, and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. In the special case of no server collusion, this rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems. While many PIR schemes in the literature require field sizes that grow with the number of servers and files in the system, we focus especially on the case of a binary base field, for which Reed-Muller codes serve as an important and explicit class of examples.
AB - Private information retrieval (PIR) schemes for coded storage with colluding servers are presented, which are not restricted to maximum distance separable (MDS) codes. PIR schemes for general linear codes are constructed, and the resulting PIR rate is calculated explicitly. It is shown that codes with transitive automorphism groups yield the highest possible rates obtainable with the proposed scheme. In the special case of no server collusion, this rate coincides with the known asymptotic PIR capacity for MDS-coded storage systems. While many PIR schemes in the literature require field sizes that grow with the number of servers and files in the system, we focus especially on the case of a binary base field, for which Reed-Muller codes serve as an important and explicit class of examples.
KW - Servers
KW - Information retrieval
KW - Linear codes
KW - Electronic mail
KW - Indexes
KW - Private Information Retrieval
KW - transitive codes
KW - Reed-Muller codes
UR - http://www.scopus.com/inward/record.url?scp=85053616526&partnerID=8YFLogxK
U2 - 10.1109/TIT.2018.2871050
DO - 10.1109/TIT.2018.2871050
M3 - Article
SN - 0018-9448
VL - 65
SP - 2107
EP - 2118
JO - IEEE Transactions on Information Theory
JF - IEEE Transactions on Information Theory
IS - 4
M1 - 8469024
ER -