sk

on if the NIZKP was accepted or not. The augmentation algorithm Aug takes

(pk B , CRS) as input and outputs (pk B , sk B ) = KgB (1n ). The stripping algo-

1 0 0

rithm Strip checks the NIZKP and outputs c0 or Encpk B (0, 0) depending on if

0

the NIZKP was accepted or not.

3 Generic Cramer-Shoup Is Submission Secure

The fact that the generic CCA2-secure cryptosystem of Cramer and Shoup is

submission secure if we view it as an augmentation of a basic semantically secure

cryptosystem is quite easy to see from their security proof. On the other hand we

need to prove that this is indeed the case. Thus, we recall their scheme and prove

this fact, but we use coarse-grained and streamlined de¬nitions. We also take the

liberty of ignoring the technical problem of constructing e¬ciently computable

hash families, since this complicates the de¬nitions and does not add anything

to our exposition (see [11] for details).

3.1 Preliminaries

Subset Membership Problems. A subset membership problem consists of three

sets X, L X, and W , and a relation R ‚ X — W . The idea is that it should

be hard to decide if an element is sampled from L or from X \ L. To be useful

in cryptography we also need some algorithms that allow us to sample instances

and elements, and check for membership in X.

De¬nition 3. A subset membership problem M consists of a collection of dis-

tributions (In )n∈N , an instance generator Ins ∈ PPT, a sampling algorithm

Sam ∈ PPT, and a membership checking algorithm Mem ∈ PT such that:

Simpli¬ed Submission of Inputs to Protocols 301

1. In is a distribution on instance descriptions Λ[X, L, W, R] specifying ¬nite

non-empty sets X, L X, and W , and a binary relation R ‚ X — W .

2. On input 1n , Ins outputs an instance Λ with distribution statistically close

to In .

3. On input 1n and Λ[X, L, W, R] ∈ [In ] (the support of In ), Sam outputs

(x, w) ∈ R, where the distribution of x is statistically close to uniform over

L.

4. On input 1n , Λ[X, L, W, R] ∈ [In ], and ζ ∈ {0, 1}—, Mem outputs 1 or 0

depending on if ζ ∈ X or not.

De¬nition 4. Let M be a subset membership problem. Sample Λ from In and

let x and x be randomly distributed over L and X \ L respectively. We say that

M is hard if for every A ∈ PT— : | Pr[A(Λ, x) = 1]’Pr[A(Λ, x ) = 1]| is negligible.

Hash Families. Hash families are well known in the cryptographic literature and

there are many variations. We assume that all families are indexed by a security

parameter n.

De¬nition 5. A projective hash family H = (H, K, X, L, Π, S, ±) consists of

¬nite non-empty sets K, X, L X, Π, and S, a function ± : K ’ S, and a

collection of hash functions H = (Hk : X — Π ’ Π)k∈K , where ±(k) determines

Hk on L — Π .

De¬nition 6. Let H = (H, K, X, L, Π, S, ±) be a projective hash family, and let

k ∈ K be random. Then H is universal2 if for every s ∈ S, x, x ∈ X with x ∈

L ∪ {x }, and πx , πx , π, π ∈ Π, Prk [Hk (x, πx ) = π § Hk (x , πx ) = π | ±(k) = s]

is negligible.

The following de¬nition and lemma are stated informally in [11].

Experiment 2 (Computationally Universal2 , Expcuni2 (n)). Let „k be the

H,A

predicate de¬ned by „k ((x, πx ), π) ⇐’ Hk (x, πx ) = π, and consider the fol-

lowing experiment.

k←K

(x, πx , state) ← A„k (·,·) (±(k))

← A„k (·,·) (Hk (x, πx ), state)

Denote by ((xi , πx,i ), πi ) the ith query to „k , and let il be the index of the

last query before the ¬rst output. If A asks a query ((xi , πx,i ), πi ) to „k with

Hk (xi , πx,i ) = πi , xi ∈ X \ L, and i ¤ il or xi = x, then output 1 and

otherwise 0.

302 D. Wikstr¨m

o

De¬nition 7. A projective hash family H is computationally universal2 if for

every A ∈ PT— , Pr[Expcuni2 (n) = 1] is negligible.

H,A

Lemma 1. If a projective hash family H is universal2 , then it is computationally

universal2 .

Proof. Denote by ((xi , πx,i ), πi ) the ith query of A and let Ei be the event that

Hk (xi , πx,i ) = πi , xi ∈ X \ L, and i ¤ il or xi = x. Condition on arbitrary ¬xed

values of (x, πx ), π = Hk (x, πx ), and ±(k). Then the conditional probability of

the event Ei is negligible by universiality2 of H. Since the ¬xed values are arbi-

trary, this holds also without conditioning. Finally, A asks at most a polynomial

number of queries and the lemma follows from the union bound.

De¬nition 8. Let H = (H, K, X, L, Π, S, ±) be a projective hash family, and let

k ∈ K, x ∈ X \ L, and π ∈ X be random. Then H is smooth if for every πx ∈ Π

the distributions of (x, πx , ±(k), Hk (x, πx )) and (x, πx , ±(k), π) are statistically

close.

Universal Hash Proof Systems. Informally, a hash proof system may be viewed

as a non-interactive zero-knowledge proof system where only the holder of a

secret key corresponding to the public common random string can verify a proof.

Strictly speaking, the de¬nition below corresponds, in the unconditional case, to

a special case of what Cramer and Shoup [11] call “extended strongly (smooth,

universal2 )” hash proof system.

De¬nition 9. A (smooth, (computational) universal2 ) hash proof system P for

a subset membership problem M associates with each instance Λ[X, L, W, R] a

(smooth, (computationally) universal2 ) projective hash family H =

(H, K, X, L, Π, S, ±), and the following algorithms

1. A key generation algorithm Gen ∈ PPT that on input 1n and Λ ∈ [In ]

(the support of In ) outputs (s, k), where k is randomly distributed in K and

s = ±(k).

2. A private evaluation algorithm PEval ∈ PT that on input 1n , Λ ∈ [In ],

k ∈ K, and (x, πx ) ∈ X — Π outputs Hk (x, πx ).

3. A public evaluation algorithm Eval ∈ PT that on input 1n , Λ ∈ [In ], ±(k)

with k ∈ K, (x, πx ) and w, with (x, w) ∈ R and πx ∈ Π, outputs Hk (x, πx ).

4. A membership checking algorithm Mem ∈ PT that on input 1n , Λ ∈ [In ],

and ζ ∈ {0, 1}— outputs 1 or 0 depending on if ζ ∈ Π or not.

3.2 Generic Scheme of Cramer and Shoup

Given the de¬nitions above it is not hard to describe the generic cryptosys-

tem of Cramer and Shoup [11]. Let M be a hard subset membership prob-

lem, such that Π can be ¬tted with a group operation for any Λ, let P0 =

(Gen0 , PEval0 , Eval0 , Mem0 ) be a smooth hash proof system for M, and let P1 =

(Gen1 , PEval1 , Eval1 , Mem1 ) be a computationally universal2 hash proof system

for M.

Simpli¬ed Submission of Inputs to Protocols 303

Key Generation. Compute Λ[X, L, W, R] = Ins(1n ), (s, k) = Gen0 (1n , Λ),

(s, k) = Gen1 (1n , Λ), and output the key pair (pk , sk ) = ((s : Λ, s), (k : k)).

Encryption of a message m ∈ Π. Compute (x, w) = Sam(Λ), π =

Eval0 (Λ, s, x, w) = Hk (x), e = m + π, and π = Eval1 (Λ, s, x, w, e) = Hk (x, e),

and output (x, e, π).

Decryption of a ciphertext (x, e, π). Output m = e ’ PEval0 (Λ, k, x) = e ’

Hk (x), only if PEval1 (Λ, k, x, e) = Hk (x, e) = π and otherwise output 0.

We have not modi¬ed the cryptosystem, except that we have introduced a colon

in the notation to distinguish the two parts of the public and secret keys as

needed in the de¬nition of submission security, and we have replaced the special

symbol ⊥ by the zero plaintext.

Write CS = (Kg, Enc, Dec), and let CS B = (KgB , EncB , DecB ) be the underly-

ing basic cryptosystem de¬ned as follows. It has public key (Λ, s) and secret key

k. A message m ∈ Π is encrypted as (x, e), where e = Eval0 (Λ, s, x, w) + m, and

a ciphertext (x, e) is decrypted by computing e ’ PEval0 (Λ, k, x). It is clear that

CS is an augmentation of CS B , since we can de¬ne Aug(Λ, s) = Gen1 (1n , Λ) and

de¬ne Strippk ,k (x, e, π) to output (x, e) if PEval1 (Λ, k, x, e) = π and otherwise

Encpk B (0, 0).

Cramer and Shoup prove (see Theorem 1 in [11]) that CS is CCA2-secure

under the assumption that M is hard. We prove a stronger result.

Proposition 1. If M is a hard subset membership problem, then CS is a sub-