Hi,
I came across the term "indeterministic cryptosystem" while
reading the paper "MIXes in Mobile Communications Systems : Location
Management with Privacy" by Federrath, Jerichow, and A. Pfitzmann.
http://www.semper.org/sirene/lit/abstr96.html#FeJP1_96
An "indeterministic cryptosystem" is defined there as one in which "equal
plaintext blocks are encrypted to different ciphertext blocks."
I didn't see a formal definition of the term in this paper, but they use
the property to prevent the attack where an adversary encrypts known
plaintext with a public key and compares it to outgoing messages. I think
they may also mean such a cryptosystem prevents the marking attacks
detailed in "How to Break the Direct-RSA Implementation of MIXes" by B.
Pfitzmann and A. Pfitzmann
http://www.semper.org/sirene/lit/abstr90.html#PfPf_90
Anyway :
1) is the term "indeterministic cryptosystem" formally
defined anywhere?
2) has anyone followed up on "How to Break..." with a
characterization of what properties of a cryptosystem
are desirable for a mix-net? Off the top of my head,
the notion of "non-malleability" seems sufficient to
prevent the attacks mentioned in that paper.
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.
I am looking through the SIRENE collection of papers now, but I'm slightly
handicapped by the fact I don't know German. :-\ Any pointers appreciated.
Thanks much,
-David Molnar
