TY - JOUR
T1 - Private information retrieval from coded databases with colluding servers
AU - Freij-Hollanti, Ragnar
AU - Gnilke, Oliver W.
AU - Hollanti, Camilla
AU - Karpuk, David A.
N1 - Funding Information:
∗Received by the editors November 7, 2016; accepted for publication (in revised form) August 2, 2017; published electronically November 14, 2017. http://www.siam.org/journals/siaga/1/M110256.html Funding: The fourth author’s work was supported by Academy of Finland grant 268364. The third author’s work was supported by Academy of Finland grants 276031, 282938, and 303819. †Department of Mathematics and Systems Analysis, Aalto University, P.O. Box 11100, FI-00076 AALTO, Espoo, Finland ([email protected], [email protected], [email protected]). ‡Department of Mathematics and Systems Analysis, Aalto University, P.O. Box 11100, FI-00076 AALTO, Espoo, Finland. Current address: Departamento de Matemáticas, Carrera 1 No. 18a 10, Edificio H, Primer Piso, 111711 Bogotá, Colombia ([email protected]).
Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics Publications. All rights reserved.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
PY - 2017
Y1 - 2017
N2 - We present a general framework for private information retrieval (PIR) from arbitrary coded databases that allows one to adjust the rate of the scheme to the suspected number of colluding servers. If the storage code is a generalized Reed–Solomon code of length n and dimension k, we design PIR schemes that achieve a PIR rate of n-(k+t-1) while protecting against any t colluding servers, for n any 1 ≤ t ≤ n - k. This interpolates between the previously studied cases of t = 1 and k = 1 and achieves PIR capacity in both of these cases asymptotically as the number of files in the database grows.
AB - We present a general framework for private information retrieval (PIR) from arbitrary coded databases that allows one to adjust the rate of the scheme to the suspected number of colluding servers. If the storage code is a generalized Reed–Solomon code of length n and dimension k, we design PIR schemes that achieve a PIR rate of n-(k+t-1) while protecting against any t colluding servers, for n any 1 ≤ t ≤ n - k. This interpolates between the previously studied cases of t = 1 and k = 1 and achieves PIR capacity in both of these cases asymptotically as the number of files in the database grows.
KW - Distributed storage systems
KW - Generalized Reed–Solomon codes
KW - Private information retrieval
UR - https://www.scopus.com/pages/publications/85048570565
U2 - 10.1137/16M1102562
DO - 10.1137/16M1102562
M3 - Journal article
AN - SCOPUS:85048570565
SN - 2470-6566
VL - 1
SP - 647
EP - 664
JO - SIAM Journal on Applied Algebra and Geometry
JF - SIAM Journal on Applied Algebra and Geometry
IS - 1
ER -