A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers

Abstract : Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000, it is well-known that information the-oretically secure private information retrieval schemes can be built using locally decodable codes. In this paper, we construct a Byzantine ro-bust PIR scheme using the multiplicity codes introduced by Kopparty et al. Our main contributions are on the one hand to avoid full replica-tion of the database on each server; this significantly reduces the global redundancy. On the other hand, to have a much lower locality in the PIR context than in the LDC context. This shows that there exists two different notions: LDC-locality and PIR-locality. This is made possible by exploiting geometric properties of multiplicity codes.
Complete list of metadatas

Cited literature [15 references]  Display  Hide  Download

https://hal.inria.fr/hal-01094807
Contributor : Daniel Augot <>
Submitted on : Saturday, December 13, 2014 - 12:14:47 PM
Last modification on : Thursday, November 21, 2019 - 6:32:53 PM
Long-term archiving on: Saturday, March 14, 2015 - 10:20:31 AM

Files

cans-final.pdf
Files produced by the author(s)

Identifiers

Collections

Citation

Daniel Augot, Françoise Levy-Dit-Vehel, Abdullatif Shikfa. A Storage-Efficient and Robust Private Information Retrieval Scheme Allowing Few Servers. 13th International Conference, Cryptology and Network Security (CANS), Oct 2014, Heraklion, Greece. pp.222 - 239, ⟨10.1007/978-3-319-12280-9_15⟩. ⟨hal-01094807⟩

Share

Metrics

Record views

1006

Files downloads

286