funny maths (was: Re: PIR, anonymous/pseudonymous mail systems etc. )

[Peter Fairbrother]

George Danezis wrote:

> 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).

I've always thought of it more as a way to get sender+recipient anonymity
for email, without necessarily hiding the sender from the recipient. The
latter property may be useful though, and needn't be discarded.

> 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.

If... 

I take the view that "they" want the power to examine everything, not just
anything, and may eventually get it. Consequently I discard all solutions
that include "trusted" hardware (who's to say the user should trust it?) or
MIX based approaches that rely on "someone" not being observed or
compromised (and who's to say the user should trust that someone?).

If funny maths isn't good enough yet to implement anonymity usefully then we
need better funny maths. I don't know about anyone else, but I'm working on
that.  :)

It's not a final solution though, because then "they" will want to know the
keys or whatever, so we need more funny maths to let people communicate
invisibly, not just anonymously. I'm (longer-term) working on that too.

Is funny maths capable of doing the job? For the first requirement I'm
fairly sure it soon will be, for the second, I think so, we'll see. Funny
maths is the only thing I can think of that I'd trust when my life depended
on it, not a remailer or some "trusted' hardware run by people I don't know.

-- Peter Fairbrother

peter@m-o-o-t.org
http://www.m-o-o-t.org

[included for completeness]:

> 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
>