An Oblivious Transfer Protocol with Log-Squared Communication

By Helger Lipmaa. 2005

336 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

XPIR : Private Information Retrieval for Everyone (2016, methodology): “In our library, we have decided to stick to the basic approach for recursion although it would be interesting to develop other optimizations, such as those proposed in [33].”
A Lattice-Based Computationally-Efficient Private Information Retrieval Protocol (2007, background): “For Lipmaa’s scheme, if k = 1024, the computational cost is roughly of one 2048-bit modular multiplication per bit in the database.”
Bandwidth Efficient PIR from NTRU (2014, background): “In [7] Lipmaa presented a different yet quite interesting cPIR scheme that leverages a (length-flexible) additively homomorphic public-key encryption scheme and provides better communication complexity performance.”
Keyword Search and Oblivious Pseudorandom Functions (2005, methodology): “A good choice is to use a PIR scheme with a polylogarithmic communication overhead, such as the scheme of Cachin et al. [4] (based on the Φ-hiding assumption) or the schemes of Cheng [6] or Lipmaa [21] (based on the Paillier and Damgård-Jurik cryptosystems, respectively).”
Cryptography from Anonymity (2006, background): “In recent yea rs, there has been a significant body of work on improving the communication complexity of PIR, either in th e above single-server scenario [41, 10, 42, 26] or using multiple servers [15, 3].”
Delegating computation: interactive proofs for muggles (2008, background): “We note that such a PIR scheme exists for any κ ≥ log |DB| (where |DB| is the database size) under the N -th Residuosity Assumption [48, 40], and under the Φ-Hiding Assumption [20].”
Polynomial Batch Codes for Efficient IT-PIR (2016, methodology): “We view these findings as a generalization and extension of Henry, Huang, and Goldberg’s multi-block IT-PIR queries [34], which are likewise constructed from ramp schemes.”
A Simpler Rate-Optimal CPIR Protocol (2017, methodology): “[10], following earlier protocols [11,16,12,8,13], homomorphically executes a branching program, by using a (w, 1)-CPIR at every internal node of the branching program.”
High-Speed Private Information Retrieval Computation on GPU (2008, methodology): “Lipmaa’s scheme [15] is the outcome of a set of protocols [14, 24, 5] based on homomorphic encryption.”
Single-Database Private Information Retrieval with Constant Communication Rate (2005, background): “Recently, Lipmaa [11] gave a PBR scheme with stated Θ(l m · log 2 n + d · log n) communication complexity for d-bit blocks, where again l m = Ω(log 3−o(1) n).”
On the Computational Practicality of Private Information Retrieval (2006, background): “Lipmaa [49] extends the work of Stern [71].”
Evaluating Branching Programs on Encrypted Data (2007, methodology): “√ Its variant suggested in [34] (resp., [26]) corresponds to a decision tree of depth log N and degree t = 2 √ log N (resp., depth log N and degree t = 2 ).”
A Fast Single Server Private Information Retrieval Protocol with Low Communication Cost (2014, methodology): “– Lipmaa’s protocol [10] requires for each 2 ≤ j ≤ log n (cid:48) , 2 log n (cid:48) − j exponentiations. modular The computational cost is at least c n multiplications for some c depending on log n (cid:48) .”
Efficient Fully Homomorphic Encryption from (Standard) LWE (2011, methodology): “The first polylogarithmic candidate protocol was presented by Cachin, Micali and Stadler [9] and additional polylograithmic protocols were introduced by Lipmaa [24] and by Gentry and Ramzan [20].”
A fast private information retrieval protocol (2008, background): “…has not as good communication performance as other existing protocols, but we show that practical usability of PIR schemes is not as dependent on communication performance as the literature suggests, and that a trade-off between communication and computation leads to much more versatile schemes.”
Distributed Point Functions and Their Applications (2014, methodology): “Single-server protocols with polylogarithmic communication are known to exist under standard cryptographic assumptions [10, 25, 17, 6].”
Optimal Rate Private Information Retrieval from Homomorphic Encryption (2015, methodology): “In [20, 25, 26], one recursively applies a basic (w, 1)CPIR, for a small w, that is based on the cryptosystem of [11].”
Revisiting the Computational Practicality of Private Information Retrieval (2011, methodology): “In addition, the measurements for the single-server PIR schemes [12, 20] used for their comparison was based on estimates derived from openssl speed rsa, which is quite unlike our approach where the comparison is based on analytical expressions for query response times and experimental observations.”