4.3 Security Results

From the de¬nition of the algorithms, it should be apparent that running PSig

with a warrant correctly produced by registered users returns a signature which

is accepted by PVer and correctly opened by Open. Moreover, the de¬ned scheme

satis¬es all security notions from Sect. 3:

Lemma 1. The proxy signature scheme PS is anonymous (De¬nition 1).

Lemma 2. The proxy signature scheme PS is traceable (De¬nition 2).

Due to space limitations, we refer to the full version [FP08] for the proofs of

Lemmata 1 and 2.

Lemma 3. The proxy signature scheme PS is non-frameable (De¬nition 3).

Proof (of Lemma 3).

Figure 6 shows experiment Expn-frame rewritten with the code of the respective

PS,A

algorithms. Note that we can dispense with the OSndToU-oracle, because in our

scheme the user communicates exclusively with the issuer.

We construct an adversary B against the signature scheme DS having input a

veri¬cation key pk and access to a signing oracle OSig . B simulates Expn-frame for

PS

A, except that for one random user registered by A via ISndToU, B sets pkσ to

his input pk, hoping that A will frame this very user. If B guesses correctly and

A wins the game, a forgery under pk can be extracted from the proxy signature

returned by A. Let n(») be the maximal number of ISndToU queries A makes.

Adversary B and its handling of A™s ISndToU and SK oracle queries or detailed

in Fig. 6. To answer oracle calls Del and PSig with argument pk— = (pk, ··), B

replaces the line with Sig(skσ, (task, pkσ1 , . . .)) in the respective algorithms by

a query to his own signing oracle. For all other public keys, B holds the secret

keys and can thus answer all queries.

Let S denote the event (pk±, pkω, pkσ1 , pkµ1 , certω1 , task, M, C) ∈ LR and

E1 , E2 , E3 denote the union of S and the event that Expn-frame returns 1 in

line 7, 8, 9, respectively. Then the following holds:7

Advn-frame (») ¤ Pr[E1 ] + Pr[E2 ] + Pr[E3 ] + Pr[Expn-frame (») = 1 § S]

¯

PS,A PS,A

We now show that the four summands are negligible:

—

1. Consider the event E1 := [E1 § pkσ1 = pk]. Then, since S is satis¬ed,

we have Ver pk, (task, pkσ1 , pkσ2 ), warr1 = 1,. So, B returns a valid mes-

sage/signature pair.

The forgery is valid, since B did not query its oracle for (task, pkσ1 , pkσ2 )

as this only happens when A queries ODel ((pkσ1 , ··), {··, task, ··}, (pkσ2 , ··)),

which by E1 is not the case. Moreover, B simulates perfectly, for E1 implies

OSK ((pk, ··) was not queried. All in all, we have

Adveuf-cma ≥ Pr[E1 ] = Pr[pk— = pk1 ] · Pr[E1 ] =

— 1

Pr[E1 ]

DS,B n(»)

If not otherwise de¬ned, we use Adv• (·) as shortcut for Pr[Exp• (·) = 1].

7

•• ••

Anonymous Proxy Signatures 213

Expn-frame (»)

PS,A

(pk±, sk±) ← Kσ (1» ); (pkω, skω) ← Kσ (1» ); crs ← {0, 1}p(»)

1

pp := (», pk±, pkω, crs)

2

(ok, pk, task, M, σ) ← A(pp, sk±, skω : ISndToU, SK, Del, PSig)

3

parse ok ((pkσ1 , pkµ1 , cert1 , certω1 , pp), skµ1 ); σ (C, π)

4

» ¡

if Vk 1 , (pk±, pkω, pkσ1 , pkµ1 , certω1 , task, M, C), π, crs = 0 then return 0

5

(pkσ2 , . . . , pkσk , cert2 , . . . , certk , warr1 , . . . , warrk’1 , s) := Dec(skµ1 , C)

6

if pk1 ∈ HU and no queries ODel (pk1 , {··, task, ··}, pk2 ) then return 1

7

if ∃ i : pki ∈ HU and no queries ODel (pki , warr, {··, task, ··}, pki+1 )

8

with warr[j][0][1] = pkσj for 1 ¤ j ¤ i then return 1

if pkk ∈ HU and no queries OPSig (pkk , warr, task, M )

9

with warr[j][0][1] = pkσj for 1 ¤ j ¤ k then return 1

return 0

10

OISndToU (…) OSK ((pkσ, ··))

»

(pkσ, skσ) ← Kσ (1 ) if ∃ skσ : (pkσ, skσ) ∈ HU ,

1 1

HU := HU ∪ {(pkσ, skσ)} delete the entry and return skσ

2 2

return pkσ otherwise, return ⊥

3 3

Adversary B(pk : Sig(sk, ·))

j — ← {1, . . . , n}; j := 0

0

.

.

.

if pkσ1 = pk and no queries ODel ((pk1 , ··), {··, task, ··}, (pkσ2 , ··))

7

¡

then return (task, pkσ1 , pkσ2 ), warr1

if ∃ i : pkσi = pk and no queries ODel ((pkσi , ··), warr, {··, task, ··}, (pkσi+1 , ··))

8

with warr[j][0][1] = pkσj for 1 ¤ j ¤ i

¡

then return (task, pkσ1 , . . . , pkσi+1 ), warri

if pkσk = pk and no queries OPSig ((pkσk , ··), warr, task, M ) with

9

¡

warr[j][0][1] = pkσj for 1 ¤ j ¤ k, then return (task, pkσ1 , . . . , pkσk , M ), s

return 0

10

OISndToU (…) by B OSK ((pkσ, ··)) by B

—

j := j + 1; if j = j , return pk if pkσ = pk then abort

1 1

(pkσ, skσ) ← Kσ (1» ) else if ∃ skσ : (pkσ, skσ) ∈ HU

2 2

HU := HU ∪ {(pkσ, skσ)} delete entry, return skσ

3 3

return pkσ return ⊥

4 4

Fig. 6. Instantiated experiment for non-frameability and adversary B against DS

214 G. Fuchsbauer and D. Pointcheval

2. Consider the event [E2 § pkσi = pk]: Then S implies