TY - GEN
T1 - A storage-efficient and robust private information retrieval scheme allowing few servers
AU - Augot, Daniel
AU - Levy-Dit-Vehel, Françoise
AU - Shikfa, Abdullatif
N1 - Publisher Copyright:
© Springer International Publishing Switzerland 2014.
PY - 2014/1/1
Y1 - 2014/1/1
N2 - Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000 [11], it is well-known that information theoretically secure private information retrieval schemes can be built using locally decodable codes [15]. In this paper, we construct a Byzantine robust PIR scheme using the multiplicity codes introduced by Kopparty et al. [12]. Our main contributions are on the one hand to avoid full replication 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.
AB - Since the concept of locally decodable codes was introduced by Katz and Trevisan in 2000 [11], it is well-known that information theoretically secure private information retrieval schemes can be built using locally decodable codes [15]. In this paper, we construct a Byzantine robust PIR scheme using the multiplicity codes introduced by Kopparty et al. [12]. Our main contributions are on the one hand to avoid full replication 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.
UR - https://www.scopus.com/pages/publications/84911362777
U2 - 10.1007/978-3-319-12280-9_15
DO - 10.1007/978-3-319-12280-9_15
M3 - Conference contribution
AN - SCOPUS:84911362777
T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
SP - 222
EP - 239
BT - Cryptology and Network Security - 13th International Conference, CANS 2014, Proceedings
A2 - Gritzalis, Dimitris
A2 - Kiayias, Aggelos
A2 - Askoxylakis, Ioannis
PB - Springer Verlag
T2 - 13th International Conference on Cryptology and Network Security, CANS 2014
Y2 - 22 October 2014 through 24 October 2014
ER -