Cryptography Reference
In-Depth Information
F
00
= (001,) : {2}
F
01
= (010,) : {3}
F
10
= (101,) : {6}
F
11
= (110,) : {7}
F
0
= (011,) → (01,0) → (0,01) : {4}→{4,3}→{4,3,2}
F
1
= (100,) → (10,1) → (1,10) : {5}→{5,6}→{5,6,7}
F
fl
= (000,) → (00,1) → (0,10) → (0,11) : {1}→{1,2}→{1,2,3}
→ (,100) → (,101) → (,110) → (,111) →{1,...,4}→ ... →{1,...,8}
F
fr
= (111,) → (11,0) → (1,01) → (1,00)
: {8}→{7,8}→{6,7,8}
→ (,011) → (,010) → (,001)
→{5,...,8}→ ... →{2,...,8}
Proposition 2.45. The set F
KCT
= {F
s
| s ∈ {fl,fr,{0,1}
x
},x = 0,...,
log(n−2)} is a key-forest of the set system Φ
KCT
with degree 2.
Proof. Due to the definition of the sets F
Lb
it is easy to observe that the
key-forest consists of “upward” looking trees in the poset, i.e. it holds that a
parent of a node is a subset of that node.
Consider now a subset j = (L,bR) for any b ∈{0,1} where |LbR| = log n.
We have two cases: (i) L = ; if b = 0 then S
j
exists in the chain F
fr
, if b = 1
then S
j
exists in the chain F
f
l
.
(ii) Suppose that L = L
0
b
x
for some x ≥ 0 so that L
0
is either or ends
with b. In case L
0
= holds, it is easy to see that the subset exists in the
chain F
fr
if b = 0 and it exists in the chain F
fl
otherwise. We next claim that
if L
0
6= , this subset belongs to the chain F
L
0
and not in any other chain. To
prove the claim, we recall the following two facts:
• F
L
0
is a chain that starts with a leaf encoded by (L
0
b
log n−|L
0
|
,) and grows
one-by-one until all leaves are covered (except one) located in the subtree
rooted at v
L
0
in the following direction: (i) if b = 0 then from right to
left, starting from (L
0
1
log n−|L
0
|
,) adding leaves whose string-indices rep-
resent smaller numbers. (ii) if b = 1 then from left to right, starting from
(L
0
0
log n−|L
0
|
,) adding leaves whose string-indices represent larger num-
bers.
• Recall that j = (L,bR) is an encoding of a subset S
j
= {c,c + 1,...,d}
where (i) if b = 0 then c = str2int(LbR) and d = str2int(L1
log n−|L|
) =
str2int(L
0
1
log n−|L
0
|
).
(ii) if b = 1 then c = str2int(L0
log n−|L|
) = str2int(L
0
0
log n−|L
0
|
) and d =
str2int(LbR).
Hence, we obtain the fact that the subset encoded as j = (L,bR) is con-
tained in the tree F
L
0
. Furthermore it can be easily verified that any other
chain cannot contain j. The degree of the key-forest is 2 since the key-forest
consists of chains.
Since the above key-forest has a degree of two, we can apply the key-
assignment of Definition
2.21
by employing a 2-fold key extender f
2
: K 7→ K
2
.
