Abstract
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.
| Original language | English |
|---|---|
| Journal | SIAM Journal on Applied Algebra and Geometry |
| Volume | 1 |
| Issue number | 1 |
| Pages (from-to) | 647-664 |
| Number of pages | 18 |
| DOIs | |
| Publication status | Published - 2017 |
Bibliographical note
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 (ragnar.freij@aalto.fi, oliver.gnilke@aalto.fi, camilla.hollanti@aalto.fi). ‡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 (da.karpuk@uniandes.edu.co).
Publisher Copyright:
© 2017 Society for Industrial and Applied Mathematics Publications. All rights reserved.
Copyright:
Copyright 2021 Elsevier B.V., All rights reserved.
Keywords
- Distributed storage systems
- Generalized Reed–Solomon codes
- Private information retrieval