more e¬cient and simpler protocols. We also introduce a strengthened variation

of CCA2-security called submission security and observe that the generic scheme

of Cramer and Shoup [11] already satis¬es this stronger de¬nition. In the full

version [32] we also illustrate the use of the new notion by applying it to general

secure function evaluation, which strictly generalizes the notion of a mix-net.

The real e¬ciency gain from using our technique obviously depends on the

application, but it is clear that when the number of submittors N is large the

complexity of our solution based on the El Gamal cryptosystem is close to that

of the most e¬cient heuristic solution in the random oracle model. Due to the

cost of evaluating a pairing we also expect it to out-perform any solution based

on elliptic curves with pairings.

Limitations of Our Approach. When using our solution, no new inputs can be

accepted after part of the secret key is revealed. This is a minor drawback in

the targeted applications, since we have a large number of submitting parties

and executions of the underlying protocol are infrequent. When a new session

1

In [10] a special symbol ⊥ is output if the test fails, but this is only to simplify the

analysis. Any ¬xed output works just as well.

298 D. Wikstr¨m

o

is executed the servers simply generate a new key. However, it may be useful

to re-use the public key of the basic cryptosystem in the underlying protocol.

Thus, our de¬nitions require that the augmentation can be replaced by a freshly

generated augmentation without any loss in security. This allows using several

independent augmentations that may be revealed sequentially, i.e., inputs can be

processed in batches and then input to the same underlying protocol. We remark

that for general threshold decryption, e.g. [6], our approach is not reasonable,

since users requesting a decryption expect the result immediately.

1.3 Notation

We denote by PT and PPT the sets of deterministic and probabilistic polyno-

mial time Turing machines respectively, and write PT— for the set of non-uniform

polynomial time Turing machines. We use n to denote the security parameter,

and say that a function (n) is negligible if for every constant c there exists a

constant n0 such that (n) < n’c for n > n0 . If pk is the public key of a cryp-

tosystem, we denote by Mpk , Cpk , and Rpk the plaintext space, the ciphertext

space, and the randomness space respectively.

2 Augmented Cryptosystems

Keeping our observation about the original Cramer-Shoup cryptosystem in mind,

we formalize a general class of augmented cryptosystems that given part of the

secret key allow conversion of a ciphertext into a ciphertext of another basic

cryptosystem. In applications, the basic cryptosystem typically has special prop-

erties, e.g., it is homomorphic, that are exploited by the cryptographic protocol.

We introduce the following de¬nition.

De¬nition 1 (Augmented Cryptosystem). A cryptosystem CS = (Kg, Enc,

Dec) is an augmentation of a cryptosystem CS B = (KgB , EncB , DecB ) if there

exists an augmentation algorithm Aug ∈ PPT and a stripping algorithm Strip ∈

PT such that:

1. On input 1n , Kg computes (pk B , sk B ) = KgB (1n ) and (pk A , sk A ) = Aug(pk B ),

and outputs (pk , sk ) = ((pk A : pk B ), (sk A : sk B )).

2. On input ((sk A : sk B ), c), Dec outputs DecB B (Strippk ,sk A (c)).

sk

Clearly, any cryptosystem can be viewed as a trivial augmentation of itself, and

if it is CCA2-secure then the trivial augmentation is also submission secure as

de¬ned below, but we are interested in non-trivial augmentations where CS B

has structural properties useful in the construction of protocols.

Some readers may ¬nd it tempting to use a de¬nition that mirrors the Cramer-

Shoup cryptosystem more closely to avoid the existence of trivial augmentations,

i.e., one could explicitly require that it is possible to check the “validity” of

a ciphertext using sk A . We remind those readers that for most cryptographic

notions there are trivial instances, e.g., the identity map is a cryptosystem, and

we see no reason to impose unnecessary conditions on which particular properties

of the basic cryptosystem that should be considered useful.

Simpli¬ed Submission of Inputs to Protocols 299

2.1 Submission Security of Augmented Cryptosystems

Recall the game considered in the de¬nition of CCA2-security [20,13,26]. The ad-

versary is given a public key pk . Then it may ask any number of decryption queries

to a decryption oracle Decsk (·) holding the secret key sk corresponding to pk .

The adversary must then choose two challenge messages m0 and m1 . The game

is parameterized by a bit b and returns a challenge ciphertext of the form c =

Encpk (mb ). Then the adversary is again allowed to ask arbitrary decryption queries

to Decsk (·) with the exception of c, and must ¬nally output a guess b of the bit b.

If the cryptosystem is CCA2-secure, then the di¬erence in distribution of b when

b = 0 or b = 1 respectively, should be negligible. Consider the following game.

Experiment 1 (Submission Security, Expsub’b B ,A (n))

CS,CS

(pk B , sk B ) ← KgB (1n ) // Basic keys

(pk A , sk A ) ← Aug(pk B ) for j = 1, 2, 3, . . . // Augmentations

j j

(pk j , sk j ) ← (pk A : pk B ), (sk A : sk B ) // Augmented keys

j j

pk A ,sk A ,Decsk (·) (·)

(i, m0 , m1 , state) ← A (·) (·) (choose, pk B ) // Choice of challenges

c ← Encpk i (mb ) // Challenge ciphertext

pk A ,sk A ,Decsk (·) (·)

d←A (·) (·)

(guess, state) // Guess of adversary

The experiment returns 0 if Decsk (·) (·) was queried on (i, c) or if it was queried

on (j, c ) for some c after sk A was queried on j. Otherwise the experiment

(·)

returns d.

In the game above, the adversary is given a public key pk B of the basic

cryptosystem. It can request that the experiment generates an augmentation

(pk A , sk A ) = Aug(pk B ), stores (pk j , sk j ) = ((pk A : pk B ), (sk A : sk B )), and

j j j j

A B

returns pk j = (pk j : pk ) to the adversary. This is done by submitting the

integer j to its pk A -oracle. Any subsequent identical queries j give the same pk j .

(·)

It can ask decryption queries. This is done by submitting an index and ciphertext

pair (j, c ) to its Decsk (·) (·)-oracle. It can request that the experiment reveals an

augmentation sk A by submitting j to its sk A -oracle, but after such a query no

j (·)

more decryption queries of the form (j, c ) for some ciphertext c are allowed. Then

the adversary must choose an index i and two challenge messages m0 and m1 . The

game is parameterized by a bit b and returns a challenge ciphertext of the form

c = Encpk i (mb ). The adversary is then again allowed to: ask for more fresh public

keys, ask more decryption queries with the exception of decryption of (i, c), and

request more augmentations or augmentation keys. Finally, it outputs a guess b

of b. If the cryptosystem is submission secure, then the di¬erence in distributions

of b with b = 0 or b = 1 respectively should be negligible.

300 D. Wikstr¨m

o

We could equivalently have de¬ned a game where the game only generates an

augmentation if requested to do so by the adversary, but the above is conceptu-

ally simpler.

De¬nition 2 (Submission Security). An augmentation CS of CS B is sub-

mission secure if ∀A ∈ PT— : | Pr[Expsub’0 B A (n) = 1] ’ Pr[Expsub’1 B ,A (n) = 1]|

CS,CS CS,CS

is negligible.

Example 1. A simple example of a submission secure cryptosystem can be de-

rived from the scheme of Sahai [27] based on the Naor and Yung double cipher-

text trick [20]. A semantically secure cryptosystem CS B is given and a CCA2-

secure cryptosystem CS = (Kg, Enc, Dec) is constructed as follows. To generate

a public key, compute (pk B , sk B ) = KgB (1n ) and (pk B , sk B ) = KgB (1n ), and

0 0 1 1

generate a common reference string CRS. Then output the key pair (pk , sk ) =

((pk B : pk B , CRS), (sk B : sk B )). To encrypt a message m, output (c0 , c1 , π) =

0 1 0 1

(EncB B (m), EncB B (m), π), where π is a simulation sound non-interactive adap-

pk 0 pk 1

tively zero-knowledge proof (NIZKP) that the same message is encrypted in c0