Cryptography Reference
In-Depth Information
encrypting m
b
and testing the resulting ciphertext for equality to c. Further,
since we are only interested in key encapsulation we can require the encryption
oracle to only return encryptions of random plaintexts (as opposed to have
them adaptively selected by the adversary).
Key-indistinguishability.
To ensure the security of the broadcast encryption scheme based on an ex-
clusive set system, we have to perform the key-assignment in an appropriate
way, i.e., a user should not be able to extract any information on a key of
a subset that it does not belong to. Recall that for a set system Φ, where
Φ = {S
j
}
j∈J
, the KeyGen procedure generates a collection of keys {k
j
}
j∈J
,
one for each subset in Φ. Any user u ∈ [n] is provided with a key assignment
that is determined by the pair of sets hJ
u
,K
u
i where J
u
= {j ∈J | u ∈ S
j
}
and K
u
= {k
j
| j ∈ J
u
}. The key-indistinguishability property ensures that
any coalition of users are not able to distinguish the key k
j
0
of a subset
S
j
0
they do not belong to from a random key. We will formalize the key-
indistinguishability requirement through the following security-game.
EncryptOracle(m, j)
DecryptOracle(c, j)
retrieve k
j
, j
0
;
retrieve k
j
, j
0
;
return c ←
E
k
j
(m);
return
D
k
j
(c)
Experiment Exp
key−in
A
(1
n
)
b ←{0,1}; j
0
←A(Φ)
if b = 0 then (Φ,{k
j
}
j∈J
) ←KeyGen(1
n
)
else (Φ,{k
j
}
j∈J
) ←KeyGen
j
0
(1
n
)
b
0
←A
EncryptOracle(),DecryptOracle()
(hJ
u
,K
u
i
u∈S
j
0
)
return 1 if and only if b = b
0
Fig. 2.4. The security game for the key-indistinguishability property.
Definition 2.6. We say that the broadcast encryption
BE
based on an ex-
clusive set system satisfies the key indistinguishability property with distin-
guishing probability ε if there exists a family of key generation procedures
{KeyGen
j
}
j∈J
with the property that for all j, KeyGen
j
selects the j-th key
independently at random and it holds that for any probabilistic polynomial-
time A, Adv
key−ind
A
(1
n
) = |Prob[Exp
key−ind
A
(1
n
) = 1] −
2
| ≤ ε, where the
The definition of key indistinguishability suggests the following : the key
generation algorithm KeyGen makes such a selection of keys that it is impos-
sible for an adversary to distinguish with probability better than ε the key of
subset S
j
from a random key, even if it is given access to the actual keys of all
users that do not belong to S
j
as well as arbitrary encryption and decryption
capability within the key system.
