Re: MixMinion Status

[Zooko <zooko@zooko.com>]

> |In practice, mail programs such as PGP tend to include the recipient's
> |identity in their header information. Even if headers are stripped, David
> |Hopwood has pointed out in the case of RSA that because different RSA
> |public keys have different moduli, a stream of ciphertext taken modulo
> |the ``wrong'' modulus will tend to have a distribution markedly different
> |from the same stream taken modulo the ``right'' modulus. This allows an
> |adversary to search through a set of possible public keys to find the one
> |which is the best fit for any ciphertext, even if OAEP or similar padding
> |is used.

This reminds me of an idea that I came up with for a related reason.

Suppose you are sending messages to a peer, and some of the messages are PK-
encrypted but others are symmetrically encrypted.  (In fact, this was the case in
a protocol [1] I was designing for Mnet [2] nee Mojo Nation.)

It would be nice if a passive eavesdropper couldn't tell the difference between 
these two kinds of messages.  It occurred to me that you could generate an RSA 
modulus which had the most-significant 80 bits all "1" bits.  (You could do this 
pretty efficiently.)  Then, making certain assumptions about the value that you 
are exponentiating, the resulting ciphertext should be statistically 
indistinguishable from a random string.  I think.

This same technique would perhaps help with "recipient-hiding".

There was actually a third potential use for this idea, which is that if you are 
trying to generate a random number less than some number N which *isn't* close 
to a power of 2, then there is no obvious way to do it so that the number is 
evenly distributed among possible numbers *and* the time that you take to do it 
is constant!

Normally this doesn't matter because the time that you take to do it is strongly 
related to N and N is normally "public" (not-recipient-anonymous) information, 
but it might matter if, say, you were generating agnostic Chaumian blinded 
tokens for a recipient-anonymous token server to sign.  :-)

Okay, I think there should definitely be a category of things called "Possible 
Research Topics that We Came Up With While Designing MixMinion But Which Were 
Not Allowed To Influence the Simple and Conservative Design of MixMinion".

In other words, please disregard the above if you are actually thinking about 
our simple and conservative MixMinion design right now.  ;-)

As far as MixMinion goes, I think we should document the lack of recipient-
anonymity in the public-key encryption scheme.

Regards,

Zooko

[1] http://sf.net/projects/egtp
[2] http://mnet.sf.net/

---
                 zooko.com
Security and Distributed Systems Engineering
---