Fig. 1. Pseudo-code for AES encryption

B List of Tables

We summarise in Table 2 the list of randomised tables required for each opera-

tion. Note that for decryption, we also need table S to compute the key-schedule,

Table 2. Randomised tables required for each AES operation, for the basic permutation

table countermeasure, and with the three time-memory tradeo¬s

Operation Tables required

P , P ’1 , XT1 , XT2 , S , ML, MH

AES encryption, basic 4 4

P , P , XT4 , XT2 , S ’1 , ML, MH,RL, RH,TL, TH

’1 1

AES decryption, basic 4

tradeo¬s P , P ’1 , XT1 , ML, MH, p12 , p21 , P , P ’1 , T

AES encryption, 4

tradeo¬s P , P ’1 , XT1 , ML, MH, p12 , p21 , P , P ’1 , T

AES decryption, 4

292 J.-S. Coron

but this table can be discarded at the end of the key-schedule. The RAM re-

quirement for those randomised tables is summarised in Table 3.

InvCipher(byte in[16], byte out[16], word w[44])

begin

byte state[16]

state=in

AddRoundKey(state,w[40,43])

for round=9 downto 1

InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state,w[round*4,(round+1)*4-1])

InvMixColumns(state)

end for

InvShiftRows(state)

InvSubBytes(state)

AddRoundKey(state,w[0,3])

end

Fig. 2. Pseudo-code for AES decryption

Table 3. Memory requirement for the randomised tables

Operation RAM (bytes)

’1

Permutations P and P 32

1

Xor-table XT4 128

2

Xor-table XT4 128

Randomised SBOX S 256

Randomised SBOX S ’1 256

Tables ML, MH 32

Tables TL, TH, RL, RH 64

Permutations p12 and p21 16

’1

Permutations P and P 32

Table T 128

Simpli¬ed Submission of Inputs to Protocols

Douglas Wikstr¨m

o

CSC KTH Stockholm, Sweden

dog@csc.kth.se

Abstract. Consider an electronic election scheme implemented using a

mix-net; a large number of voters submit their votes and then a smaller

number of servers compute the result. The mix-net accepts an encrypted

vote from each voter and outputs the set of votes in sorted order without

revealing the permutation used. To ensure a fair election, the votes of

corrupt voters should be independent of the votes of honest voters, i.e.,

some type of non-malleability or plaintext awareness is needed. How-

ever, for e¬ciency reasons the servers typically expect inputs from some

homomorphic cryptosystem, which is inherently malleable.

In this paper we consider the problem of how non-malleability can be

guaranteed in the submission phase and still allow the servers to start

their computation with ciphertexts of the homomorphic cryptosystem.

This can clearly be achieved using general techniques, but we would like

a solution which is: (i) provably secure under standard assumptions, (ii)

non-interactive for submittors (iii) very e¬cient for all parties in terms

of computation and communication.

We give the ¬rst solution to this problem which has all these prop-

erties. Our solution is surprisingly simple and can be based on various

Cramer-Shoup cryptosystems. To capture its security properties we in-

troduce a variation of CCA2-security.

1 Introduction

Mix-Nets. A mix-net is a cryptographic protocol executed by N senders and k

mix-servers, where typically N is quite large and k is fairly small, e.g., N = 104

and k = 10. The functionality implemented by a mix-net corresponds to a trusted

party that collects inputs from the senders and then outputs the inputs in sorted

order. The main application of mix-nets is for electronic elections. All known e¬-

cient robust mix-nets exploit the homomorphic properties of cryptosystems such

as the El Gamal cryptosystem [16] in an essential way. A problem with using a

homomorphic cryptosystem in the submission phase is that corrupted senders

can submit inputs that are related to those of honest senders, i.e., the cipher-

texts should be non-malleable during the submission phase and then become

homomorphic when the mixing starts.

Formally, the proof of security fails if a semantically secure cryptosystem is used

directly. When using the simulation paradigm, e.g., universally composable secu-

rity [4], a mix-net is said to be secure if for every adversary attacking the mix-net

Work partly done while at ETH Z¨rich, Department of Computer Science.

u

R. Ostrovsky, R. De Prisco, and I. Visconti (Eds.): SCN 2008, LNCS 5229, pp. 293“308, 2008.

c Springer-Verlag Berlin Heidelberg 2008

294 D. Wikstr¨m

o

there is an ideal adversary (simulator), typically running the adversary as a black-

box, attacking the ideal mix-net (the trusted party mentioned above) such that

no environment can tell the two models apart. The simulator does not know the

inputs of the honest parties and replaces them in its simulation, e.g., by zero mes-

sages. It must also extract the inputs of corrupted parties in its simulation and

hand them to the ideal mix-net, since otherwise these inputs would be missing

in the output from the ideal mix-net and the environment could trivially distin-

guish the two models. Any successful adversary must result in a successful attack

against the underlying cryptosystem, which means that the simulator can not use

the secret key of the cryptosystem to extract the inputs of corrupt senders.

General Case. More generally, consider a cryptographic protocol that starts

with a submission phase where many parties submit ciphertexts formed with a

public key pk , and a smaller group of servers hold shares of the secret key sk

corresponding to pk . The servers then compute and publish some function of

the input plaintexts. Typically, e¬cient protocols exploit the algebraic structure

of the cryptosystem, e.g., homomorphic properties. The problem with using a

semantically secure cryptosystem directly in such protocols is that it does not

guarantee that the plaintexts submitted by corrupt parties are unrelated to those

submitted by honest users.

Formally, the problem surfaces when the cryptographer constructing the pro-

tocol tries to reduce the security of his/her scheme to the security of the cryp-

tosystem. If the simulation paradigm is used, some kind of simulator must be

constructed and the simulator must extract the values of the corrupt parties to

be able to hand these to an ideal version of the protocol. The existence of a

successful adversary must contradict the security of the cryptosystem, i.e., ex-

traction must be done without using the secret key of the cryptosystem. This is

not possible using only a semantically secure cryptosystem.

Submission Problem. The submission problem is how to ¬nd a submission scheme

such that: (I) the inputs of corrupted parties can be extracted by the simulator

without using the secret key, and (II) its output is a list of ciphertexts of the

form expected by the servers computing the result. These requirements are es-