Cryptography Reference
In-Depth Information
forest over Φ and f c is a key extender with insecurity ε and h F is the height
of the forest F Φ plus one.
Proof. We will first show the existence of 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 adversary A, Adv key−ind
A
(1 n ) = |Prob[Exp key−ind
A
(1 n ) = 1] − 2 | ≤
h F ·ε, where the experiment is defined as in figure 2.4 .
We consider a sequence of key generation KeyGen j i procedures that are
successive modifications of the way key generation works in the scheme BE F,f c
for i = 0,...,l. We first set KeyGen j 0 to be exactly the key generation
KeyGen. The procedure KeyGen j 1 modifies KeyGen j 0 by substituting the
labels of all level 1 children of the key tree F j with random values from K
while respecting the key derivation method for all remaining keys. Based on
the property of the key extender f c this incurs a distance of at most ε in
distinguishing these two key generation algorithms. We continue in the same
fashion for procedures i = 2,...,l,l+1, following the path from the tree root
of F j to S j . At each level we incur a distance of at most ε. At procedure
KeyGen j l the key k j has been substituted by a random element of K. At last
in the final modification, for l + 1, we substitute the labels of all children of
the subset S j with random values to obtain KeyGen j . Finally, we have the
value k j selected independently at random.
Based on this we derive that the distribution KeyGen of the scheme BE F,f c
has a distance of at most h F ·ε, from the distribution KeyGen j for any j.
This proves the fact that for any key indistinguishability adversary A against
the broadcast encryption BE F,f c where F is a key forest over Φ and f c is a key
extender with insecurity ε, It holds that Adv key−ind
A
≤ h F ·ε where h F is the
height of the forest F Φ plus one and KeyGen j
is defined as above.
2.4 Revocation in the Key-Poset Framework
In order for a set system to be suitable for the design template of Figure 2.2
it should have an e cient covering algorithm that can be used for revocation.
It follows that any proposal for a set system should be accompanied by a
description of how the revocation algorithm works. Instead of treating the
design of a fully-exclusive set systems with an e cient revocation algorithm
on a case-by-case basis, in this chapter we will introduce an algebraic property
that implies the existence of a revocation algorithm that optimally works for
any set system that satisfies the property.
This section is structured as follows. In section 2.4.1 we will formalize the
revocation problem in the key-poset framework and we will show its relation
to a basic problem for a poset called PatternCover . We show that revocation
is interreducible to PatternCover through an algebraic manipulation of the
Search WWH ::




Custom Search