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