Appears in M. Joye (Ed.): Topics in Cryptology – CT-RSA 2003,
Springer-Verlag LNCS 2612, pp. 244–262, ISBN 3-540-00847-0.

Provably Secure Public-Key Encryption
for Length-Preserving Chaumian Mixes
Bodo Möller
Technische Universität Darmstadt, Fachbereich Informatik
moeller@cdc.informatik.tu-darmstadt.de

Abstract. Mix chains as proposed by Chaum allow sending untraceable
electronic e-mail without requiring trust in a single authority: messages
are recursively public-key encrypted to multiple intermediates (mixes),
each of which forwards the message after removing one layer of encryption. To conceal as much information as possible when using variable (source routed) chains, all messages passed to mixes should be of
the same length; thus, message length should not decrease when a mix
transforms an input message into the corresponding output message directed at the next mix in the chain. Chaum described an implementation for such length-preserving mixes, but it is not secure against active
attacks. We show how to build practical cryptographically secure lengthpreserving mixes. The conventional definition of security against chosenciphertext attacks is not applicable to length-preserving mixes; we give
an appropriate definition and show that our construction achieves provable security.

1

Introduction

Chaum’s mix concept [6] is intended to allow users to send untraceable electronic e-mail without having to trust a single authority. The idea is to use anumber of intermediates such that it suffices for just one of these to be trustworthy in order to achieve untraceability. (The sender does not have to decide
which particular intermediate he is willing to trust, he just must be convincedthat at least one in a given list will behave as expected.) These intermediates,
the mixes, are remailers accepting public-key encrypted input. Messages must
be of a fixed size (shorter messages can be padded, longer messages can be
split into multiple parts). To send a message, it is routed through a chain ofmixes M1 , . . ., Mn : the sender obtains the public key of each mix; then he recursively encrypts the message (including the address of the final recipient) yielding EM1 EM2 (. . . EMn (payload ) . . .) where EMi denotes encryption with Mi ’s
public key, and sends the resulting ciphertext to mix M1 . (The public-key cryptosystem will typically be hybrid, i.e. involve use of symmetric-key cryptography
for bulk data encryption.) Each mix removes the corresponding layer of encryption and forwards the decrypted message to the next mix; thus mix Mn will
finally recover payload .
1Each mix is expected to collect a large batch of messages before forwarding
the decryption results. The messages in the batch must be reordered (mixed) toprevent message tracing. It is important to prevent replay attacks – a mix must
not process the same message twice, or active adversaries would be able to trace
messages by duplicating them at submission to cause multiple delivery. (Timestamps can be used to limit the timespan for which mixes have to remember
which messages they have already processed; see [6] and [7].)Usually it is desireable to allow source routing, i.e. let senders choose mix
chains on a per-message basis. This increases the flexibility of the whole scheme:
senders can make use of new mixes that go into operation, and they can avoid
mixes that appear not to work properly; in particular, they can avoid mixes thatsuppress messages (be it intentionally or because of technical problems), whichmight be noticed when sending probe messages to oneself over mix chains. For
source routing, in the recursively encrypted message, each layer must contain theaddress of the next mix in the chain so that each mix knows where to forward themessage. A problem with the straightforward implementation of source routing
is that messages will shrink as they proceed through the chain, not only becauseof the forwarding address for each layer that must be included, but also because
public-key encryption increases message sizes. For optimal untraceability, weneed length-preserving mixes: the messages that mixes receive should essentiallylook like the resulting messages that they forward to other mixes.
A construction of length-preserving mixes is given in [6] (a variant of thisis used in the fielded system Mixmaster [15]): mix messages consist of a fixed
number of slots of a fixed size. The first slot is public-key encrypted so that it
can be read by the first mix in the chain. Besides control information directed
at the respective mix (such as the address of the next mix in the chain or,in case of the last mix, the address of the final recipient), decryption yields
a symmetric key that the mix uses to decrypt all the other slots. Then slots
are shifted by one position: the decryption of the second slot becomes the new
first slot, and so on. A new final slot is added consisting of random (garbage)
data to obtain a mix message of the desired fixed length, which can the be
forwarded to the next mix. On the way through the chain, each mix message
consists of a number of slots with valid data followed by enough slots withgarbage to fill all available slots; mixes are oblivious of how many slots containvalid data and how many are random. Each mix in the chain, when decrypting
and shifting the slots, will “decrypt” the garbage slots already present and add
a new final slot, thus increasing the number of random slots by one. We notethat while the transformation of an incoming mix message to the corresponding
outgoing mix message is length-preserving, the decryption step itself is actuallylength-expanding because some of the data obtained by decryption is control
data directed at the current mix.
The problem with this method for obtaining a hybrid public-key cryptosystem with length-expanding decryption is that it is not secure against active
attacks: assume that an adversary controls at least one mix, and that all senders
submit well-formed messages. Now when the victim submits a message, the adversary can mark it by modifying one of the slots. This mark will persist as
2

the message is forwarded through the mix chain: assuming CBC or CFB mode
block cipher encryption, certain blocks of the corresponding slot will essentiallycontain garbage due to the decryption and slot shifting performed by each mix(whereas unmarked messages will not show such defects). If the final mix is controlled by the adversary, the adversary may be able to notice the modificationand thus break untraceability.
To rule out such attacks, the hybrid public-key cryptosystem should provide security against adaptive chosen ciphertext attacks (CCA security): thatis, it should be secure against an adversary who can request the decryption ofarbitrary ciphertexts.
In this paper, we present a secure and practical hybrid construction forlength-preserving mixes, which is also more flexible than the slot-based approach.
The structure of each layer of encryption resembles that of the public-key encryption scheme DHAES/DHIES ([1], [2]). The standard notion of CCA security
for public-key cryptosystems is not applicable to our hybrid public-key cryptosystem with length-expanding decryption because the encryption operationmust be defined differently for our application: encryption cannot be treated as
an atomic black-box operation that takes a plaintext and returns a ciphertext– in this model, we could not have length-expanding decryption. Rather, ourencryption process first is input part of the desired ciphertext and determinesa corresponding part of what will be the decryption result (it is this step thatprovides length expansion); then it is input the payload plaintext and finallyoutputs the complete ciphertext, which includes the portion requested in thefirst input.
We describe the hybrid construction in section 2. Section 3 discusses appropriate security notions and gives provable security results for the construction.
This paper shows essentially how Mixmaster ([15], [16]) should have been
specified to be cryptographically secure against active attacks. (Note that an
entirely different model of operation for mix networks is assumed by Ohkubo andAbe [17] and Jakobsson and Juels [11]: these constructions assume the existenceof a shared authenticated bulletin board, whereas in the present paper we areinterested in an open system that can be used with point-to-point communicationby e-mail or similar means.) We use many ideas and techniques described by
Cramer and Shoup in [8], but adapt them to fit the new notions of security
needed in the context of length-preserving mixes.
1.1 Notation
Strings are binary, i.e. elements of {0, 1}∗ . The concatenation of strings s and t
is denoted s || t. The length of string s is |s|. For |s| ≥ w, prefixw (s) denotes thestring consisting of the leftmost w bits of s; thus, prefix|s| (s || t) = s. Messages(plaintexts, ciphertexts) are strings.
Algorithms are usually probabilistic (randomized).

2

A Construction for Length-Preserving Mixes

Our construction allows much flexibility in the choice of cryptographic schemes,
even in a single chain. The single parameter that must be fixed for all mixes is3the desired mix message length `. Also it may be desireable to define a maximum
length for the actual message payload, i.e. the part of the plaintext as recoveredby the final mix that can be chosen by the sender: as a message proceeds throughthe mix chain, more and more of the data will be pseudo-random gibberish; thelength of the useful part of the final plaintext reveals that chains leaving lessthan this amount cannot have been used. The length n of the mix chain neednot be fixed.
For purposes of exposition, we number the mixes M1 , . . ., Mn according totheir position in the chain chosen by the sender (note that the same mix might
appear multiple times in one chain). For each mix Mi , the following must be
defined and, with the exception of the secret key SKMi , known to senders whowant to use the mix:
– A key encapsulation mechanism
KEMMi
and a key pair
(PKMi , SKMi )consisting of a public key PKMi and a secret key SKMi for this key encapsulation mechanism. A key encapsulation mechanism, similarly to a public-key
encryption mechanism, provides an algorithm
KEMMi .Encryptusing the public key and an algorithm
KEMMi .Decryptusing the secret key. Associated with KEMMi is a key generation algorithm
KEMMi .KeyGenthat returns appropriate key pairs (PK, SK). (Note that our formalization
uses no explicit security parameter, so desired key sizes are implicit to
KEMMi .KeyGen.) In contrast with public-key encryption, the Encrypt algorithm of a key encapsulation mechanism takes no input apart from the public
key: KEMMi .Encrypt(PKMi ) generates a ciphertext K of a fixed length
KEMMi .CipherLen
corresponding to a (pseudo-)random string K of a fixed length
KEMMi .OutLen
and outputs the pair (K, K). Evaluation of KEMMi .Decrypt(SKMi , K) will
return said string K if the key pair (PKMi , SKMi ) has been produced by
KEMMi .KeyGen. In this sense, ciphertext K encapsulates the random message K (which can be used as a key for symmetric-key cryptography). On
4

arbitrary inputs K, the computation KEMMi .Decrypt(SKMi , K) may either
return some string K or fail (return the special value invalid).
One example of a key encapsulation mechanism is the Diffie-Hellman key
exchange [9] with static keys for one party and ephemeral keys for the otherparty where the concatenation of the ephemeral public key with the common
secret group element is hashed to obtain K (cf. [1], [19]); KEMMi .CipherLen
can be kept particularly small for elliptic curve Diffie-Hellman using just x coordinates of points (see [14]). Specifications for various key encapsulation
mechanisms can be found in [19].
– A one-time message authentication code
MACMi
with key length
MACMi .KeyLen
and output length
MACMi .OutLen.
A one-time message authentication code specifies an efficient deterministic algorithm that takes as input a key K of length MACMi .KeyLen anda bit string s and returns a string MACMi (K, s) of length MACMi .OutLen.
In our construction, MACMi will only be used for strings s of fixed length` − KEMMi .CipherLen − MACMi .OutLen.
Candidate one-time message authentication codes are UHASH [12]1 and
HMAC [3].
– A pseudo-random bit string generator
STREAMMitaking as input a key K of length
STREAMMi .KeyLen
and deterministically generating an output string STREAMMi (K) of length
STREAMMi .OutLen.
This will be used for an XOR-based stream cipher. A convenient example
implementation is the so-called counter mode of a block cipher (the output
sequence is the prefix of appropriate length of EK (0) || EK (1) || EK (2) || . . .
where EK denotes block cipher encryption using key K; see [4] and [13]).
1

UHASH is the combination of a key derivation function with an almost strongly
universal hash function [20] and is the core of UMAC as specified in [12]. Note thatthe security arguments provided for the earlier version of UMAC described in [5] arebased on a different approach.

5

– An integer
PlainLenMi
specifying the length of the prefix of each decrypted message that is considered control data directed to mix MMi and will not be forwarded. (This is
the amount of message expansion: the decrypted message minus the prefixmust be of size ` because that is what will be sent to the next mix.)
The parameters must fulfil the following conditions:
KEMMi .CipherLen + MACMi .OutLen + PlainLenMi < `KEMMi .OutLen = STREAMMi .KeyLen + MACMi .KeyLen
STREAMMi .OutLen = PlainLenMi + `
2.1

(1)
(2)
(3)

Encryption

We now describe encryption for sending a message through a chain M1 , . . ., Mn .
Let payload be the message of lengthX|payload | = ` −(KEMMi .CipherLen + MACMi .OutLen + PlainLenMi ) (4)1≤i≤n(messages shorter than this maximum should be randomly padded on the right).
For each i, let plain i be the control message of length PlainLenMi directed to therespective mix. The encryption algorithm for these arguments is denoted
chain encrypt M1 ,...,Mn (plain 1 , . . ., plain n ; payload )orchain encrypt M1 ,...,Mn (plain 1 , . . ., plain n ; payload ; λ)where λ is the empty string. The algorithm is defined recursively. Let 1 ≤ i ≤ n,
and let Ci be a string of length
X|Ci | =
(KEMMk .CipherLen + MACMk .OutLen + PlainLenMk )
(5)
1≤k<i

(thus specifically |C1 | = 0). Then algorithm
chain encrypt Mi ,...,Mn (plain i , . . ., plain n ; payload ; Ci )works as follows:
1. Use KEMMi .Encrypt(PKMi ) to generate a pair (Ki , Ki ).
2. Split Ki in the form
Ki = Ki,MAC || Ki,STREAM
such that |Ki,MAC | = MACMi .KeyLen (so |Ki,STREAM | = STREAMMi .KeyLenby (2)).
6

3. Compute STREAMMi (Ki,STREAM ) and split this string in the form
stream i,L || stream i,Rsuch that the left part stream i,L is of length` − |Ci | − KEMMi .CipherLen − MACMi .OutLen.
4. If i = n (last mix), then by (4) and (5) it follows that |stream n,L | =PlainLenn + |payload |. In this case, setCn = stream n,L ⊕ (plain n || payload ) || Cn .
Otherwise, let
Ci+1 = stream i,R ⊕ (Ci || 0KEMMi .CipherLen+MACMi .OutLen+PlainLenMi ),by recursion computexi = chain encrypt Mi+1 ,...,Mn (plain i+1 , . . ., plain n ; payload ; Ci+1 ),and letCi = stream i,L ⊕ (plain i || prefix|stream i,L |−PlainLenM (xi )) || Ci .
i

5. Compute Mi = MACi (Ki,MAC , Ci ).
6. Return the ciphertext Ki || Mi || Ci , which is of length `.
Appendix A.1 illustrates a ciphertext generated by chain encrypt M1 ,...,Mn .
2.2

Decryption

The decryption algorithm for mix Mi (1 ≤ i ≤ n) works as follows, given
a length-` ciphertext K || M || C (split into its three components according toparameters KEMMi .CipherLen = |K| and MACMi .OutLen = |M|). We denote it
mix decrypt Mi (K || M || C).
Remember that Mi in general is not aware of the mix chain used by the senderor even of its own position i in the chain.
1. Compute K = KEMMi .Decrypt(SKMi , K). If this computation fails, abortwith an error (return invalid).
2. Split K in the form
K = KMAC || KSTREAM
such that |KMAC | = MACMi .KeyLen.
7

3. Computef = MACM (KMAC , C)Miand test whether

f = M.
M

If this is not the case, abort with an error (return invalid).
4. Compute the string
stream = STREAMMi (KSTREAM )of length STREAMMi .OutLen.
5. Computestream ⊕ (C || 0KEMMi .CipherLen+MACMi .OutLen+PlainLenMi )and split the resulting string in the form
plain i || P
where plain i is of length PlainLenMi (and thus, by (3), P is of length `).
6. Return the pair (plain i , P ).
If this algorithm finishes without an error, plain i is a control message directedto the current mix, and P is the message to be forwarded to another mix or to
the final recipient (as requested by the control message).
It is straightforward to verify that for ciphertexts computed as
chain encrypt M1 ,...,Mn (plain 1 , . . ., plain n ; payload ),iterative decryption by mixes M1 , . . ., Mn will indeed work without an error andrecover the respective strings plain i and finally also the message payload concatenated with some (useless) extra data. Appendix A.2 illustrates decryption.

3

Provable Security

The mix concept is intended to provide security when at least one mix can betrusted and behaves correctly. (However note that denial-of-service attacks byincorrectly operating mixes cannot be ruled out; the only option is to avoid mixes
that appear to malfunction.) Thus we assume that some single mix Mi works as
expected while all other mixes are controlled by the adversary and may not follow
the protocol (also the cryptographic schemes KEMMj , MACMj , and STREAMMj
associated with mixes Mj , j 6= i, might be not secure, and KEMMj might evennot be a valid key encapsulation mechanism according to the description given
in section 2).
This leaves only Mi to be attacked: outer layers of encryption for mixes thatappear before Mi in a mix chain are easily removed by the adversary and thus
8are not relevant for security; and inner layers of encryption for mixes that appear
after Mi in a mix chain are involved in the encryption process
chain encrypt Mi ,...,Mn (plain i , . . ., plain n ; payload ; Ci )described in section 2.1, but cannot provide protection against the adversary.
An important security property for mixes is unlinkability: an adversary who
observes a batch of encrypted messages as these are sent to a mix and who sees
the resulting decrypted messages when these are forwarded should not be able
to tell better than by chance which decrypted messages correspond to whichencrypted messages.
Beyond this basic security notion, we also want to achieve security against
active attacks. As noted in the introduction, it is crucial to detect message replay
and ignore replayed message. However, this does not rule out active attacks basedon message modifications. To show that our construction for length-preserving
mixes is secure against this kind of attacks, we will model an active adversary
who is able to launch an adaptive chosen ciphertext attack (CCA).
We point out that in the model of operation that we assume, unlinkability
cannot be fully guaranteed in the presence of active attacks: an active adversary
who suppresses all but a single one of the legitimate encrypted messages in abatch and substitutes new messages for them can easily trace the remaining
legitimate message. This can be avoided only heuristically (each sender of mix
messages should occasionally route a message to himself to see if it gets through).
To avoid related flooding attacks, mixes should not start a new batch whenevera certain fixed number of messages has arrived; instead, each batch should be
kept open for additional messages during some time frame.
We show how the security of the mix construction can be captured formallyby describing unlinkability (section 3.1) and CCA security (section 3.2). We
then provide security definitions for the underlying key encapsulation method(section 3.3), one-time message authentication code (section 3.4), and pseudorandom bit string generator (section 3.5). Finally, section 3.6 present security
results that relates the security of the mix encryption scheme to the security ofthese cryptographic schemes: we will see that if the mix encryption scheme is
not secure, then this is because one of the underlying cryptographic schemes is
not secure.
3.1

Unlinkability of the Mix Encryption Scheme

An intuitive approach to defining unlinkability is as follows: the adversary sees abatch of m ciphertexts and a random permutation of the resulting m decryption
results; for each decryption result, the adversary makes a guess on the index
of the corresponding ciphertext. With random guessing, the expected numberof correct guesses is one. An adversary who can do better than this breaks
unlinkability.
More specifically, we let the adversary select the plaintexts as far as possible(remember that as we have length-expanding decryption, it is not possible to9choose all of the decryption result arbitrarily when generating a ciphertext). In
the formal definition, we confine to a setting with two plaintexts where only one
ciphertext is shown to the adversary (an adversary in the unrestricted setting canbe used to build an adversary in this setting). This is captured in the following
attack game:
1. The adversary queries a key generation oracle, which uses KEMMi .KeyGen tocompute a key pair
(PK, SK)and responds with PK (and secretly stores SK).
2. The adversary uses an encryption oracle as follows (cf. the encryption algorithm from section 2.1 in the case of a length-1 mix chain, i.e. with norecursion and |Ci | = 0):– The adversary submits a pair of string pairs(plain i,0 , m0 ), (plain i,1 , m1 )where|plain i,b | = PlainLenMi
and|mb | = ` − KEMMi .CipherLen − MACMi .OutLen − PlainLenMi
for b = 0, 1.
– The encryption oracle chooses a bit b ∈ {0, 1} uniformly at random.
Then it uses KEMMi .Encrypt(PK) to generate a pair (Koracle , Koracle ) andsplits Koracle in the form
Koracle = KMAC || KSTREAM
such that |KMAC | = MACMi .KeyLen; it computes STREAMMi (KSTREAM )and splits the resulting string stream in the form
stream = stream L || stream R
such that |stream L | = ` − KEMMi .CipherLen − MACMi .OutLen; and it
computes
C = stream L ⊕ (plain i,b || mb )andM = MACMi (KMAC , C).
Then it outputs the pair
(Koracle || M || C, stream R ).
3. The adversary outputs a bit eb ∈ {0, 1}.
10

The bit eb output by the adversary is its guess for the value of b. Note that thedecryption result corresponding to the ciphertext Koracle || M || C is(plain i,b , mb || stream R )(see section 2.2), and all of this except for the choice of the bit b is known to theadversary.
Let A be any adversary (interactive probabilistic algorithm with boundedruntime) in this attack game. Its advantage against unlinkability for Mi ’s instantiation of the mix encryption scheme isAdvLinkMi ,A = Pr eb = 1 | b = 1 − Pr eb = 1 | b = 0 .
3.2

CCA Security of the Mix Encryption SchemeDue to the recursive nature of our encryption algorithm for mix chains, we cannot
directly apply the usual definitions of security under adaptive chosen ciphertext
attack (CCA) for ordinary public-key encryption. We adapt the attack gamedescribed in [8, section 3.2] (which goes back to [10] and [18]) as follows to take
into account the special properties of our construction:
1. The adversary queries a key generation oracle, which uses KEMMi .KeyGen tocompute a key pair
(PK, SK)and responds with PK (and secretly stores SK).
2. The adversary makes a sequence of queries to a decryption oracle. Each queryis an arbitrary string s of length `, and the oracle responds with
mix decrypt Mi (s),using the secret key SK from step 1. That is, each oracle response is eithera pair (plain, P ) where |plain| = PlainLenMi and |P | = `, or the special
value invalid.
3. The adversary uses an interactive encryption oracle as follows (compare withthe encryption algorithm in section 2.1):– First the adversary submits some string Ci subject only to the conditionthat
0 ≤ |Ci | < ` − KEMMi .CipherLen − MACMi .OutLen.
– The interactive encryption oracle uses KEMMi .Encrypt(PK) to generatea pair (Koracle , Koracle ) and splits Koracle in the form
Koracle = KMAC || KSTREAM
such that |KMAC | = MACMi .KeyLen; it computes STREAMMi (KSTREAM )and splits the resulting string stream in the form
stream = stream L || stream R
11such that |stream L | = ` − |Ci | − KEMMi .CipherLen − MACMi .OutLen; andit computes
Ci+1 = stream R ⊕ (Ci || 0KEMMi .CipherLen+MACMi .OutLen+PlainLenMi )and sends Ci+1 to the adversary.
– The adversary submits a pair of string pairs(plain i,0 , m0 ), (plain i,1 , m1 )satisfying|plain i,b | = PlainLenMi
and|mb | = ` − |Ci | − KEMMi .CipherLen − MACMi .OutLen − PlainLenMi
for b = 0, 1.
– The interactive encryption oracle chooses a uniformly random bit b ∈{0, 1}, determinesC = stream L ⊕ (plain i,b || mb ) || Ciand
M = MACMi (KMAC , C),
and responds with the challenge ciphertext
Koracle || M || C.
4. The adversary again makes a sequence of queries to a decryption oracle as
in step 2, except that this time the decryption oracle refuses being asked forthe challenge ciphertext Koracle || M || C from step 3 (it returns invalid for thiscase).
5. The adversary outputs a bit eb ∈ {0, 1}.

The bit eb output by the adversary is its guess for the value of b.
The essential difference to the adaptive chosen ciphertext attack game forordinary public-key encryption is that we have made the encryption oracle interactive to reflect the recursiveness of the encryption algorithm for mix chains,
where encryption to mixes later in the chain than Mi can have potentially arbitrary effects on a large part of the plaintext. Appendix A.3 illustrates the
ciphertext resulting from the invocation of the interactive encryption oracle.
Let A be any adversary (interactive probabilistic algorithm with boundedruntime) in the above attack game. Its CCA advantage against Mi ’s instantiationof the mix encryption scheme isAdvCCAMi ,A = Pr eb = 1 | b = 1 − Pr eb = 1 | b = 0 .
12

3.3

Security of the Key Encapsulation Mechanism

CCA security for the key encryption mechanism KEMMi is defined through thefollowing attack game (cf. [8, section 7.1.2]):
1. The adversary queries a key generation oracle, which uses KEMMi .KeyGen tocompute a key pair (PK, SK) and responds with PK (and secretly stores SK).
2. The adversary makes a sequence of queries to a decryption oracle. Each queryis an arbitrary string s of length KEMMi .CipherLen; the oracle responds with
KEMMi .Decrypt(SK, s).
Thus each oracle response is either a string of length KEMMi .OutLen or the
special value invalid.
3. The adversary queries an encryption oracle, which works as follows: it uses
KEMMi .Encrypt(PK) to obtain a pair (K0 , Koracle ), it generates a uniformly
randomly string K1 such that |K0 | = |K1 |, chooses a uniformly random bit
bKEM ∈ {0, 1}, and responds with (KbKEM , Koracle ).
4. The adversary again makes a sequence of queries to a decryption oracle as instep 2, but this time the oracle refuses the specific query Koracle and responds
invalid in this case.
5. The adversary outputs a bit ebKEM ∈ {0, 1}.
The CCA advantage of an adversary A (an interactive probabilistic algorithmwith bounded runtime) against KEMMi in this attack game isAdvCCAKEMMi ,A = Pr ebKEM = 1 | bKEM = 1 − Pr ebKEM = 1 | bKEM = 0 .
3.4

Security of the One-Time Message Authentication CodeTo define the security of MACMi , we use the following attack game (cf. [8, section 7.2.2]:
1. The adversary submits a string s (which for our purposes may be assumed
to be of fixed length ` − KEMMi .CipherLen − MACMi .OutLen) to an oracle.
The oracle generates a uniformly random string K of length MACMi .KeyLen
and responds with MACMi (K, s).
2. The adversary outputs a list (s1 , t1 ), (s2 , t2 ), . . ., (sm , tm ) of pairs of strings.
An adversary A again is an interactive probabilistic algorithm with boundedruntime; the runtime bound implies a bound on the list length m. We say thatadversary A has produced a forgery if sk 6= s and MACMi (K, sk ) = tk for some k(1 ≤ k ≤ m). Its advantage against MACMi , denoted AdvForgeMACM ,A , is theiprobability that it produces a forgery in the above game.
13

3.5

Security of the Pseudo-Random Bit String Generator

To define the security of STREAMMi , we use the following attack game:
1. The adversary queries an oracle. The oracle generates a uniformly random
string K of length STREAMMi .KeyLen, computes stream 0 = STREAMMi (K),generates a uniformly random string stream 1 with |stream 0 | = |stream 1 |,chooses a uniformly random bit bSTREAM ∈ {0, 1}, and responds with stream b .
2. The adversary outputs a bit ebSTREAM ∈ {0, 1}.

The advantage of an adversary A (again an interactive probabilistic algorithmwith bounded runtime) against STREAMMi is
AdvSTREAMMi ,A= Pr ebSTREAM = 1 | bSTREAM = 1 − Pr ebSTREAM = 1 | bSTREAM = 0 .
3.6

Security Results

First let A be an adversary against the unlinkability of the mix encryption
scheme, attacking a mix Mi as described in section 3.1. It can be shown that
there are adversaries A1 and A2 against KEMMi and STREAMMi , respectively,
with essentially the same runtime as A such that
AdvLinkMi ,A ≤ 2 · AdvCCAKEMMi ,A1 + AdvSTREAMMi ,A2 .
Details of the proof can be found in appendix B.1.
Now let A be an adversary against the CCA security of the mix encryption
scheme, attacking a mix Mi as described in section 3.2. It can be shown that
there are adversaries A1 , A2 , A3 against KEMMi , MACMi , STREAMMi all having
essentially the same runtime as A such that
AdvCCAMi ,A ≤ 2 · AdvCCAKEMMi ,A1 + AdvForgeMACM ,A2 + AdvSTREAMMi ,A3 .
i

Details of the proof are given in appendix B.2.

Acknowledgement
David Hopwood and the anonymous reviewers provided valuable comments on
earlier versions of this paper.

14

References
1. Abdalla, M., Bellare, M., and Rogaway, P. DHAES: An encryption
scheme based on the Diffie-Hellman problem. Submission to IEEE P1363a.
http://grouper.ieee.org/groups/1363/P1363a/Encryption.html, 1998.
2. Abdalla, M., Bellare, M., and Rogaway, P. The oracle Diffie-Hellman assumptions and an analysis of DHIES. In Progress in Cryptology - CT-RSA 2001
(2001), D. Naccache, Ed., vol. 2020 of Lecture Notes in Computer Science, pp. 143–
158.
3. Bellare, M., Canetti, R., and Krawczyk, H. Keying hash functions formessage authentication. In Advances in Cryptology – CRYPTO ’96 (1996),
N. Koblitz, Ed., vol. 1109 of Lecture Notes in Computer Science, pp. 1–15.
4. Bellare, M., Desai, A., Jokipii, E., and Rogaway, P. A concrete security
treatment of symmetric encryption. In 38th Annual Symposium on Foundationsof Computer Science (FOCS ’97) (1997), IEEE Computer Society, pp. 394–403.
5. Black, J., Halevi, S., Krawczyk, H., Krovetz, T., and Rogaway, P.
UMAC: Fast and secure message authentication. In Advances in Cryptology –CRYPTO ’99 (1999), M. Wiener, Ed., vol. 1666 of Lecture Notes in Computer
Science, pp. 216–233.
6. Chaum, D.
Untraceable electronic mail, return addresses, and digital
pseudonyms. Communications of the ACM 24 (1981), 84–88.
7. Cottrell, L. Mixmaster & remailer attacks.
http://www.obscura.com/%7Eloki/remailer/remailer-essay.html, 1997.
8. Cramer, R., and Shoup, V. Design and analysis of practical public-key encryption schemes secure against adaptive chosen ciphertext attack. Manuscript,
http://shoup.net/papers/, 2001.
9. Diffie, W., and Hellman, M. E. New directions in cryptography. IEEE Transactions on Information Theory 22, 6 (1976), 644–654.
10. Goldwasser, S., and Micali, S. Probabilistic encryption. Journal of Computerand System Sciences 28 (1984), 270–299.
11. Jakobsson, M., and Juels, A. An optimally robust hybrid mix network. In
20th Annual ACM Symposium on Principles of Distributed Computing (PODC2001) (2001), ACM Press, pp. 284–292.
12. Krovetz, T., Black, J., Halevi, S., Hevia, A., Krawczyk, H., andRogaway, P.
UMAC: Message authentication code using universal hashing. Internet-Draft draft-krovetz-umac-01.txt, http://www.cs.ucdavis.edu/~rogaway/umac/, 2000.
13. Lipmaa, H., Rogaway, P., and Wagner, D. Comments to NIST concerning AES modes of operation: CTR-mode encryption. http://csrc.nist.gov/
encryption/modes/workshop1/papers/lipmaa-ctr.pdf, 2000.
14. Miller, V. S. Use of elliptic curves in cryptography. In Advances in Cryptology –CRYPTO ’85 (1986), H. C. Williams, Ed., vol. 218 of Lecture Notes in Computer
Science, pp. 417–428.
15. Mixmaster anonymous remailer software. http://sourceforge.net/projects/
mixmaster/.
16. Möller, U., and Cottrell, L. Mixmaster protocol version 2.
http://www.eskimo.com/~rowdenw/crypt/Mix/draft-moeller-v2-01.txt,
2000.
17. Ohkubo, M., and Abe, M. A length-invariant hybrid mix. In Advances in
Cryptology – ASIACRYPT 2000 (2000), T. Okamoto, Ed., vol. 1976 of Lecture
Notes in Computer Science, pp. 178–191.

15

18. Rackoff, C. W., and Simon, D. R. Non-interactive zero-knowledge proof ofknowledge and chosen ciphertext attack. In Advances in Cryptology – CRYPTO’91 (1992), J. Feigenbaum, Ed., vol. 576 of Lecture Notes in Computer Science,
pp. 433–444.
19. Shoup, V. A proposal for an ISO standard for public key encryption. Version
2.1, December 20, 2001. http://shoup.net/papers/.
20. Wegman, M. N., and Carter, J. L. New hash functions and their use in authentication and set equality. Journal of Computer and System Sciences 22 (1981),
265–279.

A

Illustrations

A.1

Encryption

We depict a ciphertext generated by the encryption algorithm
chain encrypt M1 ,M2 ,M3 (plain 1 , plain 2 , plain 3 ; payload )as described in section 2.1. In the illustration, we have concatenation horizontallyand XOR vertically (i.e. boxes in the same row represent bit strings that areconcatenated, and the ciphertext is the XOR of the multiple rows shown).
plain 3 payload
stream 3,L
M3
stream 2,Lplain 2 K3plain 1 K2
K1

A.2

M2
stream 1,L

M1

Decryption

The result obtained by mix M1 when applying the decryption algorithm fromsection 2.2 to the ciphertext from appendix A.1 is composed as follows:
plain 2 K3plain 1

K2

M2

plain 3 payload
stream 3,L
M3
stream 2,Lstream 1,R

The string plain 1 is directed to M1 . The remainder of the decryption result isa ciphertext that should be forwarded to the next mix in the chain, M2 , which
will then obtain the following result:plain 2

K3

plain 3 payload
stream 3,L
M3
stream 2,R
stream 1,R

16

Similarly, mix M3 will obtain the following final decryption result:plain 3

payloadstream 3,R
stream 2,R
stream 1,R

A.3

Interactive Encryption Oracle

In the adaptive chosen ciphertext attack game from section 3.2, recursive encryption is replaced by an interactive encryption oracle to generate the challenge
ciphertext, which has the following structure:mb
stream L

plaini,b
Koracle M

Ci

Applying algorithm mix decrypt Mi from section 2.2 to this ciphertext would
yield the following result:plain i,bmb

Ci
stream R

This can also be written as follows:
plain i,bmb

B

Security Proofs

B.1

Unlinkability

Ci+1

We prove the security result from section 3.6 for the unlinkability of the mix
encryption scheme. Let G0 denote the attack game from section 3.1. Let G1 be
like G0 except that a uniformly random string is used for Koracle , whereas Koracle
is still generated by KEMMi .Encrypt(PK). Let G2 be like G1 except that theencryption oracle uses a uniformly random string stream instead of computing
STREAMMi (KSTREAM ).
Now we consider an adversary A as in section 3.1, exposed to these different attack gamesGx , 0 ≤ x ≤ 2, and look at the respective success probabilities Pr Gx eb = b . Based on A, adversaries A1 and A2 against KEMMi and
STREAMMi , respectively, will be built, each with essentially the same runtime
as A.
A1 attacks KEMMi as follows (cf. section 3.3; note that this A1 never actuallyuses its decryption oracle). At first, it generates b ∈ {0, 1} uniformly at random.
Then, it runs the adversary A; when A queries its encryption oracle, A1 queries
its own encryption oracle to obtain a pair (Koracle , Koracle ) and performs step 2
17

from section 3.1 using this pair and the pregenerated bit b. Finally, when A
outputs its bit eb, A1 outputs 1 if eb = b and 0 otherwise. Observe that

Pr G1 eb = b − Pr G0 eb = b = AdvCCAKEMMi ,A1(G0 corresponds to bKEM = 0, G1 corresponds to bKEM = 1 in section 3.3).
A2 attacks STREAMMi as follows (cf. section 3.5). First, it generates b ∈{0, 1} and a string Koracle of length KEMMi .OutLen uniformly at random. Then,it runs the adversary A, playing the role of the key generation oracle and the roleof the encryption oracle, wherein it substitutes the pregenerated string Koracle
and the pregenerated bit b in step 2 of section 3.1. When A outputs its bit eb, A2
outputs 1 if eb = b and 0 otherwise. Observe that

Pr G2 eb = b − Pr G1 eb = b = AdvSTREAMMi ,A2(G1 corresponds to bSTREAM = 0, G2 corresponds to bSTREAM = 1 in section 3.5).
Finally observe that Pr G2 eb = b = 12 .
From this we obtain the inequality1− Pr G0 eb = b
2
X 




=2·
Pr Gx eb = b − Pr Gx−1 eb = b

AdvLinkMi ,A = 2 ·

1≤x≤2


≤ 2 · AdvCCAKEMMi ,A1 + AdvSTREAMMi ,A2 ,which concludes the proof.
B.2

CCA Security

We prove the CCA security result given in section 3.6. Let G0 denote the attack
game from section 3.2. We will modify it in multiple steps, essentially disabling
the underlying cryptographic schemes (key encryption method, one-time message
authentication code, and pseudo-random bit string generator) one after another.
G1 is like G0 except that a uniformly random string is used for Koracle ,whereas Koracle is still generated by KEMMi .Encrypt(PK). In the decryption oracle, K is substituted whenever KEMMi .Decrypt(SK, Koracle ) would have to becomputed.
G2 is like G1 except that the decryption oracle always responds with invalid
when faced with any query prefixed with string Koracle . (This applies to bothstep 2 and step 4 in section 3.2. Thus, the invocation of KEMMi .Encrypt(PK) togenerate (Koracle , Koracle ) must be advanced from step 3 to an earlier step; in G1 ,this is only a descriptive change and does not affect the behaviour observed by
the adversary.)
G3 is like G2 except that the interactive encryption oracle uses a uniformly
random string stream instead of computing STREAMMi (KSTREAM ).
18

Now we consider an adversary A as in section 3.2, exposed to these different
attack games Gx , 0 ≤ x ≤ 3, and look at the respective success probabilities
Pr Gx eb = b . Based on A, adversaries A1 , A2 , A3 against KEMMi , MACMi ,STREAMMi will be built all having essentially the same runtime as A.
A1 attacks KEMMi as follows (cf. section 3.3). At first, it generates b ∈{0, 1} uniformly at random. Then, it runs the adversary A; when A queries its
decryption oracle, A1 uses its own decryption oracle to perform the decryption
algorithm from section 2.2, and when A queries its interactive encryption oracle,
A1 queries its own encryption oracle to obtain a pair (Koracle , Koracle ) and performs
step 3 from section 3.2 using this pair and the pregenerated bit b. Finally, when A
outputs its bit eb, A1 outputs 1 if eb = b and 0 otherwise. Observe that

Pr G1 eb = b − Pr G0 eb = b = AdvCCAKEMMi ,A1(G0 corresponds to bKEM = 0, G1 corresponds to bKEM = 1 in section 3.3).
A2 attacks MACMi as follows (cf. section 3.4). At first, it generates b ∈ {0, 1}
and a string Koracle of length KEMMi .OutLen uniformly at random. Then, it runs
the adversary A, playing the roles of the key generation oracle, decryption oracle,
and interactive encryption oracle, substituting the pregenerated string Koracle
and the pregenerated bit b in step 3 of section 3.2. Whenever A submits a query
K || M || C to the decryption oracle, A2 adds the pair (C, M) to its own output(A’s final output bit eb is ignored). Observe that

Pr G2 eb = b − Pr G1 eb = b ≤ AdvForgeMACM ,A2i(G2 behaves differently from G1 only if a forgery has been produced).
A3 attacks STREAMMi as follows (cf. section 3.5). First, it generates b ∈{0, 1} and a string Koracle of length KEMMi .OutLen uniformly at random. Then,it runs the adversary A, playing the roles of the key generation oracle, decryption oracle, and interactive encryption oracle, substituting the pregenerated
string Koracle and the pregenerated bit b in step 3 of section 3.2. When A outputs
its bit eb, A3 outputs 1 if eb = b and 0 otherwise. Observe that
Pr G3 eb = b − Pr G2 eb = b = AdvSTREAMMi ,A3(G2 corresponds to bSTREAM = 0, G3 corresponds to bSTREAM = 1 in section 3.5).
Finally observe that Pr G3 eb = b = 12 .
From this we obtain the inequality1− Pr G0 eb = b
2
X 




=2·
Pr Gx eb = b − Pr Gx−1 eb = b

AdvCCAMi ,A = 2 ·

1≤x≤3


≤ 2 · AdvCCAKEMMi ,A1 + AdvForgeMACM ,A2 + AdvSTREAMMi ,A3 ,iwhich concludes the proof.
19