New crypto idea implemented in gpg

[Brent R. Waters]

I am a graduate student at Princeton University working under Ed Felten. I
recently worked on a new type of cryptography scheme that I call an
Incomparable Public Key scheme and implemented the idea in gpg.

The basic idea is that some private decryption keys there can be several
equivalent, but incomparable public keys. This means that data encrypted
with any one of the equivalent public keys can be decrypted by the one
private key, but holders of public keys will not be able to tell if they
are equivalent (thus the incomparable part).

This is helpful in the following example. Suppose you are
anonymously receiving encrypted messages by instructing different senders
to an anonymous newsgroup such as "alt.anonymous.messages". If you were to
give two different senders the same public key to encrypt messages with
this could potentially result in a loss of privacy. For instance, suppose
I had one sender send information about Princeton U. and instructed
another to give me information on cryptography. If they got together they
could possibly deduce my true identity from their combined knowledge.
Worse, if there was a third sender whom I asked to send me information
about 'Joe Millionaire' with the same key and he got together with the
other two I would be embarased that people know about my Reality TV
fascination.

An obvious solution to this problem is to create a new key for every
sender to use. However, for n senders this would require n attempted
decryptions of any message on the newsgroup. If an Incomparable Public Key
scheme were used I could give each sender a different, but equivalent
public key and I could maintain my anonymity while only having to attempt
one decryption per newsgroup message.

Anyway, I implemented this idea into gpg to allow people to try this out
in the real world. The code and a paper describing the idea in more detail
is available at http://www.cs.princeton.edu/~bwaters/research/ . I would
like to hear questions or comments from anyone who gets the chance to try
this out.

I should emphasize that this is not part of the standard GuPG line in any
way. I basically took the code a few months ago and put my own idea into
it.

Regards,
Brent Waters

bwaters@cs.princeton.edu


P.S. I am really not a Reality TV fan.