Cryptography Reference
In-Depth Information
1. Encoding Testing: tst(j); return 1 if j = {0,1}
s
for some s ∈
{0,1..., log n}.
2. Membership Testing: mbr(j,u); if j = or j is a prefix of u, then
return 1.
3. Outside Selection: slo(j
1
, j
2
,..., j
r
); if j
i
= for an i ≤ r return
⊥, otherwise compute the mimimal string s, that does not have
any of j
i
's as a prefix. This can be done quite e
ciently starting
from the most significant bits of the input strings. Then pad the
string s with 0 and 1's arbitrarily to prepare a string u of length
log n; output u.
Inclusion Testing: sbs(j, j
0
); if j
0
4.
is a prefix of j then return 1.
5.
Parent Finding: cvr(j,i); if i 6= 1 then return ⊥. Otherwise,
given that j = j
0
b for b ∈{0,1}, output j
0
.
6.
Split Finding: spt(j); if |j| < log n then return the subset pair
(j0, j1) else return ⊥.
It is straightforward to see that the complete subtree family as defined
above is e
cient.
The key-forest for compression.
The key forest F
CS
used for compression is defined trivially by having trees
of size one, i.e., each node constitutes a tree by itself and thus there is no
compression. Hence, the key-handling procedure of Definition
2.21
would es-
sentially yield a information theoretical key-assignment where each subset is
assigned a unique key randomly and independently. It is not hard to observe
that there is no possible way to derive a better strategy in this case : indeed
any upward looking tree in the complete subtree poset needs to be a single
node.
The factorizability of the complete subtree set system.
We see next that the complete subtree set system satisfies the factorizability
property and thus it inherits the revocation algorithm of Figure
2.9
.
Proposition 2.37. The set system Φ
CS
is a factorizable set system.
Proof. Our proof will take advantage of the alternative characterization for
factorizability, that is the “diamond property” given in definition
2.32
which
is shown to be equivalent with factorizability (see Theorem
2.33
).
Indeed, it is immediate to see that if any two subsets in Φ
CS
are intersect-
ing, then one of them is actually completely containing the other and hence
their union is also in the set system.
Since the Complete Subtree method satisfies the factorizability property
the revocation algorithm given in Figure
2.9
finds the optimal cover.
