Cryptography Reference
In-Depth Information
expressed in terms of 3 ORs and 4 NOTs as follows:
s
i
s
j
= OR( OR(s
i
;s
j
);OR(s
i
;s
j
) );
then, the computation of each pairwise XOR can be performed by using a
Boolean circuit, having a depth 4, constituted only by OR and NOT gates.
Therefore, the computation of s
1
s
k
can be performed by a Boolean
circuit having a depth 4dlog ke.
In the corresponding VCS with reversing, for each pixel of the original
image, the dealer runs the distribution phase of the BSS, and, for each partic-
ipant i, generates on the transparency ti
i
the pixel corresponding to the share
s
i
distributed by the BSS. In order to reconstruct the secret image, the k
participants are involved in a computation consisting of stacking and revers-
ing their transparencies, simulating the circuit computing the XOR, which is
composed only by OR and NOT gates. It is easy to see that the number of
reversing and stacking operations needed to reconstruct the secret image is
equal to 4(k 1) and 3(k 1), respectively.
Example 4 Let k = 4. If the dealer wants to share a white pixel, he runs
the distribution phase of the BSS for the secret s = 0. Hence, he randomly
chooses three bits s
1
, s
2
, and s
3
, and computes s
4
= s s
1
s
2
s
3
. For
example, let s
1
= 1, s
2
= 0, s
3
= 0, then s
4
= 1. The corresponding pixels
in the transparencies t
1
;t
2
;t
3
;t
4
are equal to 1; 0; 0; 1, respectively. In order
to reconstruct the secret pixel, the participants have to simulate the compu-
tation of s
1
s
2
s
3
s
4
by performing a sequence of stacking and revers-
ing operations on their transparencies. Notice t
hat s = s
1
s
2
s
3
s
4
=
(s
1
s
2
) (s
3
s
4
). Sinc
e a = s
1
s
2
= OR(
OR(s
1
;s
2
);OR(s
1
;s
2
) ) = 1
and b = s
3
s
4
= OR( OR(s
3
;s
4
);OR(s
3
;s
4
) ) = 1, it follows that the
four participants
can reconstruct the
secret pixel corresponding to the secret
s = ab = OR( OR(a;b);OR(a;b) ) = 0 by performing 12 reversing opera-
tions and 9 stacking operations.
9.4.2 Constructions Using Perfect Black VCSs
In this section we describe different constructions using as a building block
a perfect black VCS. In particular, the solution described in
Section 9.4.2.1
requires each participant to store m transparencies, where m denotes the pixel
expansion of the underlying perfect black VCS, and offers no loss of resolution.
The scheme described in
Section 9.4.2.2
still offers no loss of resolution, but
requires each participant to hold two transparencies having a large size, i.e.,
reduces the number of transparencies stored by each participant to mh+ 1,
but there is a loss of resolution on the reconstructed image.
Search WWH ::
Custom Search