Cryptography Reference
In-Depth Information
The following lemma is similar to the analogous result proved in Section
2.1 of [1] for deterministic schemes.
Lemma 1 Given a -probabilistic (k;n;`;h;m)-VCS S, there exists a -
probabilistic (k;n;`;h;m)-VCS S
0
such that jC
W
(S
0
)j = jC
B
(S
0
)j.
Proof Fix a -probabilistic (k;n;`;h;m)-VCS S, let r
1
= jC
W
(S)j and r
2
=
jC
B
(S)j and assume that r
1
6= r
2
(otherwise we can choose S
0
= S and we
are done). Let r = r
1
r
2
and construct S
0
by letting C
W
(S
0
) (resp. C
B
(S
0
))
consists of all the matrices of C
W
(S) (resp. C
B
(S)) each one repeated r
2
(resp.
r
1
) times. It is obvious that jC
W
(S
0
)j = jC
B
(S
0
)j = r.
Since we have only repeated matrices of the collections C it is easy to see
that k;n, and m remain the same. Keeping the same ` and h also stays the
same: indeed C
W
(S
0
) is obtained by replicating the same number of times each
matrix of C
W
(S) and thus the probabilities p
wjw
(Q) and p
bjw
(Q) do not change
for any Q and similarly for p
wjb
(Q) and p
bjb
(Q) since C
B
(S
0
) is obtained by
replicating the same number of times each matrix of C
B
(S).
The following lemma shows that schemes can be built where the number
of black subpixels in a reconstructed pixel does not depend on the particular
qualified set of participants chosen to reconstruct the secret pixel and the
characteristic parameters remain the same.
Lemma 2 Given a -probabilistic (k;n;`;h;m)-VCS S, there exists a -
probabilistic (k;n;`;h;m)-VCS S
0
such that for any two qualified sets Q
1
and
Q
2
of participants, we have that p
xjy
(Q
1
) = p
xjy
(Q
2
), for x 2 fw;bg and
y 2fw;bg.
Proof Fix a -probabilistic (k;n;`;h;m)-VCS S. Consider rst C
W
(S) and
assume that the desired property does not hold. Then we build a new scheme
S
0
where C
W
(S
0
) is obtained from C
W
(S) in the following way: for each matrix
M of C
W
(S) insert into C
W
(S
0
) all the matrices that we can build from M by
permuting in all possible n! ways its rows. The collection C
B
(S
0
) is obtained
in the same way from C
B
(S).
Let Q
1
and Q
2
be two qualified sets. We have that C
Q
W
(S
0
) = C
Q
W
(S
0
);
indeed, by construction both sets contain, for any qualified set Q, all the ma-
trices in C
W
(S), with the same multiplicity (the multiplicity is due to the fact
that when restricting the attention to the rows in Q, the other n k rows
can be taken in any order). Hence, we have that p
wjw
(Q
1
) = p
wjw
(Q
2
), and
p
bjw
(Q
1
) = p
bjw
(Q
2
). For the same reason we have C
Q
B
(S
0
) = C
Q
B
(S
0
) and
thus p
bjb
(Q
1
) = p
bjb
(Q
2
), and p
wjb
(Q
1
) = p
wjb
(Q
2
).
By Lemmas 1 and 2, it follows that considering only canonical schemes is
without loss of generality, because for any scheme S an equivalent canonical
scheme S
0
having the same characteristic parameters of scheme S can be
provided.
Search WWH ::
Custom Search