11
$\begingroup$

Back in the day, if you wanted to show an image to a large audience, you would use an overhead projector. This would shine a light through a transparency, which is a clear sheet with a black drawing printed on it, and project the resulting shadows onto a large screen.

enter image description here

You are currently preparing a talk for the NSA, where you need to display some TOP SECRET information using an overhead projector. All of this fits on a single transparency, but you are worried it may fall into the wrong hands. For safety, you instead want to prepare several transparencies so that

  • when all of the transparencies are stacked, they display a legible message, but

  • if an adversary intercepted some, but not all, of the transparencies, they would learn nothing about this message.

How can you do this?

For our purposes, assume a transparency is an array of (quite small) pixels, each of which is black or clear. When several transparencies are stacked, the corresponding pixel on the big screen is black if at least one of the stacked pixels is black. Two black pixels in a stack looks just as dark as three, or any number.

$\endgroup$
  • $\begingroup$ SO are you after the most efficient method of checking pixels with a for loop or something? $\endgroup$ – Daedric May 9 '15 at 1:46
  • $\begingroup$ What do you mean "learn nothing"? Do you mean this in a formal statistical sense, or in a colloquial sense of getting no useful information? $\endgroup$ – xnor May 9 '15 at 3:41
  • $\begingroup$ @xnor In the formal statistical sense. Your method should provide the same security as the one-time pad. $\endgroup$ – Mike Earnest May 9 '15 at 3:49
  • $\begingroup$ @MikeEarnest Then I really don't see how this could be possible. Any black pixel on a transparency guarantees that that pixel is black in the final image. Or are we restricting to some class of possible images? $\endgroup$ – xnor May 9 '15 at 3:51
  • $\begingroup$ @xnor True, you will not be capable of displaying every possible pixel pattern. So, if there are $n$ pixels, you won't be able to display $n$ bits of info. However, all of the info you do display should be perfectly secure, if at least one transparency is not stolen. $\endgroup$ – Mike Earnest May 9 '15 at 3:59
9
$\begingroup$

Note: Taken from here

There is a simple way to do this. For example, if we need to make two such transparencies, we take our original black-and-white picture and for each of its pixels do this:

Our transparencies should have two pixels for each pixel of original image. If this pixel is black, one of transparencies should have black pixel and white pixel like this: ■□ and another like this:□■, assigned randomly to them. When stacked together, this pixel will be completely black. However, if the pixel was white, both should have the same combination: ■□ or □■, again, chosen randomly. The resulting pixel will look grey.

It is obvious that having only one of the transparencies, it is impossible to decode the picture: out of each pair of pixels, one is black and one is white, positioned without any pattern, but combined, they produce the encrypted picture, which will look like this:

enter image description here

Not exactly clear, but quite recognisable, and bigger resolution pictures will look much better.

Furthermore, for any transparency it is possible to create a paired one, which, combined with the first, will produce any picture you want, so there is no way to even guess what was encrypted; each of your transparencies will be absolutely useless and undecryptable without the second one.

This method is called 'Visual encryption' and it is possible to do this with any amount of transparencies. You can read about it here: Visual cryptography

$\endgroup$
  • $\begingroup$ +1 This is a great answer, because it is written in such a way that nearly anyone can understand it. $\endgroup$ – JLee May 9 '15 at 12:23
  • $\begingroup$ This answer would be even better if you provided the pair of images that together make your example. $\endgroup$ – Bob May 9 '15 at 14:03
  • $\begingroup$ Excellent! Simpler than what I had in mind as well, I had a solution with 3 slides. $\endgroup$ – Mike Earnest May 9 '15 at 17:02
2
$\begingroup$

Here is another possible answer, using $3$ slides.

Group the pixels of each slide into $2\times 2$ blocks. Every block of the first slide will look like

##        ..
..   or   ##

where "#" is black, "." is clear. Each block is chosen randomly. Similarly, for the second slide, every block is randomly either

#.        .#
#.   or   .#

Finally the, every block of the last side is chosen deterministically to be either

#.        .#
.#   or   #.

One of the choices will lead to the corresponding block being all black when the three slides are stacked; the other will cause exactly one of the four pixels to be clear. You make the choice based on whether the pixel of the corresponding message is black or clear.

The final image will have $1/4$ the resolution of the original. Since pictures speak louder than words, here is an example of the process. The first row are the original slides, the second are each stacked pair, and the last is when all three are stacked:enter image description here

It certainly appears that you get no information out of any proper subset of the slides. This is provably true. If you have the first two slides, then all you have is randomness. If you have just the last two, then there is no way to tell if a block is black or not, since this will be determined by the random first slide you don't have. Same for if you have the first and last slides.

$\endgroup$
2
$\begingroup$

It suffices to encode a single bit, since then we can copy the protocol on different patches of the overhead to get a multibit message.

Take a region of $2^n$ pixels that we associate with vectors in $V=\mathbb{F}_2^n$. To a vector $v$ in $V$, we associate the transparency whose clear pixels are in the orthogonal subspace to $v$, the locations $x$ with $x\cdot v = 0$. Then, a pixel $x$ appears clear in the overlay of transparencies $v_1, ..., v_n$ exactly if $x\cdot v_i = 0$ for each $i$, or equivalently, if $x$ is in the orthogonal subspace to their span.

Now, we encode the bit by generating uniformly random transparencies subject to either:

  • $v_1, ..., v_n$ are linearly independent
  • $v_1, ..., v_n$ have a single relation of summing to the vector $0$, but are otherwise independent

In the first, they span all of $V$ and so only the $0$-vector location is clear. In the second, they span a subspace of codimension $1$, so a 1D subspace is clear, containing $0$ and a second vector. So, the overlaid transparencies convey a bit that can be seen by an elderly with exponentially good eyesight.

But, someone with a proper subset of the transparencies cannot distinguish two cases because they correspond to a random set of $n-1$ independent vectors of $V$.

$\endgroup$
  • $\begingroup$ Something isn't adding up... I think when you said "black" in your third sentence, you meant clear, and your $\neq$ in the next sentence should be a $=$? Because your second paragraph implies the zero vector is black, while the fourth implies it is clear. $\endgroup$ – Mike Earnest May 9 '15 at 10:26
  • $\begingroup$ As I read answers like this, I wonder if they could be stated so that it makes sense to me (in laymen's terms). Maybe use pictures? $\endgroup$ – JLee May 9 '15 at 12:21
  • $\begingroup$ Post an example to demonstrate this works. $\endgroup$ – Bob May 9 '15 at 13:52
  • $\begingroup$ @MikeEarnest You're right, I mixed up black/clear, fixed it. $\endgroup$ – xnor May 11 '15 at 0:38
-1
$\begingroup$

Here's my idea:

1. Create a transparency that contains the top secret info that you want to display. Let it dry completely so that it won't smear.


2. Create a random pattern of ten 1's, ten 2's, ten 3's, ... up to ten 10's, such as this


enter image description here


3. That pattern will then be tiled (repeated) to fill a another transparency. Let it dry completely so that it won't smear.


4. Put both transparencies (the pattern one on top of the secret info one) on top of each other on the projector. Secure them with small pieces of tape, so that they won't move.


5. Get 10 blank transparencies. Turn on the projector, and use more small pieces of tape to secure one of the blank transparencies on top of the other two. Color all of the #1 pixels on the blank transparency that are on top of ink on the top secret transparency. Mark a tiny dot in the top right of the page so that you know which way to turn the transparency to line it up with the others. Repeat this step for #'s 2 through 10, each number on its own transparency.


6. You now have 10 transparencies that will make your message when you overlay them. Destroy the transparency that has your top secret information.

$\endgroup$
  • $\begingroup$ I think this doesn't quite work: if a villain obtained nine of the transparencies, and stacked them, they would see about 90% of the message. That could allow them to learn quite a lot. $\endgroup$ – Mike Earnest May 9 '15 at 2:00
  • $\begingroup$ Wow, I wonder if there is a way to require having ALL of the transparencies to make any sense of the message. $\endgroup$ – JLee May 9 '15 at 2:02
  • $\begingroup$ There certainly is ;) $\endgroup$ – Mike Earnest May 9 '15 at 2:10
  • $\begingroup$ OK I am curious to see it. I will keep this answer up as a bad example, just in case someone else might want to post something similar. $\endgroup$ – JLee May 9 '15 at 2:27
  • $\begingroup$ @MikeEarnest If I would have used just 2 transparencies instead of 10, then only 50% of the information could have been revealed. That's a huge improvement over 90%. Also, in a silly case, had I used just one transparency, by the rules, 0 of them could be stolen, because they ALL can't be stolen, and therefore, 0% of the information could be leaked. :) $\endgroup$ – JLee May 9 '15 at 11:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.