On Mon, 8 May 2000, Wei Dai wrote:
> On Sun, May 07, 2000 at 01:27:31PM -0400, dmolnar wrote:
> > 1) is the term "indeterministic cryptosystem" formally
> > defined anywhere?
>
> It sounds kind of like "probabilistic encryption" which is a standard
> term. Maybe they're the same thing?
That could be. This paper was aimed at a GSM/mobile telephone audience,
which perhaps wouldn't be expected to know about probabilistic encryption
or other definitions of security. Plus the only place the
"indeterministic" property is explicitly used in the paper is to prevent
an adversary from trial encrypting plaintexts and comparing them to
outputs from the mix. So it seems to me that any semantically secure
cryptosystem should provide that much, and then you would need
non-malleability under adaptive chosen ciphertext attack to prevent
other attacks.
[description of game for mix-nets]
> indistinguishability under adaptive chosen-ciphertext attack, which in
> turn is equivalent to non-malleability under adaptive chosen-ciphertext
> attack. See
> http://www.cs.ucdavis.edu/~rogaway/papers/relations-abstract.html for the
> proof.
Thanks, that seems right. I suppose one thing to note is that a mix node
is somewhat close to a decryption oracle in real life.
> > You might also want a cryptosystem to be
> > what I call "recipient-hiding" -- a ciphertext gives
> > up no information about to whom it has been encrypted.
>
> Can you elaborate on how "recipient-hiding" might help?
I was thinking in terms of communication schemes which use "public
bulletin boards," e.g. two people communicating anonymously by using
remailers to post encrypted mail to alt.anonymous.messages. Suppose we
have an adversary who wants to perform some kind of traffic analysis on
the public bulletin board, and happens to have a list of public keys for
everyone who might be posting.
If the cryptosystem is not "recipient-hiding", then the adversary can
determine which messages were encrypted with which public keys. He or she
may not be able to gain any information about the message, but now traffic
analysis seems easier. Perhaps another (more useful in practice?)
notion would be that the adversary can't even tell whether two messages
are encrypted with the same public key (whether or not he has that public
key).
Plain-vanilla RSA with no padding is not recipient hiding in this sense :
an adversary who guesses that a message is encrypted with public key PK,
and who guesses plaintext P can compute E(PK, P) and compare to the
ciphertext. OK, that's not such a big deal.
Maybe not as obvious is the fact that "recipient hiding" has nothing to
do with semantic security. Consider the cryptosystem C' formed by taking
a semantically secure cryptosystem C and augmenting the encryption
function to always append the public key used to the output. It seems
clear that all messages to the same public key are still
indistinguishable and so C' is semantically secure, but it's the very
oppostite of "recipient hiding." (I spent some time trying to prove that
semantic security --> recipient hiding before realizing this; maybe it's
obvious to everyone else)
David Hopwood has pointed out a more serious problem -- different RSA
public keys by nature have different public moduli. If you take a stream
of ciphertext and interpret it as being over the correct modulus, then it
should look random. If you interpret it as being over the "wrong" modulus,
then it won't, and you can distinguish. David has a modification to RSA
which minimizes this problem, but doesn't get rid of it in any nice
provable way.
David Wagner and (independently) Anna Lysyanskaya pointed out that a
semantically secure variant of Elgamal in which everyone uses the same
public modulus might be recipient-hiding. David posted some definitions
for this to sci.crypt a few weeks ago, which I plan to look at after
finals are done here. :-/ He also indicated that he's trying to extend
the Abdalla-Bellare-Rogaway DHAES scheme to be recipient hiding.
Anyway, recipient-hiding is most obviously useful when public bulletin
boards are involved. I'm not so sure it's useful between remailers, since
the underlying transport protocol will tend to reveal the ID of the next
hop anyway...but it strikes me as something to have as a hedge against
future clever attacks I can't think of.
Thanks,
-David Molnar
