Re: MixMinion Status

[George Danezis <gd@theory.lcs.mit.edu>]

Roger,

This is a very good point and is discussed in:

Key-Privacy in Public-Key Encryption
Mihir Bellare, Alexandra Boldyreva, Anand Desai, and David 
Pointcheval
LNCS 2248, p. 566 ff. 

http://link.springer.de/link/service/series/0558/papers/2248/22480566.pdf

Definitely something to keep in mind. 

George

On Fri, 15 Mar 2002, Roger Dingledine wrote:

> (David and Nick: I've changed the address from which you're subscribed.)
> 
> On Fri, Mar 15, 2002 at 09:10:32AM -0500, George Danezis wrote:
> > I am in the process of rewritting the core of the design document to 
> > reflect what we discussed last Saturday. 
> 
> This is probably something to deal with down the road, but I wanted to
> mention it now so I don't forget and so we can be keeping it in mind.
> 
> Two quotes from page 69 of http://freehaven.net/doc/freehaven10.ps :
> 
> |We call a public key cryptosystem \emph{recipient-hiding} if it is
> |infeasible to determine, given a ciphertext, the public key used to create
> |that ciphertext. The recipient-hiding property is \emph{not} implied
> |by the standard definition of semantic security (even with respect to
> |adaptive chosen ciphertext attack). Moreover, it is not even achieved
> |in common practical constructions. This has implications for mixnets
> |which use reply blocks that are separate from the body of the message.
> 
> |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.
> 
> On the other hand, most actual systems generate a symmetric key, encrypt
> that with RSA, and then crypt the text with the symmetric key. Does that
> solve our problem?
> 
> > Roger: Feel free to hack the introduction, I am not going to work on it 
> > until later.
> 
> Ok. I'll put it on my plate.
> 
> --Roger
>