[tor-dev] Scaling tor for a global population

[Nikita Borisov]

On Tue, Sep 30, 2014 at 12:04 AM, isis <isis at 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
-- 
Nikita Borisov - http://hatswitch.org/~nikita/
Associate Professor, Electrical and Computer Engineering
Tel: +1 (217) 244-5385, Office: 460 CSL