Here is a fun (but not particularly useful) variant of 2-out-of-2 secret-sharing. Visual secret sharing is a secret-sharing technique where the secret and both shares are black-and-white images. We require the same security property as traditional secret-sharing — that is, a single share (image) by itself reveals no information about the secret (image). What makes visual secret sharing different is that we require the reconstruction procedure to be done visually.
More specifically, we imagine each share to be printed on transparent sheets. When the two shares are stacked on top of each other, the secret image is revealed visually. We will discuss a simple visual secret sharing scheme that is inspired by the following observations:
Importantly, when stacking shares on top of each other in the first two cases, the result is a \(2 \times 2\) block that is half-black, half white (let’s call it “gray”); while in the other cases the result is completely black.
So the idea is to process each pixel of the source image independently, and to encode each pixel as a \(2 \times 2\) block of pixels in each of the shares. A white pixel should be shared in a way that the two shares stack to form a “gray” \(2 \times 2\) block, while a black pixel is shared in a way that results in a black \(2 \times 2\) block.
It is not hard to see that share \(s_1\) leaks no information about the secret image \(m\), because it consists of uniformly chosen \(2 \times 2\) blocks. In the exercises you are asked to prove that \(s_2\) also individually leaks nothing about the secret image.
Note that whenever the source pixel is white, the two shares have identical \(2\times 2\) blocks (so that when stacked, they make a “gray” block). Whenever a source pixel is black, the two shares have opposite blocks, so stack to make a black block.