The key observations needed to extend Cramer™s and Shoup™s proof of CCA2-

security are:

1. The projective property of hash proofs implies that proofs computed using

a witness and hash proofs computed using the private key k are identical

(indeed this is how a hash proof is veri¬ed). This means that the holder of k

can “perfectly simulate” proofs without the witness, i.e., even if k is made

public the “simulated proof” looks exactly like a proof computed using a

witness.

2. The soundness of proofs computed by an adversary before k is made public,

is not decreased by the publishing of k.

The generic Cramer-Shoup scheme generalizes several concrete schemes de-

scribed in [11], such as the El Gamal based scheme in the introduction, but also

schemes based on the Paillier cryposystem [22]. Both schemes are common in

e¬cient protocols.

3.3 Proof of Proposition 1

Conceptually, we follow the proof of Cramer and Shoup, but our proof is some-

what simpli¬ed, since we ignore the problem of approximating the hash families

by e¬ciently computable hash families.

304 D. Wikstr¨m

o

Denote by Tb the machine that simulates the experiment Expsub’b B ,A (n)

(0)

CS,CS

with some adversary A ∈ PT— , except that when computing the challenge cipher-

text (x, e, π), the two hash proofs π and π are computed as π = PEval0 (Λ, k, x) =

Hk (x) and π = PEval1 (Λ, ki , x, e) = Hki (x, e), where i is the challenge index cho-

sen by the adversary. By the projectivity of hash proofs this does not change the

distribution of the experiment.

(0)

We now change Tb step by step until it is independent of b.

(1) (0)

Claim 1. Denote by Tb the machine Tb except that x is chosen randomly in

(0) (1)

X \ L. Then | Pr[Tb = 1] ’ Pr[Tb = 1]| is negligible.

Proof. Denote by Amem an algorithm that tries to solve the subset membership

problem M. It accepts as input (Λ, x), where x either belongs to L or X \ L.

(0)

It simulates Tb except that it uses the instance Λ and de¬nes the challenge

ciphertext (x, e, π) using x from its input (Λ, x). Note that Amem is identically

(0) (1)

distributed to Tb or Tb depending on if x ∈ L or x ∈ X \L. From the hardness

(0) (1)

of M follows that | Pr[Tb = 1] ’ Pr[Tb = 1]| is negligible.

Denote by (ij , (πj , ej , πj )) the jth query to the decryption oracle Decsk (·) (·),

and let jl be the index of the last query before the adversary outputs its choice

of challenge index and messages. Denote by (x, e, π) the challenge ciphertext,

and let E be the event that A asks a decryption query (ij , (πj , ej , πj )) with

Hki (xj , ej ) = πj , xj ∈ X \ L, and j ¤ jl or xj = x, for some index j before it

j

requests sk A from its sk A -oracle (it may of course not ever do this).

ij (·)

Claim 2. Pr[E] is negligible.

Proof. Let Q be the total number of queries to the augmentation oracle pk (·)

made by the adversary. Without loss we assume that the adversary asks the

queries l = 1, . . . , Q.

(1)

De¬ne Al uni for l = 1, . . . , Q to be the machine that simulates Tb and

takes part in Experiment 2. The simulation is modi¬ed in that: sl is de¬ned

(1)

as the hash proof key received in Experiment 2, whenever Tb needs to check

a hash proof as PEval1 (Λ, kl , xj , ej ) = Hkl (xj , ej ) it simply queries its „kl (·, ·)-

oracle in Experiment 2 with (xj , ej ) instead, and when it needs to compute

PEval1 (Λ, kl , x, e) = Hkl (x, e) = π it outputs (x, e) and waits for Hkl (x, e) = π

from the experiment instead. The computational universal2 property and the

union bound then implies the claim.

Note that the computational universal2 property can be applied despite that the

experiment reveals private hash proof keys, since by de¬nition of submission

security the adversary only wins if it never asks a decryption query after this

point. This observation is the only essential change to the original proof.

(2) (1)

Denote by Tb the machine Tb , except that it outputs ⊥ if the event E oc-

(2)

curs. The machine Tb may not be e¬cient, but this does not matter since the

remainder of the argument is statistical in nature.

Simpli¬ed Submission of Inputs to Protocols 305

(3) (2)

Claim 3. Denote by Tb the machine Tb except that in the computation of

(2)

the challenge ciphertext (x, e, π), π is chosen randomly in Π. Then | Pr[Tb =

(3)

1] ’ Pr[Tb = 1]| is negligible.

Proof. Consider an arbitrary ¬xed instance Λ of the subset membership problem

and an arbitrary ¬xed random string of the experiment conditioned on the event

E. De¬ne a function f : X — S — Π ’ {0, 1} as follows. Let f (x, ±(k), π)

¯

(2)

simulate Tb except that the input parameters are used in the computation of

(2)

the challenge ciphertext. Note that f exists, since Tb outputs ⊥ if the event

E occurs and ±(k) determines Hk on L by the projective property of H, so

the answers of all queries are determined by ±(k). When k ∈ K, x ∈ X, and

(2)

π ∈ Π are randomly chosen, f (x, ±(k), Hk (x)) is identically distributed to Tb

(3)

and f (x, ±(k), π) is identically distributed to Tb . The claim now follows from

the smoothness of P.

Conclusion of Proof of the Proposition. To conclude the proof of the proposition

(3) (3)

we simply note that the distributions of T0 and T1 are identical since Π is a

(0) (0)

group. The claims above now imply that | Pr[T0 = 1]’Pr[T1 = 1]| is negligible.

4 Applications of Submission Security

The original motivation for this paper was to come up with a practical non-

interactive submission phase in El Gamal based mix-nets. For readers that are

not familiar with mix-nets we give an informal description of a construction that

goes back to Sako and Kilian [28]. In the full version [32] we also illustrate how the

notion of submission secure augmented cryptosystems can be used to construct

and analyze the submission phase of a protocol in a modularized way for general

secure function evaluation, and explain how this generalizes the mix-net setting

in the informal description.

4.1 Informal Description of Application to a Mix-Net

There are many senders S1 , . . . , SN and few mix-servers M1 , . . . , Mk , e.g., N =

104 and k = 10. In a joint key generation phase the mix-servers generate a

joint public key (g, h) such that each mix-server holds a veri¬able secret share

sj of the joint secret key z such that h = g z . This can be done using Feld-

man veri¬able secret sharing [14]. To submit a message mi ∈ Gq , a sender

Si computes an El Gamal ciphertext (u0,i , e0,i ) = (g ri , hri mi ), where ri ∈ Zq

is randomly chosen. Then the mix-servers take turns at re-encrypting, using

the homomorphic property of El Gamal, and permuting the list of ciphertexts.

In other words, for j = 1, . . . , k, Mj computes and publishes {(uj,i , ej,i )} =

{(uj’1,πj (i) g tj,i , ej’1,πj (i) htj,i )}, where tj,i ∈ Zq and πj are random. Finally, the

mix-servers jointly and veri¬ably decrypt the list {(uk,i , ek,i )} output by the last

mix-server Mk using their shares sj , sort the result, and output it.

306 D. Wikstr¨m

o

The idea is that due to the transformations computed by the mix-servers the

correspondence between the output plaintexts and the input ciphertexts should

be hidden. To ensure correctness, each mix-server also proves in zero-knowledge

that it processed the list of ciphertexts correctly. This is done using a so called

proof of a shu¬„e [21,15].

Unfortunately, the construction is completely insecure [24], since a malicious

sender Sl may compute its ciphertext as (u0,l , e0,l ) = (ua , ea ) for some random

0,i 0,i

a

exponent a and then identify a matching pair (mi , mi ) in the ¬nal output, where

mi is the message sent by Si . This reveals the message mi sent by the honest

sender Si . Intuitively, what is needed is a non-malleable cryptosystem, but on