Cryptography Reference
In-Depth Information
5.6 Constructing Probabilistic Schemes
The construction previously described can be applied for the construction of
novel probabilistic schemes. The starting point however is the selection of a
particular deterministic scheme that determines the parameters of the result-
ing scheme. Obviously, by changing the selected scheme, different probabilistic
schemes are obtained. In the next sections we will describe some probabilistic
schemes for the (n;n) and the (2;n) cases starting from two selected de-
terministic schemes. In the first case a simple formula for the probabilistic
factor can be obtained, relating to the pixel expansion of the resulting
scheme, while in the second case, the computation of the parameters results
is more complicated and depends on the selected pixel expansion of the new
scheme.
5.6.1 (n;n)-Threshold Probabilistic Schemes with Any Pixel
Expansion
In this section a (n;n)-threshold probabilistic schemes with any pixel expan-
sion is built, for n 2 starting from deterministic scheme S
D
, which is the
(n;n)-threshold deterministic scheme of Naor and Shamir [16]. S
D
has pixel
expansion m = 2
n1
, and thresholds ` = m 1 and h = m. Moreover, the
scheme consists of a white base matrix containing all vectors with an even
(including 0) number of black subpixels and a black base matrix containing
all vectors with an odd number of black subpixels. For example, for n = 4 the
scheme S
D
is given by:
2
3
2
3
0
1
1
1
0
0
0
1
0
0
0
1
1
1
1
0
4
5
4
5
:
0
1
0
0
1
1
0
1
0
0
1
0
1
1
0
1
M
W
=
M
B
=
0
0
1
0
1
0
1
1
0
1
0
0
1
0
1
1
0
0
0
1
0
1
1
1
1
0
0
0
0
1
1
1
Let S be the (n;n; 0; 0; 1)-VCS obtained applying Lemma 3 to scheme S
D
.
For scheme S we have that the cardinality of the collections C
B
and C
W
is
r = 2
n1
, and that p
bjb
= 1, p
wjb
= 0, p
wjw
= 1=2
n1
, p
bjw
= 1 1=2
n1
.
8
<
2
3
2
3
2
3
2
3
2
3
2
3
2
3
2
3
9
=
0
0
0
0
1
1
0
0
1
0
1
0
1
0
0
1
0
1
1
0
0
1
0
1
0
0
1
1
1
1
1
1
4
5
;
4
5
;
4
5
;
4
5
;
4
5
;
4
5
;
4
5
;
4
5
C
B
=
:
;
Search WWH ::
Custom Search