PIR, anonymous/pseudonymous mail systems (Re: [OT-ish] How big is the UK 'net?)

[George Danezis]

PIR is usually thought as a replacement for receiver anonymous communications 
(the ability to reply to an anonymous email without knowing who the recipient 
will be).
The idea is that one writes an email to a database (using a forward anonymous 
system if they wish) and the receiver uses a PIR scheme to retrieve the 
document "anonymously". If one has a full duplex (sender & receiver) anonymous 
channel, then PIR can be implemented using simple engineering instead of funny 
maths.

As Adam notes number theoretic algorithms for PIR is expensive in bandwidth 
and CPU terms. For these reasons in the last Privacy Enhancing Technologies 
workshop (PET2002) quite a few people proposed implementing PIR on tamper 
proof cryptographic modules (including the infamous IBM4758). This minimizes 
the (long term) cost of running such a database, while maintaining most of the 
nice properties.

"Almost Optimal Private Information Retrieval"
                     Dmitri Asonov, Johann-Christoph Freytag

"Unobservable Surfing on the World Wide Web: Is Private Information
                     Retrieval an alternative to the MIX based Approach?"
                     Dogan Kesdogan, Mark Borning, Michael Schmeink

"Prototyping an Armored Data Vault: Rights Management on Big Brother's
                     Computer"
                     Alex Iliev, Sean Smith

Hope the above helps,

George Danezis