Cryptography Reference
In-Depth Information
Computational Specification of Subset Difference in the KP Framework.
1. Encoding Testing: tst(j); if j = return 1, otherwise parse j as ({0,1}
x
,{0,1}
y
).
If x + y ≤ log n provided that y ≥ 1, then return 1.
2. Membership Testing: mbr(j,u); let j = (L,R) and u ∈{0,1}
log n
. if L is a prefix
of u whereas LR is not, then return 1.
3. Outside Selection: slo(j
1
, j
2
,..., j
r
); if j
i
= for any i ≤ r then return ⊥. Let
j
i
= (L
i
,R
i
) for i = 1,...,r. We have two possible cases:
(i) {s ∈{0,1}
log n
|∃i ∈ [r],R s.t. s = L
i
R}6= {0,1}
log n
; this case implies that
there exists a u ∈{0,1}
log n
such that none of L
i
's are prefix of u; in this case
return u. This string can be determined easily by computing the tree connecting
the nodes corresponding to strings L
i
.
(ii) {s ∈{0,1}
log n
|∃i ∈ [r] s.t. s = L
i
R} = {0,1}
log n
; observe that for any u
that is selected outside the subsets encoded by {j
1
,..., j
r
}, it holds that if L
i
is
a prefix of u for any i ≤ r then L
i
R
i
is also a prefix of u. We will compute such
u, if it exists, in the following way: for all i = 1,...,r, set p = L
i
R
i
and test
whether it holds that for all j 6= i, either L
j
R
j
is a prefix of p or L
j
is not a
prefix of p. If such an i is found, p = L
i
R
i
is padded arbitrarily to length log n
to obtain a string u and return it. Otherwise return ⊥.
4. Inclusion Testing: sbs(j, j
0
); Let j = (L,R), j
0
= (L
0
,R
0
), if L
0
is not prefix of L
then return 0. We have two possible cases:
(i) L is a prefix of L
0
R
0
: if LR is also prefix of L
0
R
0
return 1, otherwise return
0.
(ii) L is not prefix of L
0
R
0
: if L
0
R
0
is prefix of L then return 0; else return 1.
5. Parent Finding: cvr(j,i); We define for i = 1,2,3,4 = cvm.
i = 1: if j is defined such that j = (Lb,R), where b ∈ {0,1} and |L| ≥ 0, then
return (L,bR); otherwise return ⊥.
i = 2: if j is defined such that j = (L,R), where |LR| < log n, then return
(L,R0); otherwise return ⊥
i = 3: if j is defined such that j = (L,R), where |LR| < log n, then return
(L,R1); otherwise return ⊥
i = 4: if j is de
fin
ed such that j = (Lb,R), where b ∈{0,1} and |LbR| = log n,
then return (L,b); otherwise return ⊥
6. Split Finding: spt(j); if j is defined such that j = (L,bR), where b ∈ {0,1}
and |R| > 0, then ret
u
rn {(L,b), (Lb,R)}; otherwise if R = then return
{(Lb,0), (Lb,1)} where b = 1−b.
Fig. 2.13. The computational specification of subset difference set system in the
Key-Poset framework.