Replication is not needed: single database, computationally-private information retrieval

By Eyal Kushilevitz, Rafail M. Ostrovsky. 1997

Subfields: Information Retrieval & Search, Privacy & Security

How researchers see this paper

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

In Information Retrieval & Search

1. Ian Goldberg
2. Yuval Ishai
3. Helger Lipmaa
4. Ryan Henry
5. Carlos Aguilar Melchor
6. Amos Beimel
7. Casey Devet
8. Philippe Gaborit

In Privacy & Security

1. Peter Kairouz
2. Dan Boneh
3. Badih Ghazi
4. Amos Beimel
5. Kobbi Nissim
6. Yuval Ishai
7. Adrià Gascón
8. Rasmus Pagh

Citations in the corpus

• Advances and Open Problems in Federated Learning (2019, background): “MPC approaches to PIR break down into two main categories: computational PIR (cPIR), in which a single party can execute the entire server side of the protocol [249], and information theoretic PIR (itPIR), in which multiple non-colluding parties are required to execute the server side of the protoco”
• Private Stateful Information Retrieval (2018, methodology): “In this work, we are interested in single-server PIR with computational security as first considered by Kushilevitz and Ostrovsky [36].”
• PIR with Compressed Queries and Amortized Query Processing (2018, methodology): “This protocol assumes a CPIR scheme with the API given in Figure 1.”
• Efficient Private File Retrieval by Combining ORAM and PIR (2014, methodology): “Our hybrid construction will be different from traditional ORAM in one important way: it requires computation on the server side.”
• Searchable symmetric encryption: Improved definitions and efficient constructions (2006, unknown): “We review existing security definitions for searchable encryption, including IND2-CKA [17] and the simulation-based definition in [13], and highlight their shortcomings.”
• Optimal Rate Private Information Retrieval from Homomorphic Encryption (2015, methodology): “This general strategy was introduced in [22], albeit with an inefficient basic (w, 1)-CPIR protocol (that resulted in super-polylogarithmic communication for the recursive construction), and it has been used in many subsequent works.”
• Linear Batch Codes (2014, background): “In anm-out-of-n CPIR (computationally-private information retrieval [7]), the client wants to retrieve m elements from an n element database without the storage provider getting to know which elements were retrieved.”
• Fully homomorphic SIMD operations (2012, methodology): “The plaintext underlying the returned ciphertext c consists of l components, where the k th component is given by If there is only one match per component then we have recovered the matching indices and hence can recover the actual data by engaging in a PIR protocol [5,18].”
• A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol (2007, methodology): “When representing the database as a matrix, instead of using the load balancing technique, it is possible to use the PIR scheme recursively as Kushilevitz and Ostrovsky proposed in [4].”
• Breaking the O(n/sup 1/(2k-1)/) barrier for information-theoretic Private Information Retrieval (2002, methodology): “Recursion was used previously in PIR protocols [1, 10, 25]; however, our recursion is somewhat more sophisticated.”
• Delegating computation: interactive proofs for muggles (2008, unknown): “[46]).”
• An Oblivious Transfer Protocol with Log-Squared Communication (2005, methodology): “The first CPIRn 1 protocol with sublinear communication, O(2sqrtlog(2;n) sqrtlog(2;k)), was proposed by Kushilevitz and Ostrovsky in [ KO97 ].”
• Function Secret Sharing: Improvements and Extensions (2016, background): “The third model, introduced in [24], assumes that the database is held by a single server and security is again computational.”
• Homomorphic Encryption (2017, background): “PIR and other private queries.”