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.
 
 
Search WWH ::




Custom Search