Cryptography Reference
In-Depth Information
by v
x
. We determine the sequence of leaves that are in S
j
as follows: (i) if R
starts with 1 then S
j
contains the sequence of leaves of the subtree rooted at
v
x
that start with the leftmost leaf and continue up to and including the leaf
encoded by LR. (ii) if R starts with 0 then S
j
contains the sequence of leaves
of the subtree rooted at v
x
that start with the rightmost leaf and continue
towards the left up to and including the leaf encoded by LR.
The encoding that we put forth above is convenient as can be seen from the
following facts. Given j = (L,1R) we can represent the set S
j
in the following
way. Suppose that a = str2int(L0
|R|
) and b = str2int(L1R) then it holds
that S
j
= {a,a + 1,...,b}. On the other hand, if j = (L,0R), suppose that
c = str2int(L0R) and d = str2int(L1
|R|
) then it holds that S
j
= {c,c+1,...,d}.
Observe that the encoding scheme would cover all subsets of Φ
KCT
exactly
once with the only exception being the subsets that consist of the complete
sets of leaves that are rooted at a node in the binary tree. These sets of leaves
will be counted twice. For example, (,0
log n
) and (,1
log n
) are both referring
to the set {1,...,n}. For this reason, for any L with |L| < log n, we will
consider invalid as encoding the pair j = (L,R) with R = b
log n−|L|
where b is
the last bit of L (and say b = 0 if L = ). In this way any S ∈ Φ
KCT
uniquely
corresponds to an encoding j ∈J
KCT
.
To summarize the above for any L,R with |L|+|R|+ 1 = log n we have
S
(L,0R)
= {str2int(L0R),..., str2int(L1
|R|+1
)}
and
S
(L,1R)
= {str2int(L0
|R|+1
),..., str2int(L1R)}
while note that S
(Lb,b
log n−|L|−1
)
and S
(,0
log n
)
are undefined.
The key forest for compression.
Let L ∈{0,1}
x
with 0 ≤ x ≤ log n−2. We define F
L0
(resp. F
L1
) as a chain of
length 2
log n−x−1
−1 which consists of subsets that are of the following form:
a subset is included in chain F
L0
(resp. F
L1
) if it is a consecutive set of leaves
rooted at node v
L0
(resp. v
L1
) including the rightmost (resp. leftmost) leaf
rooted at node v
L0
(resp. v
L1
).
Observe that the leaf encoded by (Lbb
log n−x−1
,) with b =
df
1 − b for
b ∈{0,1} either amounts to the rightmost leaf of the subtree rooted at v
Lb
in
case b = 0 or the leftmost leaf in case b = 1. The chain F
Lb
can be formally
describ
e
d as follows: it contains the leaf that corresponds to the encoding
j = (Lbb
log n−x−1
,), and includes all the nodes in a chain recursivel
y
following
this rule : for any node j
0
in F
Lb
, if it holds that cvr(j
0
,2) 6= (Lb,b
log n−x−1
)
(refer to the Figure
2.17
for the computational key assignment of Key Chain
Tree) the next node (as a child of j
0
) is assigned cvr(j
0
,2), otherwise the chain
ends as it reaches its maximum of length 2
log n−x−1
−1.
In addition, we define F
fl
to be the chain starting from j = (0
log n
,) and
F
fr
be the chain starting from j = (1
log n
,). In such case, the chain covers
the consecutive set of leaves defined for the root of the Figure
2.15
.
