Cryptography Reference
In-Depth Information
Fig. 2.19. The transformation of definition 2.52 (note that the illustration does
not include the connections described in step number 7).
requirement of the X−property of the set system Φ). We will show that the
filters of the same subsets are the required filters we need to demonstrate their
existence of for the set system Φ 0 . It is easy to see that F(S 1 ) and F(S 2 ) within
the new set system Φ 0 are full binary trees of height 2m− 1. This is true as
for each v ∈ M, the node C v ∈ Φ b was connected (see the 5-th step of the
transformation) to two full binary trees of height m−1; it follows that F(S 1 )
and F(S 2 ) within Φ 0 are binary trees of height m−1 + 1 + m−1 = 2m−1.
2. For any index u ∈M 0 , there exists an integer v ∈{1,...,2 m } so that u ∈
M v . Since Φ v satisfies the X−property, there is a unique path {u v ,...,u m− v }
not including the atom u that is intersecting with the either the filter F Φ v
or F Φ v . Since those filters that are structurally upward full binary trees are
copied (refer to the second step of transformation) to the head of the resulting
set system we can discover an isomorphic copy of this path that we denote by
{u v∗ ,...,u v∗ }. Note that by definition the subsets corresponding to u v∗ for
i = 1,...,m exclude the atom u.
Recall now that v ∈ M, hence there exists a unique path within one of
the two filters of the body set system Φ. The subsets corresponding to the
nodes over this path do not contain the node v which is atomic in the body
while it is the leading subset of the lower level set system Φ v . Hence, this path
does not contain the receiver indexed by u ∈ M 0 . Moreover, the path ends
 
Search WWH ::




Custom Search