Cryptography Reference
In-Depth Information
pixel is black the reconstruction in S gives at least h black subpixels, that each
matrix of C
B
(S) has at least h columns, which reconstruct black. Hence, in S
0
we have at least rh columns that reconstruct black. Since jC
B
(S
0
)j = rm we
have that p
bjb
h=m. Obviously this gives p
wjb
(mh)=m. Similarly, we
have p
wjw
(m`)=m and p
bjw
`=m.
Hence, in S
0
we have that p
wjw
p
wjb
h`
m
and p
bjb
p
bjw
h`
m
and
thus we can set =
h
m
. The security property is immediate.
For a canonical scheme it is possible to define the characteristic vectors as:
c
B
= (c
0
B
;c
1
B
;:::;c
B
)
and
c
W
= (c
0
W
;c
1
W
;:::;c
W
)
where c
i
X
is the number of matrices of C
X
that provide a reconstruction,
by any qualified set, of the secret pixel with exactly i black subpixels. The
characteristic vectors are well defined because, by Property 2 of canonical
schemes, each c
i
X
does not depend on the particular qualified set chosen for
reconstructing the secret pixel.
The following lemma complements the results presented above, showing
how it is possible to transform a probabilistic (canonical) scheme into a de-
terministic scheme.
Lemma 5 Let S be a -probabilistic canonical (k;n; 0; 1; 1)-VCS and let c
B
=
(c
0
B
;c
1
B
) and c
W
= (c
0
W
;c
1
W
) be its characteristic vectors. Then, there exists
a deterministic (k;n;`
0
;h
0
;m
0
)-VCS S
0
with `
0
= c
1
W
; h
0
= c
1
B
, m
0
= jC
W
(S)j
and contrast (S
0
) (S).
Proof Let S be a -probabilistic (k;n; 0; 1; 1)-VCS satisfying the hypothesis
of the lemma. Scheme S
0
is constructed by letting its base matrix M
B
(resp.
M
W
) consist of all the vectors of C
B
(S) (resp. C
W
(S)). Fix `
0
= c
1
W
and
h
0
= c
1
B
. We have to prove that S
0
is a deterministic (k;n;`
0
;h
0
;m
0
)-VCS
with m
0
= r, where r = jC
W
(S)j = jC
B
(S)j.
Both C
B
(S) and C
W
(S) contain r matrices of dimension n1; hence, the
dimension of both M
B
and M
W
is nr; thus, m
0
= r.
Since S is a -probabilistic scheme, we have that p
bjb
p
bjw
> 0 hence,
p
bjb
> p
bjw
, and since p
bjb
= c
1
B
=r and p
bjw
= c
1
W
=r, we have c
1
B
> c
1
W
. Thus,
`
0
< h
0
. Now we need prove that the scheme is deterministic. Scheme S
0
is a
basis matrices scheme, so all the matrices of the collections C
W
(S
0
) and C
B
(S
0
)
are equal up to a permutation of the columns; moreover it is easy to see that a
reconstructed black pixel always has h
0
black subpixels and that a reconstructed
white pixel always has `
0
black subpixels. Hence, we have p
0
bjb
= p
0
wjw
= 1 and
p
0
wjb
= p
0
bjw
= 0. Hence, scheme S
0
is deterministic.
Let us consider the security property. Fix a nonqualified set of participants
and consider the corresponding k
0
< k rows of the basis matrices. Each of these
rows can be seen as the concatenation of shares of S (one per each matrix in
Search WWH ::
Custom Search