Cryptography Reference
In-Depth Information
Computational Specification of Key Chain Tree in the KP Framework.
1. Encoding Testing: tst(j); Let the encoding j be (L,R) such that |LR| = log n.
Denote the last bit of L by b ∈ {0,1}, define b = 0 if L = . If R = b
log n−|L|
and |x| < log n then return 0 otherwise return 1.
2. Membership Testing: mbr(j,u); Let j be a valid encoding (L,bR) such that
|LbR| = log n, b ∈{0,1} and u ∈{0,1}
log n
. Return 1 if and only if str2int(u) ∈
S
j
.
3. Outside Selection: slo(j
1
, j
2
,..., j
r
). Choose the smallest integer that lies outside
the set S
j
1
∪...∪S
j
r
and if no such integer exists return ⊥.
4. Inclusion Testing: sbs(j, j
0
); return 1 if and only if S
j
⊆ S
j
0
.
5. Parent Finding: cvr(j,i), where 1 ≤ i ≤ cvm = 2.
• i = 1: L
e
t j be encoded by (L,bR) such th
at
|LbR| = log
n
and b ∈{0,1}. If
L = L
0
bb
x
for some L
0
,x, then return (L
0
,bb
x
bR). Recall b =
df
1−b. Return
⊥ if j is not of the form required.
• i = 2: If j = (Lbb
0
,), then return (Lb,b).
Otherwise, let j be encoded by (L,bR) such that |LbR| = log n and b ∈{0,1}:
(i) b = 0; if str2int(bR) > 2 then return (L,bR
0
) such th
at
str2int(bR
0
) =
str2int(bR) − 1, otherwise if str2int(bR) = 2, return (L
0
a,a
log n−|L|
) where
L = L
0
a for some a ∈ {0,1} ( return ⊥ in case L = ), otherwise if
str2int(bR) = 1, we have that bR = 0
log n−|L|
(and hence by the validity
of encoding it holds that L = L
0
1) return (L
0
,01
log n−|L|
).
(ii) b = 1; if str2int(bR) < 2
|bR|
− 1 then return (L,bR
0
) such that
str2in
t(
bR
0
) = str2int(bR) + 1, otherwise if str2int(bR) = 2
|bR|
− 1, return
(L
0
a,a
log n−|L|
) where L = L
0
a for some a ∈{0,1} (return (,1
log n
) in case
L = ), otherwise if str2int(bR) = 2
|bR|
, we have bR = 1
log n−|L|
(and hence
by the validity of encoding it holds that either L = L
0
0 or L = ) return
(L
0
,10
log n−|L|
) if |L| > 0 and ⊥ otherwise.
6. Split Finding: spt(j); There are two cases:
(i) Let j be encoded by (L,0R) such that |L0R| = log n. Suppose R = 1
x
0R
0
,
then output {(L01
x
,0R
0
), (L1,0
|R|
)}.
(ii) Let j be encoded by (L,1R) such that |L1R| = log n. Suppose R = 0
x
1R
0
,
then output {(L10
x
,1R
0
), (L0,1
|R|
)}.
Fig. 2.17. The computational specification of the key chain tree set system in the
Key-Poset framework.
As an illustration, let us write the chains for the key forest of a key chain
tree with 8 users given in Figure
2.16
, i.e. the case log n = 3.
