On the Computational Practicality of Private Information Retrieval

By Radu Sion, Bogdan Carbunar. 2006

214 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.

1. Peter Kairouz
2. Jakub Konecný
3. Chaoyang He
4. Yang Liu
5. Jianyu Wang
6. Tian Li
7. Qiang Yang
8. H. Brendan McMahan

Citations in the corpus

• Advances and Open Problems in Federated Learning (2019, background): “The main roadblocks to the applicability of PIR have been the following: cPIR has very high computational cost [361], while the non-colluding parties setting has been difficult to achieve convincingly in industrial scenarios.”
• XPIR : Private Information Retrieval for Everyone (2016, background): “In NDSS’07, Sion and Carbunar presented a paper on cPIR practicality [1].”
• Revisiting the Computational Practicality of Private Information Retrieval (2011, methodology): “Besides, the projections from [28] assume that all PIR schemes make intractability assumptions that would necessitate the use of larger keys when today’s hardware and networks improve.”
• The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication Efficiency (2014, background): “In a 2007 study, Sion and Carbunar concluded that no single-server PIR protocol would likely outperform this trivial download PIR protocol [30].”
• Enabling Security in Cloud Storage SLAs with CloudProof (2011, background): “The chain hash thus depends not only on the current attestation but also on the history of all the attestations for that block so far (because it includes the previous chain hash).”
• Private Information Retrieval With Side Information (2017, background): “However, computational PIR schemes typically suffer from heavy computational cost, and require homomorphic encryption [22].”
• 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.”
• Pors: proofs of retrievability for large files (2007, background): “Recent work suggests that PIR schemes may be no more efficient in practice than transferring all of F̃ [39].”
• Bandwidth Efficient PIR from NTRU (2014, background): “In 2007 the computational practicality of PIRs was raised by Sion and Carbunar [20] who concluded that no existing construction is as efficient as the trivial PIR scheme.”
• Sublinear Scaling for Multi-Client Private Information Retrieval (2015, methodology): “Sion and Carbunar [20] found that it would always be faster to simply download the entire database than to use Kushilevitz and Ostrovsky’s CPIR scheme [14].”
• Private queries in location based services: anonymizers are not necessary (2008, methodology): “[24] showed that the computational time of PIR may be longer than the time required for an oblivious transfer of the database.”
• High-Speed Private Information Retrieval Computation on GPU (2008, background): “Indeed, in [23], Sion and Carbunar show that in a large variety of situations number theory schemes are much slower than the trivial solution to the PIR problem (i.”
• PRISM - Privacy-Preserving Search in MapReduce (2012, background): “Private Information Retrieval: Private Information Retrieval (and similarly oblivious transfer and oblivious RAM) has received a lot of attention [9, 13, 19, 22, 29, 32, 33, 35].”
• Achieving Efficient Query Privacy for Location Based Services (2010, background): “Requiring that the smartphone download the entire database for each request so as not to provide information about its current location is clearly not practical [31]; nor is requiring that it periodically download just the updated data to ensure accuracy of results, given the practical bandwidth lim”
• First CPIR Protocol with Data-Dependent Computation (2009, background): “Based on empirical research, Carbunar and Sion [6] argued that in the foreseeable future all linearcommunication CPIR protocols will be at least one order of magnitude slower than the trivial CPIR protocol, where the server just transfers the whole database to the client.”
• Optimally Robust Private Information Retrieval (2012, background): “In 2007, Sion and Carbunar [36] opined that, given trends in computational power and network speeds, it would always be faster to send the whole database to the client than to use PIR to process it.”
• 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): “Furthermore, some CPIR schemes (e.g., [10]) have low enough computational costs that their processing latency is actually lower than transferring the entire collection over today's networks (this was believed to be an unlikely scenario [125]).”