wu :: forums (http://www.ocf.berkeley.edu/~wwu/cgi-bin/yabb/YaBB.cgi) riddles >> cs >> SUPER-VILLAIN TRANSPARENCIES (Message started by: Aaron on Aug 15th, 2002, 11:59am)

Title: SUPER-VILLAIN TRANSPARENCIES
Post by Aaron on Aug 15th, 2002, 11:59am
I'd intuitively think the answer is to split the image into several layers so that only when all the transparencies are stacked on each other will you see the completely page.

Since the problem does not limit the number of page used, the more layers you split your page into, the less imformation each peice of transparency contains.

What I don't get is why this question is under the "cs" catagory.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 15th, 2002, 12:40pm
"they won't learn even the tiniest bit of information"
Just putting little bits and pieces of the image on different slides makes the information loss smaller, but it doesn't eliminate it.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by zameericle on Aug 16th, 2002, 3:24am
perhaps split the slide up to 3 slides: A, B, C

A contains the real information encased within noisy codes.
B + C make up the key needed to filter the noisy codes thus allowing you to read A perfectly.

Thus is the enemy gets A & B they still can't read the slide nor could they if they get A & C.  B & C is just the key so no information is lost there.

close?

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by S. Owen on Aug 16th, 2002, 7:11am
He draws a black-and-white bitmap of his plans - to make it easy consider this a string of bits, really, called P.

He constructs three slides: slide A contains a random string of bits of the same length as P (i.e., a black-and-white noise bitmap image). Same for B. But slide C is A xor B xor P.

P = A xor B xor C, but each slide or pair of slides is indistinguishable from random bits.

Maybe he can write in some kind of funky "xor" ink such that all three laid on top of one another produces the original image on an overhead projector.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 16th, 2002, 10:50am
You don't really need special ink. If you use small pixels you'll wind up with the black image on a gray background instead of white but it works quite well.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Aaron on Aug 17th, 2002, 1:55pm
Hmm... how about just split the information into several peices of transparency, then produce several equally none-sensical looking peices, or transparencies that combine to other useless info... and put them into one shuffled pile?

Without knowning which ones combine to the real information, 2 randomly select transparency is unlikely to generate any useful information.

Security by obscurity works.  :D

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 20th, 2002, 4:16pm

on 08/16/02 at 10:50:05, AlexH wrote:
 You don't really need special ink. If you use small pixels you'll wind up with the black image on a gray background instead of white but it works quite well.

What happens when the random data come together to create a new black pixel?  Without the XOR ink, it seems that there is a chance for your message to be corrupted.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 21st, 2002, 12:43am
The random data creates a background noise, but to a viewer a field of random black and white dots turns into just  a grey background if you have small pixels,  leaving your black image easily readable.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 21st, 2002, 11:34am

on 08/21/02 at 00:43:51, AlexH wrote:
 The random data creates a background noise, but to a viewer a field of random black and white dots turns into just  a grey background if you have small pixels,  leaving your black image easily readable.

Yes, I understand the concept, but my question is, "what happens when the random dots cluster together to form, say, a character?"  It doesn't even have to be a whole character:  adding a small line can change an O to a Q, or a 6 could be turned into an 8.

Information is not lost only if the attacker has no means to distinguish the random dots from actual data.  In this respect, your suggestion works.  However, the other property necessary is that the original viewer must be able to distinguish the random dots from actual data.  The XOR scheme does this by providing the "ignore this noise" bits on the other slides.  With an OR scheme, though, there is no such guarantee, and the receiver might not be able to recover the original.

The only way I can see the random-dot approach working is to actively prevent the random dots from clustering in the absense of data:  that is, where one desires "white" (or "gray", I suppose), one must prevent the random dots from being "black" across all transparancies at that location.  But this gives the attacker "information" (in the information-theoretic sense):  observing that the pixel is empty across the captured slides, the attacker can conclude the pixel must be "white" (or "gray").

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 21st, 2002, 6:10pm
In the practical application which is asked for this is not an issue. With small pixels and the large letters one uses on a transparency, the odds of randomly getting artifacts that obscure or change letters is tiny. If you wanted to take this to a more general realm, then you could use special fonts and include error correction information and make the probabilities as small as you like.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Mr_Superstar on Aug 22nd, 2002, 1:53pm
Because the problem said "several" slides and not a specific amount, I would use 5. Then I would mimic a RAID 5 array onto the slides. If I remember correctly, in a 5 disk RAID 5 array, you can loose 2 disks, and still keep the array. However, if you loose 3, meaning only 2 are still good, your data is lost.

Therefore, the superhero would be able to capture 2 slides and learn nothing.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by S. Owen on Aug 22nd, 2002, 2:05pm
"RAID 5 slides" ensures that the villain still has his plans even if two slides are captured, but it does not ensure that zero information is revealed to the superhero that captures the slides.

The way RAID 5 spreads data and parity bits around, the superhero would gain some information (not necessarily enough by itself to reconstruct the plans though).

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 22nd, 2002, 4:27pm

on 08/21/02 at 18:10:40, AlexH wrote:
 In the practical application which is asked for this is not an issue. With small pixels and the large letters one uses on a transparency, the odds of randomly getting artifacts that obscure or change letters is tiny. If you wanted to take this to a more general realm, then you could use special fonts and include error correction information and make the probabilities as small as you like.

To be honest, this answer seems just as dissatisfying as the "just split the original into N slides" answer:  one can make the information gained by the attacker arbitrarily small, in that case, as well.

And when you put it that way, I'm not sure there isn't absolutely zero information obtained by the attacker under your scheme.  The bits received by the attacker are not purely random:  they are biased, based on the information from the original image.  These biases should be worth at least a few bits of information gained by the attacker.

If you don't believe this, then consider the potential threat of the attacker relative to the number of slides you use:  would you feel safe only using four or five slides?  I could easily imagine the attacker taking two of five slides and finding a reasonable fuzzy image of the original.  But then what makes 20 slides (or whatever) a magic number, where the information lost to the attacker suddenly becomes zero?  I posit that the information loss only decreases, but never actually reaches zero.

If your analysis is correct, it does not seem far off to modify it to come up with a secure alternative to the one-time pad, which is impossible.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 22nd, 2002, 4:42pm
Or let me put it another way:  suppose the attacker can steal K of your slides.  How many slides must you spread your information across for you to protect it?

Suppose one can truly limit the information loss to 0.  Let the minimal number of slides necessary be N.  Then, if you use N-1 slides, the attacker gains information somehow.  Why is there suddenly information gained by the attacker if you use one fewer slide?

N is clearly some function of K.  What is this function?

My point is this:  there does not seem to be any reasonable answer to these questions under your scheme, which suggests that there is no "breakpoint" for N, where your scheme suddenly becomes 100% secure.  As a result, one must conclude that the security only approaches 100%, but does not reach it completely.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 22nd, 2002, 6:35pm
The principle at work here is that of k-wise independent random variables. There really is absolutely 0 information loss unless the opponent gets all your slides. In the default way of creating the slides, all but 1 of the slides is actually purely random bits, and the remaining slide looks like random bits unless you have the information from all the rest of the slides. There is no probability of your opponent getting any information whatsoever. The probability (which you can make as small as you like) to which I was referring was the probability of having errors in your information once the slides are assembled.

The minimal threshold to gain information is k+1 where you're using k-wise independent random variables. This is whatever threshold you choose to set. You can use 2 slides and be secure against  1 loss, or choose 100 slides and be secure against 99.  Once you get large numbers of slides however you have a real problem with the background becoming too dark; this is why I choose 2 in the problem statement as the number of slides you have to protect against losing.

If you categorize this as an alternative to OTP, then there are plenty of perfectly secure alternatives to the one-time pad. I would call it more of a neat variation of the ideas of the OTP.

Quote:
 would you feel safe only using four or five slides?  I could easily imagine the attacker taking two of five slides and finding a reasonable fuzzy image of the original.  But then what makes 20 slides (or whatever) a magic number, where the information lost to the attacker suddenly becomes zero?  I posit that the information loss only decreases, but never actually reaches zero.

I would feel perfectly safe using just 2 slides if I was sure that at most one of them could be lost.

Look at the 2 slide case if you're still doubting. The 2 slides are <random bitstring slide> and <image XOR slide 1>. So if you only get 1 slide you either get the OTP key or you get the OTP encrypted message, but not both. Either one alone is completely independent of the message. Consider how this generalizes to more slides.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 22nd, 2002, 8:06pm

on 08/22/02 at 18:35:25, AlexH wrote:
 I would feel perfectly safe using just 2 slides if I was sure that at most one of them could be lost. Look at the 2 slide case if you're still doubting. The 2 slides are and . So if you only get 1 slide you either get the OTP key or you get the OTP encrypted message, but not both. Either one alone is completely independent of the message. Consider how this generalizes to more slides.

I thought the whole point is that it's not XOR ink we have.  We only have OR ink (or, I suppose, more technically, arithmetic PLUS ink, given how transparancies work).  If you were to try to decompose a message in OR or PLUS ink, you would have the following cases:

- white pixel in original:  at least one of the slides must have a white pixel in the same location
- black pixel in original:  both slides must be black in the same location

This is assuming one is willing to live with the transformation white -> gray in the result.

This generalizes to more than two slides:  for a pixel to appear "dark" in the final result, its location must be "dark" across a majority of the slides.

As a result, the attacker gains information from whichever slides he steals.  In the two-slide case, the observation that a pixel is white on a stolen slide means that the corresponding pixel on the original must have been white.  For N slides, the attacker gains probabilistic information about the original, which is still information.

OTP with XOR works because even if the attacker observes a white pixel in the stolen slide, there is no way to determine what the original was, since XOR is not monotonic:  the final result of combining the slides can go either way.  However, OR (or arithmetic PLUS) is monotonic:  the stolen slides allow the attacker to eliminate certain possibilities, and thus yields information.

I have zero qualms about your proposal, if you were to allow XOR ink.  In the absence of XOR (or any other non-monotonic function), though, there are information leakage problems with your technique.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 22nd, 2002, 8:20pm

on 08/22/02 at 18:35:25, AlexH wrote:
 If you categorize this as an alternative to OTP, then there are plenty of perfectly secure alternatives to the one-time pad. I would call it more of a neat variation of the ideas of the OTP.

BTW, I'd like to hear about these secure alternatives to OTP.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 22nd, 2002, 9:43pm

on 08/22/02 at 20:06:01, Yournamehere wrote:
 I thought the whole point is that it's not XOR ink we have.  We only have OR ink (or, I suppose, more technically, arithmetic PLUS ink, given how transparancies work).  If you were to try to decompose a message in OR or PLUS ink, you would have the following cases:- white pixel in original:  at least one of the slides must have a white pixel in the same location- black pixel in original:  both slides must be black in the same locationThis is assuming one is willing to live with the transformation white -> gray in the result.

No. Both of those statements are false. You are confused as to the generation method. Consider the 2 slide case for simplicity. Use 0 for clear and 1 for dark and let M be the bitstring representing the pixels of your original image.  Slide 1 is pixels representing a random bitstring (call it X). Slide 2 is M XOR X. When we put both slides together we get X OR (M XOR X) = X OR M. This means we get dark wherever we had dark in our original slide and we get a 50/50 chance of light at each pixel where we had light in our original image.

Slide 1 obviously doesn't contain any information about our message  because it is a random bitstring. Slide 2 contains X XOR M ... in otherwords it contains M encrypted with a OTP X. If you don't know X, this contains 0 information about M. I'm not sure how to make this any clearer.

There are much more advanced results in this area, the simplest of which is a method for 2 slides which is still perfectly secure and also guarantees no errors in the final product. In the 2 slide case, each pixel maps to a pair of adjacent pixels. Let A be 2 pixels (dark,light) and ~A be the pair (light, dark). If your message bit is light, then with p=.5 put A on both slides, and with p=.5 put ~A on both slides. If your message bit is dark,  then with p=.5 put ~A on slide 1 and A on slide 2 and with p=.5 put A on slide 1 and ~A on slide 2.

Note that the original method does have perfect secrecy, but it is not very efficient because it relies on using many pixels trtansmitted per piece of information which you wish to transmit. This pixel pair method has better efficiency and the idea can be extended to more advanced problems including thresholds. The area is called visual cryptography and was effectively started by Naor and Shamir in 94.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Yournamehere on Aug 22nd, 2002, 11:45pm

on 08/22/02 at 21:43:57, AlexH wrote:
 Note that the original method does have perfect secrecy, but it is not very efficient because it relies on using many pixels trtansmitted per piece of information which you wish to transmit.

I think this finally clarified everything.  In your past messages, you used the term "using small pixels".  You were not referring to the use of small pixels for the original image, but rather were referring to the fact that the pixels of the slides would have to be smaller than the original image pixels (or, equivalently, that the density of the pixels would have to increase).  I had taken the "use small pixels" to apply uniformly, including applying to the original picture, when in fact one must keep those pixels large.

on 08/22/02 at 21:43:57, AlexH wrote:
 There are much more advanced results in this area, the simplest of which is a method for 2 slides which is still perfectly secure and also guarantees no errors in the final product. In the 2 slide case, each pixel maps to a pair of adjacent pixels. Let A be 2 pixels (dark,light) and ~A be the pair (light, dark). If your message bit is light, then with p=.5 put A on both slides, and with p=.5 put ~A on both slides. If your message bit is dark,  then with p=.5 put ~A on slide 1 and on slide 2 and with p=.5 put A on slide 1 and ~A on slide 2.

Is this really secure?  Theft of slide 2 seems to reveal half of the light pixels (where the A's are).

Sorry for dragging the discussion on for so long.  You're probably tired of all the explanations to an idiot like me.   :-[

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by AlexH on Aug 23rd, 2002, 10:12am
Good  :D I knew we were miscommunicating somewhere but I wasn't sure where.

Erm. There was a typo in my description of the more advanced method. The last sentence "If your message bit is dark,  then with p=.5 put ~A on slide 1 and on slide 2...", the last few words there should have been "and A on slide 2...". I'll go up and fix it.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Drake on Aug 27th, 2002, 4:40pm

Quote:
 If I remember correctly, in a 5 disk RAID 5 array, you can loose 2 disks, and still keep the array. However, if you loose 3, meaning only 2 are still good, your data is lost.

I hate to be picky, but with RAID 5 you can lose only 1 disk per set and be able to recover.  On a 5 disk set you would have 4 blocks with data, and one with the parity info.

See http://www.anandtech.com/guides/viewfaq.html?i=110 for a list of all RAID types.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by rmsgrey on Apr 23rd, 2003, 11:24pm
Maybe I'm missing something, but it seems to me that in the 2 slide (lose 1) case you have the following possibilities (using Y for the pixel on the second slide and Z for the 'stacked' pixel):

M  X  Y  Z
0   0  0  0
0   1  1  2
1   0  1  1
1   1  0  1

Meaning that with half density ink and uniform pixel size across the original and the encrypted slides, you can produce the message in grey on a black/white random background... OK, with sufficiently small pixel size you get grey on a grey background, but for visible pixels, this is better than the other method and allows all the data to be recovered

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Papa Homer on Apr 25th, 2003, 3:30pm
Let's make it a little more interesting.  Let's say that you prepared N slides in such a way that anyone that sees any K or fewer slides does not learn anything about your plan.  Now you realize that hiding your plan from others is not enough, you want to be able to view it yourself and show it off to the superhero before unleashing the very mean seabass with laser beams on their heads.  So, the new constraint is still to be able to display the presentation with any K+1 slides.  There is a very elegant solution to this problem in crypto but I am not sure how cleanly it will translate to transparencies.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by rmsgrey on May 27th, 2003, 4:03am
Just to annoy people, XOR ink is perfectly possible - provided you're willing to invest a little extra into your equipment and assuming sufficiently consistent thickness of ink layer - just have your "ink" made of an appropriate optically active compound such that it rotates the plane of polarised light by 90 degrees in the thickness of the ink - by applying parallel polarisation filters above and below the stack of slides, you get an XOR effect. Of course, getting the right degree of optical activity is an exercise left to the reader... (LCD displays on pocket calculators use a similar trick but with the degree of polarisation determined by electrical current)

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by gruff on May 14th, 2007, 7:02am
I would use three slides and three pen colours red, green and blue.  Wherever red, green and blue ink coincide the screen will be black(ish).  Fill the rest of the space with random lines/letters.  Any two slides will show gibberish, you need all three to bring out the message.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Khal on Oct 16th, 2008, 12:49pm
That almost works. Sine the transparencies are a subtractive color process, you need pens that are cyan, magenta, and yellow (rather than red, green, and blue).

With RGB pens you would get a black pixel on the screen where any two of them overlapped and you only want black where all three overlap.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by Big_Mike on Oct 2nd, 2013, 2:37pm
Assuming darkness is additive (2 black pixels on top of each other is twice as dark as just 1), I think that S. Owen's method surprisingly does not allow you to see the image when the transparencies are layered.

His idea, in order to show image P, was to have A and B be slides made of random pixels, and C = A xor B xor P. Then the darkness A, B and C layed on top of each other will be 1 or 3 when P has a black pixel, and 0 or 2 when P does not. There are 4 equally likely ways for A+B+C to be odd: letting 1 be black and 0 clear, these are

100, 010, 001, 111

In the first 3 cases, we have a darkness of 1, and the last a darkness of 3, so the average darkness in the region where P is back will be (3/4)*1 + (1/4)*3 = 1.5. This means that when the mind blurs together the pixels, it will see this region as one uniform color, of darkness halfway between 1 and 2.

Similarly, the average darkness in the region where P is clear will be (1/4)*0 + (3/4)*2 = 1.5. But this means that when the transparencies are layered, we will see the same color everywhere on the slide, so we can't recover the information P had!

My argument depends on these two assumptions.

1. Darkness is additive (maybe two black pixels on top of each other would only make a pixel which we would perceive as 1.5 times as dark).

2. Our perceived darkness of a bunch of pixels is there average darkness (maybe its the darkness that occurs most, or something else weird.).

Neither of these, I think, are intuitively true or false; they can only be verified by studying how the human eye/brain works. If this is only supposed to be a CS puzzle, it shouldn't require this kind of knowledge to come up with a solution, so hopefully there is a another answer. I've tried generalizing this method to n slides, where A1, A2, . . . An-1 are all random, and the last slide is the xor of all of these with with desired slide, but at least for n up to 5, the same thing happens! :P

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by dantruong on Apr 22nd, 2014, 1:47am
I also contributed some comments with you.
Follow me because the problem said "several" slides and not a specific amount, I would use 5. Then I would mimic a RAID 5 array onto the slides. If I remember correctly, in a 5 disk RAID 5 array, you can loose 2 disks, and still keep the array.
However, if you loose 3, meaning only 2 are still good, your data is lost.

Title: Re: SUPER-VILLAIN TRANSPARENCIES
Post by dudiobugtron on Jun 19th, 2014, 7:29pm
Here is a(nother?) solution to this puzzle.

Note that the CMY solution won't work, because you will know that a pixel should be non-black whenever two slides share the same colour for a particular pixel.

My solution is to use 5 slides, each with either a grey or empty pixel (as for previous solutions).  The black pixels in the original image will be grey on exactly 3 slides, and the white pixels on the original will be grey on exactly 2 slides.  This way the black pixels will show up as darker (3 greys vs 2) when the slides are overlapped.  But, if you have any two slides, the fact that they have a grey or non-grey pixel in a particular location will tell you nothing.

You need 5 slides, since with 3 or 4 slides, you would be able to tell whether some pixels were black or white on the original. (If, say, you got two slides which shared a non-grey pixel, then you know the original must be white (or two grey pixels would mean the answer must be black).)

This extends to a general solution pretty obviously (n = 2k + 1), providing a nice upper bound.  Note that you may need to use a different number instead of 1 if you wish the shade-difference to be more discernable.