[messaging] PIR (in Pynchon Gate)

[Trevor Perrin]

On Sun, Mar 23, 2014 at 11:48 PM, Brian Warner <warner at lothar.com> wrote:
> On 3/23/14 4:59 PM, Trevor Perrin wrote:
>
>> My vague understanding of PIR is that "single-server" schemes are less
>> practical than just sending the whole database, but there are
>> "multi-server" schemes which are somewhat-efficient and secure as long
>> as all servers don't collude. (Is that right? Could anyone explain PIR
>> in a separate thread?)
>
> I can explain the multi-server PIR scheme that the late Len Sassaman
> created for Pynchon Gate[1] (his anonymous-remailer mailbox scheme).

Thanks!  Seems potentially practical.  And the paper Stefan referenced
(Devet / Goldberg / Heninger [1]) looks like it can add robustness for
PIR-server misbehavior.

So for "introduction certificates" [2], there could be a bunch of
directories publishing intro certs from users.  These directories
would snapshot themselves periodically, and various "PIR mirrors"
would fetch the snapshots.

A user could lookup another user's intro-cert by public-key
fingerprint, without revealing which one, by querying several PIR
mirrors.

The user won't know which PIR slot to retrieve, a priori.  But a
multilevel index could be stored in the PIR slots.  The user could
fetch a top-level index which says which slots store the next-level
indexes for different fingerprint ranges, do a PIR query for the
relevant slot, and repeat until getting a slot containing the intro
cert.

Seem reasonable?


Trevor


[1] http://www.cypherpunks.ca/~iang/pubs/orpir-usenix.pdf
[2] https://moderncrypto.org/mail-archive/messaging/2014/000113.html