Cryptography Reference
In-Depth Information
of A within experiment Exp
1
can be carried out by B without problem by
resorting to its encryption oracle whenever needed.
Based on the assumption on the underlying encryption scheme we have
that |Prob[Exp
ke
B
(1
n
)]−1/2|≤ ε
p
. We observe that in the key encapsulation
attack of B in the conditional space b = 0, the adversary B
kem
(1
n
) operates
identically to the experiment Exp
v−
1
while in the conditional space b = 1 it
operates identically to the experiment Exp
1
. Based on this derive the proof
of the claim:
|Prob[Exp
kem
B
(1
n
)] −1/2|≤ ε
p
Prob[Exp
kem
B
(1
n
)|b = 0] + Prob[Exp
kem
B
|
2
(1
n
)|b = 1]
−1/2|≤ ε
p
|
2
Prob[Exp
v−1
= 0] + Prob[Exp
1
= 1]
−1/2|≤ ε
p
|
2
(1−p
v−
1
+ p
1
) −1/2|≤ ε
p
|p
v−
1
−p
1
|≤ 2ε
p
1
We are now ready to give the proof of the theorem. First recall from our
first claim that there is a v
0
∈{1,...,n} such that
1
|≥
ε
| p
v
0
−1
1
−p
v
0
n
We also have |p
v
0
−1
1
−p
v
0
1
|≤ 2ε
p
. Hence, the overall security parameter of
A satisfies ε ≤ 2n·ε
p
which completes the proof.
The obvious shortcoming of the above scheme is that the ciphertext length
is linear in n. A nontrivial approach to reduce the transmission overhead
involves the usage of fingerprinting codes. We will next present a number of
multiuser encryption schemes that are based on fingerprinting codes.
3.2.2 Multiuser Encryption Schemes Based on Fingerprinting
Codes
We now introduce three different encryption schemes that are all sharing the
same key distribution algorithm based on fingerprinting codes. All schemes
rely on an underlying encryption scheme (
E
,
D
) with plaintext space M and
key space K.
The key assignment for users is done through an (`,n,q) fingerprinting
code over an alphabet Q of size q where n amounts to the number of users.
For the sake of simplicity and without loss of generality we will assume that
Q = {1,...,q}.
KeyDist
F
: The key distribution algorithm employs a q-ary fingerprinting
code
F
= (CodeGen
`
,Identify). Given 1
n
, the algorithm first produces
a (`,n,q)-code W = {w
1
,...,w
n
} where (W,ik) ← Codegen
`
(1
n
) over
an alphabet Q.
