Robust Information-Theoretic Private Information Retrieval

By Amos Beimel, Yoav Stahl. 2002

123 citations recorded by the source corpus.

Subfields: Artificial Intelligence, Computational Theory and Mathematics

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Artificial Intelligence

In Computational Theory and Mathematics

Citations in the corpus

Staircase-PIR: Universally Robust Private Information Retrieval (2018, methodology): “guaranteedbecause each sub-query is padded with a different random vector. IV. FROM SECRET SHARING TO PIR The connection between secret sharing and PIR has been studied in the literature, e.g., [16], [27], [34]. Our Staircase-PIR construction was obtained using Staircase codes for communication efﬁc”
Private Information Retrieval From MDS Coded Data in Distributed Storage Systems (2016, background): “Robust PIR was also studied in [19] and [20].”
The Capacity of Robust Private Information Retrieval With Colluding Databases (2016, background): “bases may not respond [28] (Robust PIR); where both the privacy of the user and the databases must be protected [1] (Symmetric PIR); where only one database holds all the messages and all other databases hold independent information [29]; where retrieval operations are unsynchronized [30]; and where”
Revisiting the Computational Practicality of Private Information Retrieval (2011, background): “Subsequent work has mostly focused on improving PIR’s communication complexity bounds [13, 14], while some others [4, 8, 19, 22] have addressed such problems as using amortization and preprocessing to reduce server-side computational overheads and improving query robustness, amongst others.”
Achieving Efficient Query Privacy for Location Based Services (2010, background): “Using at least two replicated databases, and some form of restrictions on how the databases can communicate, PIR schemes with information theoretic privacy are possible, and sometimes hold attractive properties like byzantine robustness [3,15].”
The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, background): “The BPIR problem was introduced in [23].”
Polynomial Batch Codes for Efficient IT-PIR (2016, methodology): “The following observation follows immediately by inspection of the u -ary encoding procedure.”
A geometric approach to information-theoretic private information retrieval (2005, methodology): “We review the definition of robust PIR [9].”
Scalable and Private Media Consumption with Popcorn (2016, background): “Research on this problem, first posed by [14], has pursued the dual goals of identifying the highest number of faulty servers that can be tolerated and of reducing the computational burden that faulttolerance imposes on clients [25, 36].”
Sublinear Scaling for Multi-Client Private Information Retrieval (2015, background): “They achieve a communication cost much smaller than the size of the database, and modern ones additionally achieve robustness—even if some of the servers are unresponsive, buggy, or actively malicious, the client can nonetheless retrieve her information (and identify the misbehaving servers) [2, 7, ”