Cryptography Reference
In-Depth Information
(i) On transmission overhead of the transforma-
tion:
For any leaf u
0
∈ XTrans(Φ) there exists a leaf v
0
in the body which is
replaced with the set system Φ
v
0
that satisfies (v
0
−1)2
m
+ 1 ≤ u
0
≤ v
0
·2
m
.
Denote the leading subset of Φ
v
0
by (v
0
). First recall that the subset C
v
0
u
0
=
df
(v
0
)\{u
0
} exists in the set system Φ
v
0
located in the feet of the transformation.
We have three cases depending on the location of S
0
∈XTrans(Φ):
1. S
0
is located on the head: it holds that S
0
is in a binary tree extending
C
v
∈ Φ for some v ∈ {1,...,2
m
}, recall that we define C
v
= M\{v} and S
0
is corresponded to a subset in Φ
v
; we will denote its corresponding subset by
S
0∗
. We have two subcases:
(i) if v = v
0
: Consider now the lower-maximal partition hI
1
,..., I
o
i of (S
0∗
) ∩
P
u
0
within the set system Φ
v
0
(here P
u
0
is the complement of the atomic
filter u
0
in key-poset Φ
v
0
); due to the factorizability of the set system and
the theorem's statement it holds that the lower maximal partition satisfies
o ≤ t(m). Consider now the intersection (S
0
) ∩ P
u
0
within the set system
XTrans(Φ); it will hold that the users of (S
0
) ∩ P
u
0
can be covered in the
worst case by C
v
∪(∪
j=1
I
j
) (it might be possible that C
v
∪I
j
exists in the new
set system for some j something that would give an even smaller cover). In
any case, ord((S
0
) ∩P
v
0
) ≤ t(m) + 1.
(ii) if v 6= v
0
: The users of the set (S
0
) ∩ P
u
0
can be covered by the sets
S
0∗
∪C
v
0
u
0
as well as the users in the intersection (C
v
∩P
v
0
); note that the latter
intersection is taken within the body of the transformation. Hence, in any case
the cover of (S
0
)∩P
u
0
will number at most ord((S
0
)∩P
u
0
) ≤ t(m) +2 subsets.
2. S
0
is located in the body: Provided that u
0
∈ S
0
(otherwise the intersec-
tion is S
0
itself), it holds that v
0
∈ S
0
within the set system Φ and hence it
holds that the users of (S
0
)∩P
u
0
can be covered by C
v
0
u
0
∪(S
0
∩P
v
0
) where the
latter intersection is taken within the body of the transformation. It follows
that ord((S
0
) ∩P
u
0
) ≤ t(m) + 1.
3. S
0
is located on the feet of the transformation: Suppose S
0
is located in
the set system Φ
v
for some v ∈ {1,...,2
m
}. If v 6= v
0
then the intersection
is of the ideal (S
0
) and the complement of the atomic filter F(u
0
) would be
(S
0
) itself. Otherwise S
0
is located within the set system with u
0
for which the
intersection yields a lower maximal partition of order less than or equal to
t(m) due to the factorizability of the set system Φ.
(ii) Dealing with the body and feet part of the transformation is relatively
easy. We will employ the key assignment technique of the basic set system for
the set system of the body Φ as well as Φ
1
,Φ
2
,...,Φ
2
m
used in the transfor-
mation. Observe that the user would need to store exactly 2· s(m) keys (one
set of keys for the component Φ
i
it belongs to and one set of keys for Φ) and in
order to derive any key in the head and body part would require computation
overhead bounded by c(m).
With respect to the subsets located on the head of the transformation no
extra keys would be needed. We will use the structure of the binary trees and
the computational key compression method of described in definition
2.21
.
