A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol

By Carlos Aguilar Melchor, Philippe Gaborit. 2007

126 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

Bandwidth Efficient PIR from NTRU (2014, methodology): “This was later followed by a lattice based cPIR construction by Aguilar-Melchor and Gaborit [30].”
PIR-Tor: Scalable Anonymous Communication Using Private Information Retrieval (2011, methodology): “We chose standard security parameters for the CPIR scheme [1] (`0 = 19 and N = 50), and computed the client/server computation times and communication”
A fast private information retrieval protocol (2008, background): “This opens the path to computationally efficient PIR schemes, but the approach they use leads to additions over very large vectors.”
Privacy-Preserving Queries over Relational Databases (2010, background): “Note that even in scenarios where collusion cannot be forestalled, our system can still use any computational PIR protocol; recent such protocols [1, 31] offer considerable efficiency improvements over previous work in the area.”
Optimally Robust Private Information Retrieval (2012, background): “In fact, recent work by Olumofin and Goldberg [29] demonstrates that a more recent computational PIR scheme by Aguilar Melchor and Gaborit [1] is an order of magnitude faster than trivial download, while information-theoretic (IT) PIR can be two to three orders of magnitude faster.”
The Best of Both Worlds: Combining Information-Theoretic and Computational PIR for Communication Efficiency (2014, methodology): “Protocol Query Cost Response Cost AG07 [2] ( 6NwAG ) n 6s Recursive AG07 [2] d ( 6NwAG ) d √ n 6s G07 [15] `wGn `s Our hybrid (with AG07 and G07) `d ( 6NwAG ) d−1 d d √ wG d √ n `6d−1s”
Cryptanalysis of a homomorphic encryption scheme from ISIT 2008 (2012, background): “Since its publication, several homomorphic encryptions have been designed for the e-voting system [5], [24], [9], private information retrieval protocol [19], [21] and so on.”
Sublinear Scaling for Multi-Client Private Information Retrieval (2015, background): “Later, Olumofin and Goldberg [17] noted that a more modern CPIR scheme by Aguilar Melchor and Gaborit [1], as well as a number of IT-PIR schemes, are orders of magnitude faster than the trivial download scheme.”
High-Speed Private Information Retrieval Computation on GPU (2008, methodology): “We encourage the reader to read in the original paper [2] the full description of the protocol (which is given with a toy example) and the privacy and correctness proofs.”
Scalable and Private Media Consumption with Popcorn (2016, methodology): “A second line of investigation, motivated by a paper of Sion and Carbunar [70]—which noted that the cost of CPIR may be worse than the naive solution of transferring the entire library—has focused on reducing the computational load of CPIR [7, 8, 56, 75] not by reducing the number of operations perf”
Single-Database Private Information Retrieval from Fully Homomorphic Encryption (2013, background): “In 2007, Aguilar-Melchor and Gaborit [1], [2] presented a lattice-based computationally-efficient PIR protocol, in which the computational cost is a few thousand bitoperations per bit in the database.”
Efficient Computationally Private Information Retrieval from Anonymity or Trapdoor Groups (2010, methodology): “Similarly the response vectors for R1, D3, and D2 are [0 1 1 0], [1 1 1 0], and [0 1 0 0].”
First CPIR Protocol with Data-Dependent Computation (2009, unknown): “For related work on computation-efficient CPIR protocols, see for example [10,2].”