Optimally Robust Private Information Retrieval

By Casey Devet, Ian Goldberg, Nadia Heninger. 2012

244 citations recorded by the source corpus.

How researchers see this paper

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

Citations in the corpus

PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “This approach is further studied by Lueks and Goldberg [59] in the context of Goldberg’s IT-PIR scheme [41].”
RAID-PIR: Practical Multi-Server PIR (2014, methodology): “Some of these requirements may require signiﬁ-cant extensions to existing PIR schemes, or a new scheme; for example, several works study PIR schemes which are robust to benign and/or byzantine failures [Gol07, DGH12, DG14].”
One (Block) Size Fits All: PIR and SPIR with Variable-Length Records via Multi-Block Queries (2013, background): “[20] Suppose the user encodes her query using secret sharing polynomials of degree (at most) t , and that k ≤ servers respond.”
PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval (2011, methodology): “We use an implementation [13] of the multi-server PIR scheme by Goldberg [12] and compute the server computation, total communication, and client computation, for”
High-Speed Private Information Retrieval Computation on GPU (2008, result): “The second is a replicated-database PIR implementation presented at IEEE Security & Privacy 2007 [12].”
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].”
DP5: A Private Presence Service (2015, background): “Goldberg [20] demonstrated a PIR protocol with only marginally larger communication costs: Npirmax · (rw+ b) bits, where w is the bitlength of the underlying finite field (typically w = 8).”
Private Information Retrieval from Coded Databases with Colluding Servers (2016, methodology): “Our techniques extend nicely to the case of non-responsive and Byzantine server models, which have previously been studied in the case of replication storage [10, 6].”
The Capacity of Private Information Retrieval from Byzantine and Colluding Databases (2017, background): “Reference [24] observes that allowing for list decoding instead of unique decoding enlarges the feasible set up to B < N − T − 1.”
Privacy-Preserving Queries over Relational Databases (2010, background): “There is therefore a need for an extension to a more expressive data access model, and to a model that enables data retrieval from structured data sources, such as from a relational database.”
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, ”
This Paper Is Included in the Proceedings of the 12th Usenix Symposium on Operating Systems Design and Implementation (osdi '16). Unobservable Communication over Fully Untrusted Infrastructure Unobservable Communication over Fully Untrusted Infrastructure (unknown): “However, the size of the collection would need to match 1 IT-PIR schemes [36] [48] [59] are an efficient alternative to CPIR but rely on multiple servers, at least one of which must be correct.”
Polynomial Batch Codes for Efficient IT-PIR (2016, unknown): “The basic form of this Shamir-based protocol was proposed by Goldberg [29] and was subsequently extended and improved in several papers [22] [34] [35] [41].”
The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication Efficiency (2014, methodology): “[12], the client can decode the database record in polynomial time as long as the number of Byzantine servers v is bounded by v < k − t − 1.”
Robust private information retrieval on coded data (2017, methodology): “The setting in which nodes can be byzantine (malicious) and store replicated data was considered in [17]–[19] and robust PIR schemes were devised using locally decodable codes.”
Robust Private Information Retrieval from Coded Systems with Byzantine and Colluding Servers (2018, background): “The problem of constructing PIR schemes on replicated data in which some servers can be byzantine (malicious) was considered in [16]–[18].”