Cryptography Reference
In-Depth Information
We next give the definition of a key-forest which is a partition of the set
system Φ in a set of trees, i.e., a forest.
Definition 2.20. Given a set system Φ, we say that F = {F 1 ,...,F v } is a
key-forest of Φ if
1. F i is a rooted directed tree for i = 1,...,k following the superset relation.
Specifically if S 1 is a descendant of S 2 in F i , it holds that S 1 ⊂ S 2 ; further,
F i is connected and there are no cycles in F i , i.e., there are no nodes
S 1 ,S 2 ,S 3 ,S 4 ∈ F i with S 1 ⊂ S 2 , S 1 ⊂ S 3 and S 2 ⊂ S 4 , S 3 ⊂ S 4 .
2. Any subset S ∈ Φ belongs to exactly one tree F i for some i ∈{1,...,k}.
We say the key-forest F Φ is of degree c if it consists of trees whose nodes
have degree strictly less than c.
We next give the definition for the broadcast encryption scheme BE F,f c
that demonstrates the key compression strategy that employs a key-forest F
of degree c and a key-extender f c : K 7→ K c . We use the notation f c (k) to
denote the i-th block of f c (k) for 0 < i ≤ c.
Definition 2.21. The scheme BE F,f c where F is a key-forest hF 1 ,...,F v i and
f c is a key-extender follows the template of Figure 2.2 with the following mod-
ifications:
1. Each subset S j ∈ Φ is associated with a local l j ∈ K as well as a key k j . It
holds that k j = f c (l j ).
2. If it happens that S j 1 is the v-th child of S j 0 in a tree F i it holds that
l j 1 = f c (l j 0 ).
3. During the execution of KeyGen only the values l j for which S j is a tree-
root in are selected independently at random from K. The remaining values
determined based on f c as defined in item 2.
4. The secret-key sk u is defined as (J u ,K u ) where J u contains those indices
j that are tree roots in the intersection forest F∩F(u). K u = {k j | j ∈J u }.
5. During decryption a user will need to recover the key of some subset S ∈
F(u). If it happens that S is a tree-root in F ∩ F(u) then u has the key.
Otherwise it can derive it as follows. Denote the path to S from the root
as follows (S j 0 ,S j 1 ,...,S j m = S) for some integer m. Assume that S j i is
the c i -th child of the subset S j i−1 for 1 ≤ i ≤ m. The local l j m assigned
to the subset S can be derived from l j 0 by successive applications of f c (·).
More specifically, l j m = f c m
(f c m−1
... f c c (l j 0 )). Finally the key k j m can be
c
c
computed as f c (l j m ).
Obviously the above methodology will impact the time required to derive
any key that is assigned to a subset that a user belongs to. The compression
technique defined above has a computational overhead that is bounded by the
height of the underlying key-forest. Indeed, in the worst case, any user would
have to compute as many applications of f c as the height of the tallest tree to
 
Search WWH ::




Custom Search