Cryptography Reference
In-Depth Information
EncryptOracle(m,ψ)
DecryptOracle(c,u)
CorruptOracle(u)
retrieve ek;
retrieve sk
u
;
T ← T∪{u}
c ← Encrypt(ek,m,ψ);
return Decrypt(c,sk
u
);
retrieve sk
u
;
return c;
return sk
u
;
Experiment Exp
re
A
(1
n
)
h(Φ,{k
j
}
j∈J
), (J
1
,K
1
),..., (J
n
,K
n
)i←KeyGen(1
n
); T ←∅
ek = (Φ,{k
j
}
j∈J
); sk
u
= (J
u
,K
u
) for u = 1,...,n
ψ
∗
←A
EncryptOracle(),DecryptOracle(),CorruptOracle()
(Φ)
m
0
,m
1
←M; b ←{0,1};
c = hj
1
,..., j
s
,
E
k
j
1
(m
1
),...,
E
k
j
s
(m
1
)i← Encrypt(ek,m
1
,ψ
∗
)
b
0
←A
EncryptOracle()
({sk
i
}
i∈T
,m
b
,c)
return 1 if and only if b = b
0
and
ψ
∗
is an instruction that excludes all members of T.
Fig. 2.5. The initial security game Exp
0
.
output line to behave as follows: if it happens that the index of (v + 1)-th
subset in the challenge ciphertext in line 5 does not match j[w] then a ran-
dom coin flip is returned as the output of the experiment. If it happens that
v + 1 > s the s-th subset is used in the test.
Let p
1
be the probability that experiment Exp
1
returns 1 and similarly
let p
0
be the probability that the experiment Exp
0
returns 1. Observe that in
the case v ≥ s, the sequence of encryptions no longer contains any information
on b, and the same is true for all other information given to the adversary. It
follows that the adversary's view is independent of b and therefore it is easy
to see that p
1
=
2
.
On the other hand, let us assume that the adversary has advantage of at
least ε in being succesful on the original experiment Exp
0
, i.e., without loss
of generality, p
0
≥ 1/2 + ε. This suggests that
p
1
≥ 1/2 +
ε
|Φ|
It follows there is a gap of ε/|Φ| between p
1
,p
1
and by applying the triangular
inequality we obtain that there must exist some 0 < v
0
≤ t such that
ε
t·|Φ|
| p
v
0
−1
1
−p
v
0
1
|≥
Experiment Exp
2
. This experiment, for v = 0,...,t is identical to Exp
1
,
except that one of the keys is replaced with a random key, i.e., the way the
normal key generation algorithm KeyGen works in line 1 of the game is
modified. Specifically, in the modified game we employ the alternative key
generation KeyGen
j[w]
. In case a user owning this key gets corrupted the ex-
periment fails and returns a random coin flip. We denote by p
2
the probability
the experiment returns 1.
