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

[Adam Back]

More on Peter Fairbrother's discussion about PIR related pseudonymous
/ anonymous email systems:

I see in your earlier post you talk about PIR and as you're talking
about computational security and only trusting sender and recipient,
so presumably you're exploring single database computational PIR.
Single db cPIRs have interesting security properties but are very
bandwidth and CPU intensive.

One thing you can do to reduce that problem is to partition users into
sets so that an observer can make observations that someone in a group
of say 100 users received an email but not know which one.  This is a
trade-off between CPU and message overhead vs security (the security
of the anonymity being related to the size of the anonymity set).

I thought about this problem a bit (pseudonymous email -- replyable
anonymous email) a year or so ago and think that the two way
pseudonymous email problem is actually slightly simpler than full
blown PIR.  The difference I observed is that PIR involves (in the
base case):

- writer is identified (no attempt to obscure IP address)
- reader is identified (no attempt to obscure IP address)
- the data block written is observable to the database (but encrypted for
  recipient for this application)
- but the data block read is hidden from the database

(there are PIR schemes for hidden writing also, but they are yet more
expensive being essentially to re-write the entire database).

for pseudonymous email on the other hand there are some other
potentially cheaper to implement possibilities than single-db cPIR:

- writer could be anonymous to the database (behind IP obscurity,
  mixmaster)
- reader is identified (no attempt to obscure IP address)
- some function could be used so that only recipient or a collusion of
  system entities could identify where email to a given recipient
  would be written.

This makes reading efficient, fast downloads etc.

Or you could use this arrangement:

- writer could be anonymous to the database (behind IP obscurity,
  mixmaster)
- reader could be pseudonymous to database (behind interactive IP
  obscurity)
- database could only observe volume of mail received by pseudonymous entities

this later arrangement is similar to the approach used by the 2nd
generation, but no longer operating Zero-Knowledge Systems
pseudonymous mail system I designed.  Obviously the interactive IP
obscurity had close synergies to the freedom network which was why
that design made a good fit in that scenario.

Adam