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
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
.