but there are also several natural additional properties that we can look for, or

even require, in the submission phase.

(i) The solution should be provably secure under standard assumptions in the

plain model, i.e., without any random oracles or generic groups.

(ii) The submission of inputs should be non-interactive for submittors.

(iii) The solution should be very e¬cient for all parties in terms of computation

and communication. More precisely, when N and k denotes the number of

submittors and servers respectively, then the computational complexity of

each submitter should be independent of k, the communication complexity

of each server should be independent of N , and the computational com-

plexity of each server should be of the form T (k)+T (N ) for some functions

T and T .

Simpli¬ed Submission of Inputs to Protocols 295

1.1 Previous Work

Informally, we may view any solution to the problem as a form of proof of

knowledge of the encrypted plaintext, since any solution must allow the simulator

to extract the submitted plaintext without knowledge of the secret key of the

semantically secure cryptosystem. We classify the solutions in the literature and

some extensions as follows:

1. A non-interactive proof of knowledge in the random oracle model is used,

either using the Naor and Yung double ciphertext trick, or with rewinding.

Such solutions are typically very e¬cient, but unfortunately only heuristi-

cally secure [5]. Note that the CCA2-secure cryptosystems in the random

oracle model given by Shoup and Gennaro [29] may be viewed as instantia-

tions of this solution.

2. An interactive proof of knowledge [17] is used, either with a straight-line

extractor in the public key setting using the Naor and Yung [20] double-

ciphertext trick, or with a rewinding extractor.

3. A non-interactive proof of knowledge using general techniques [2] is used.

This is not e¬cient for either the submittor or the servers, even using the

recent techniques of Groth et al. [18]. One could also use the fairly general

zero-knowledge proofs based on homomorphic encryption of Damg˚ Fazioard,

and Nicolosi [12], but this requires non-standard assumptions. Note that

using a non-interactive proof in this way is essentially the construction of a

CCA2-secure cryptosystem under general assumptions given by Sahai [27]

based on the Naor-Yung double-ciphertext trick, but starting from a concrete

semantically secure cryptosystem with useful structure.

4. A non-interactive (for the submitter) proof of knowledge based on veri¬able

secret sharing is used, for example using techniques from Abe, Cramer, and

Fehr [1]. Then the computational and communication complexity of the sub-

mitting party grows linearly with the number of servers, since each server

must receive an encrypted secret share, and the servers must interact for

each submitted ciphertext to verify its proof.

5. Non-interactive secret-key proofs using Cramer and Damg˚ [7] could be

ard

used. Their technique allows a prover and veri¬er to set up a secret key in a

preliminary phase that later allows the prover to show that it behaves in a

way consistent with the secret keys. Their scheme could be used in two ways.

Either each submittor would take part in a protocol in the preliminary phase

where the needed correlated secret keys are generated, or the servers would

generate secret keys relative each other that allow them to prove that they

performed the veri¬cation of a Cramer-Shoup ciphertext correctly. In the

former case, interaction is moved to a preliminary phase, but each submittor

must still interact with the servers and the servers must store a secret key

for each submittor. In the latter case, submitting is non-interactive for the

submittor, but each server must send and receive a non-interactive proof

for each sender, i.e., its communication complexity with the other servers is

linear in N .

296 D. Wikstr¨m

o

6. An arbitrary CCA2-secure cryptosystem is used and ciphertexts are trans-

lated into suitable semantically secure ciphertexts using general multiparty

computation techniques. This is ine¬cient both in terms of computation and

communication.

7. A special CCA2-secure cryptosystem such that a ciphertext can be trans-

formed more easily into a new ciphertext for the basic semantically secure

scheme needed by the servers is used. We list the solutions of this type we

are aware of below.

(a) Canetti and Goldwasser [6] and Lysyanskaya and Peikert [19] have given

CCA2-secure cryptosystems with distributed decryption which allows

transforming ciphertexts into ciphertexts for semantically secure cryp-

tosystems. These either involve interaction, expensive setup assumptions,

or only work for a small number of servers.

(b) Boneh, Boyen, and Halevi [3] give a CCA2-secure cryptosystem with

distributed decryption that may be viewed as containing a semantically

secure cryptosystem, but its security is based on a non-standard com-

plexity assumption based on pairings.

(c) Cramer, Damg˚ and Ishai [8] present a solution based on distributed

ard,

pseudo random functions and share conversion that is reasonably e¬cient

for a small number of servers and requires communication linear in the

number of ciphertexts between the servers to verify validity.

8. Prabhakaran and Rosulek [25] present a re-randomizable and replayable

CCA secure cryptosystem where one could view the transformation as triv-

ial, i.e., nothing would be done with the ciphertexts before handing them to

the underlying protocol.

This work is interesting, but we are not aware of any (interesting) underlying

protocol that accepts input ciphertexts of their cryptosystem. In fact, the

authors point out that it can not be used directly to construct a mix-net,

and even if that would be possible it would give an ine¬cient mix-net due

to the larger and more complex ciphertexts.

We remark that our work was publicly available [32] before their work was

published.

To summarize, there are numerous solutions to the submission problem which

satis¬es properties (I) and (II), but no such solution has the properties (i)-(iii)

listed above for any interesting underlying protocol.

What Is Used In Existing Mix-Nets? There are numerous proposed mix-nets

with informal security arguments. If the submission problem is considered at all,

the Fiat-Shamir heuristic is used (mostly even without a proof in the random

oracle model). In the provably secure mix-nets either a secret sharing based

solution is used [30], or an interactive proof of knowledge is used [31,33].

1.2 Our Contribution

We give a simple solution to the submission problem that is e¬cient both in

terms of computation and communication. Although the solution is nothing

Simpli¬ed Submission of Inputs to Protocols 297

more than an observation on the Cramer-Shoup cryptosystem, it is novel and

important, since it gives a truly practical and provably secure way for senders to

submit their inputs to a mix-net, and this solution has eluded researchers ever

since the Cramer-Shoup cryptosystem appeared 10 years ago.

The Idea. Recall the original Cramer and Shoup scheme [10]. The cryptosystem

is deployed in a group Gq of prime order q in which the decision Di¬e-Hellman

assumption is assumed to be hard. The key generator ¬rst chooses two random

generators g0 , g1 ∈ Gq . Then it chooses x0 , x1 , y0 , y1 , z ∈ Zq randomly and de-

yy

xx

¬nes c = g0 0 g1 1 , d = g0 0 g1 1 , and h = g0 . It generates a collision-free hash

z

function H. Finally, it outputs (pk , sk ) = ((H, g0 , g1 , c, d, h), (x0 , x1 , y0 , y1 , z)).

To encrypt a message m ∈ Gq using the public key pk the encryption algorithm

chooses r ∈ Zq randomly and outputs (u0 , u1 , e, v) = (g0 , g1 , hr m, cr drH(u0 ,u1 ,e) ).

rr

To decrypt a tuple (u0 , u1 , e, v) ∈ G4 using the secret key sk the decryption algo-

q

y0 y1 H(u0 ,u1 ,e)

x0 x1

rithm tests if u0 u1 (u0 u1 ) = v to check the validity of the ciphertext.

If so it outputs e/u0 , and otherwise the unit element of the group.1

z

Note that h = g z and z have the form of an El Gamal [16] public and secret

key respectively and that (u0 , e) is nothing more than an El Gamal ciphertext.

This is of course not a new observation. What seems to be a new observation is

the fact that the holder of the secret key may reveal (x0 , x1 , y0 , y1 ) without any

loss in security as long as it never decrypts any ciphertext constructed after this

point, and that this solves the submission problem.

Generalizing and Applying the Idea. To allow us to generalize the observation

about the original Cramer-Shoup scheme and identify a class of cryptosystems

for which it applies, we introduce the notion of an augmented cryptosystem which

contains another cryptosystem as a component. In applications, the latter cryp-