Cryptography Reference
In-Depth Information
Definition 2.26. Given the family Φ = {S j } j∈J and j 1 ,..., j m ∈J, we define
the new family Chop(Φ,{j 1 ,..., j m }) = Φ\∪ i=1 F(S j i ); the specification of its
six algorithms is given in Figure 2.7 .
Chop (Subset Collection Φ , list of encodings {j 1 ,..., j m })
1.
set cvm = Φ.cvm
2.
return descriptions of (tst,mbr,slo,sbs,cvr,spt) as follows:
Ctst(s)
1.
if (Φ.tst(s)=1)
2.
if (Φ.sbs(j 1 ,s) = 1∨...∨Φ.sbs(j m ,s) = 1)
3.
return 0
4.
else return 1
5.
else 0
Cmbr(s,u)
1.
return Φ.mbr(s,u)
Cslo(s 1 ,...,s r )
1.
Let U = {u 1 ,...,u t } such that u ∈ U if and only if
u is an atom and there is some 1 ≤ i ≤ k, such that S j i = {u} .
2.
return Φ.slo(s 1 ,...,s r ,u 1 ,...,u t )
Csbs(s,s 0 )
1.
return Φ.sbs(s,s 0 )
Ccvr(s,i)
1. s 0 = Φ.cvr(s,i)
2.
if (Ctst(s 0 ) = 1)
then output s 0
3.
4.
else return ⊥
Cspt(s)
1.
return Φ.spt(s)
Fig. 2.7. The computational description of a chopped family Φ.
It is easy to verify that the transformation pointed above from the family Φ
to Φ 0 can be done in polynomial-time. Moreover if it happens that S j 1 ,...,S j m
are atoms, i.e., S j i = {u i } for some u i ∈ [n] for each i = 1,...,m, it is easy
to see that Φ 0 is fully exclusive over [n] \R where R is equal to {u 1 ,...,u m }.
Consider now an instance hΦ, [n],Ri of the Revocation problem; note first
that the optimal solution would be covering the set [n] \ R. Note also that
any subset in the optimal solution is also an element of the subset collection
Φ 0 = Φ\{S ∈ Φ | S∩R 6= ∅}. Thus, the optimal solution is an optimal solution
for the instance hΦ 0 , [n] \Ri of PatternCover for the chopped collection Φ 0 .
 
 
 
Search WWH ::




Custom Search