Cryptography Reference
In-Depth Information
Transmission Overhead
Recall from the theorem
2.36
that the transmission overhead depends on the
order of the lower maximal partition of an intersection (S) ∩ P
u
. The set
system Φ
KCT
satisfies the following:
Proposition 2.47. For any subset S ∈ Φ
KCT
and an atom u, it holds that
ord((S) ∩P
u
) ≤ 3.
Proof. First we give some intuition: any subset S encoded as j = (L,bR)
corresponds to a consecutive sequence of leaves and will be splitted into two
parts after removing a complement of an atomic filter P
u
. One of the parts
will contain the end leaf of the subset S, i.e., the leaf (LbR,), while the other
part can be described as a union of two subsets in the set system. Totally, the
ideal (S) will end-up with at most 3 ideals after removing the complement of
an atomic filter. Let us see next a more detailed analysis of this.
Let S have an encoding j = (L,bR), if mbr(j,u) = 0, then the intersection
(S)∩P
u
itself equals to the ideal (S), hence the proposition holds. If not, then
L would be a prefix of u. We have two cases: either (i) Lb is a prefix of u or (ii)
Lb is not a prefix of u. In both of these cases, we will construct disjoint subsets
j
1
, j
2
, j
3
that are covering all the atoms in the intersection (S)∩P
u
, further it
will be easy to observe that these subsets can not grow further, i.e. cvr(j
0
,i)
would either contain u or goes outside the range of (S) for j
0
∈{j
1
, j
2
, j
3
} and
i = 1,2.
(i) In this case it holds that the leaves corresponding to u and (LbR,)
are on the same half of the subtree rooted at v
L
. Denote the longest common
prefix of the string that encodes u and LbR by LbP where P ∈ {0,1}
x
for
some x ≥ 0. Given that u belongs to (L,bR) it will hold that LbPb is prefix
of u while LbPb is prefix of LbR.
Suppose first that b = 1. Provided that u is not the leftmost leaf in
the subtree rooted at v
L
, the subset S
j
1
= {str2int(s
1
),...,u − 1} (with
s
1
= L0
log n−|L|
) contains all leaves located on the left of the leaf corre-
sponding to u. To cover the remaining leaves we define the subsets S
j
2
=
{str2int(s
2
),..., str2int(L1R)} where s
2
= L1P10
log n−|LP|−2
) and S
j
3
=
{u + 1,..., str2int(s
3
)} where s
3
= L1P01
log n−|LP|−2
. It is easy to verify
that the subsets are not intersecting, they are members of the set systems
and cover all leaves of (L,bR) except u. Note that it is possible that some of
these subsets are empty; in such case there less than three subsets are needed
to cover the leaves.
The case b = 0 is symmetric. Provided that u is not the rightmost leaf
in the subtree rooted at v
L
, the subset S
j
1
equal to {u + 1, str2int(s
1
)}
where s
1
= L1
log n−|L|
, contains all leaves located on the right of the
leaf encoded by u. To cover the remaining leaves we define the subsets
S
j
2
= {str2int(L0R),... str2int(s
2
)} where s
2
= L0P01
log n−|LP|−2
and S
j
3
=
{str2int(s
3
),...,u−1} where s
3
= L0P10
log n−|LP|−2
. As before it is easy to
verify that these subsets are disjoint and cover all leaves of (L,bR) except u.
