On Tue, Sep 30, 2014 at 12:04 AM, isis isis@torproject.org wrote:
[1]: I assume that we need replication in Tor's use case. There are papers, such as the following:
Kushilevitz, Eyal, and Rafail Ostrovsky. "Replication is not needed: Single database, computationally-private information retrieval." 2013 IEEE 54th Annual Symposium on Foundations of Computer Science. IEEE Computer Society, 2013. http://www.cs.fiu.edu/~carbunar/teaching/cis5374/slides/pir-single.pdf for which the research doesn't apply because it was aimed at computationally-hiding PIR schemes, and obviously Tor aims for information theoretic security. Other than the PIR-Tor paper, I haven't found any literature which analyses PIR for anything close to Tor's use case. (Although I'd be stoked to hear about any such papers.)
The current Tor design relies heavily on computational assumptions in all of its cryptography, so I don't think that the Tor network setting is a reason to use information-theoretic rather than computational PIR. We advocated ITPIR because it is much more efficient and because collusion among your three guards was already a significant problem. With the move to a single guard, that argument no longer makes as much sense. We do have an analysis in the paper of the computational PIR scenario, but it does impose significantly more (computational) overhead on the directory mirrors.
- Nikita