Cryptography Reference
In-Depth Information
Set System Description in the KP Framework
Let J
KCT
be the set of encodings of subsets in the set system Φ
KCT
defined
over a set [n] = {1,...,n}. An element in J
KCT
is a pair of binary strings
so that the sum of their length is equal to log n. The algorithms, mostly,
will be based on the integer representation of the encoding, hence we de-
note the procedure to convert a string into an integer by str2int; specifically
str2int(b
k
...b
0
) = 1 +
P
i=0
2
i
·b
i
. We also use the inverse function int2str.
As mentioned already, for the sake of simplicity, we assume that log n is an
integer.
Regardless of the description of the set system, we can picture the key-
secutive lists of users present in the set system as the long chains of nodes;
especially observe the left and right sides of the triangle-looking key poset.
Fig. 2.16. (left) the key-poset of the key-chain tree method for 8 users. (right) the
recursive definition of the key-poset for the key-chain tree for 2n users.
We define an index for each node in the binary tree in a top-down manner
similar to the indexing of the complete subtree method: the root of the binary
tree is encoded by (the empty string) and subsequently the index of a left
child is constructed by appending '0' to its parent's index while the index
of a right child is constructed by appending '1' to its parent's index. We
denote the node corresponding to the string z by v
z
for any z ∈{0,1}
i
such
that 0 ≤ i ≤ log n. An encoding j ∈J
KCT
is a pair of strings j = (L,R) with
|L|+|R| = log n. The value L is the encoding of the root of the subtree that S
j
is contained, i.e. the least common ancestor of all leaves in S
j
will be the node
v
L
. In case L = then the least common ancestor of the leaves of the subset is
the root of the binary tree; in case |L| = log n then the subset contains a single
leaf corresponding to the encoding L. In case 0 < |L| < log n, observe that
the value R is of the suitable length to identify a leaf in the subtree rooted
