Author |
Topic: SUPER-VILLAIN TRANSPARENCIES (Read 18066 times) |
|
Aaron
Newbie
Gender: 
Posts: 14
|
 |
SUPER-VILLAIN TRANSPARENCIES
« on: Aug 15th, 2002, 11:59am » |
 Quote  Modify
|
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.
|
|
 IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #1 on: Aug 15th, 2002, 12:40pm » |
Quote Modify
|
"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.
|
|
IP Logged |
|
|
|
zameericle
Newbie
Posts: 8
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #2 on: Aug 16th, 2002, 3:24am » |
Quote Modify
|
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?
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #3 on: Aug 16th, 2002, 7:11am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #4 on: Aug 16th, 2002, 10:50am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Aaron
Newbie
Gender:
Posts: 14
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #5 on: Aug 17th, 2002, 1:55pm » |
Quote Modify
|
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. 
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #6 on: Aug 20th, 2002, 4:16pm » |
Quote Modify
 Remove
|
on Aug 16th, 2002, 10:50am, 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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #7 on: Aug 21st, 2002, 12:43am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #8 on: Aug 21st, 2002, 11:34am » |
Quote Modify
Remove
|
on Aug 21st, 2002, 12:43am, 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").
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #9 on: Aug 21st, 2002, 6:10pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Mr_Superstar
Newbie
Posts: 2
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #10 on: Aug 22nd, 2002, 1:53pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
S. Owen
Full Member
Gender:
Posts: 221
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #11 on: Aug 22nd, 2002, 2:05pm » |
Quote Modify
|
"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).
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #12 on: Aug 22nd, 2002, 4:27pm » |
Quote Modify
Remove
|
on Aug 21st, 2002, 6:10pm, 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.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #13 on: Aug 22nd, 2002, 4:42pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #14 on: Aug 22nd, 2002, 6:35pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #15 on: Aug 22nd, 2002, 8:06pm » |
Quote Modify
Remove
|
on Aug 22nd, 2002, 6:35pm, 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 <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. |
|
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.
|
|
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #16 on: Aug 22nd, 2002, 8:20pm » |
Quote Modify
Remove
|
on Aug 22nd, 2002, 6:35pm, 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.
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #17 on: Aug 22nd, 2002, 9:43pm » |
Quote Modify
|
on Aug 22nd, 2002, 8:06pm, 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 location
This 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.
Edited to add:
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.
|
| « Last Edit: Aug 23rd, 2002, 10:13am by AlexH » |
IP Logged |
|
|
|
Yournamehere
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #18 on: Aug 22nd, 2002, 11:45pm » |
Quote Modify
Remove
|
on Aug 22nd, 2002, 9:43pm, 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 Aug 22nd, 2002, 9:43pm, 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. 
|
|
IP Logged |
|
|
|
AlexH
Full Member
Posts: 156
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #19 on: Aug 23rd, 2002, 10:12am » |
Quote Modify
|
Good 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.
|
|
IP Logged |
|
|
|
Drake
Newbie
Gender:
Posts: 7
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #20 on: Aug 27th, 2002, 4:40pm » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
   
Gender:
Posts: 2872
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #21 on: Apr 23rd, 2003, 11:24pm » |
Quote Modify
|
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
|
|
IP Logged |
|
|
|
Papa Homer
Guest
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #22 on: Apr 25th, 2003, 3:30pm » |
Quote Modify
Remove
|
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.
|
|
IP Logged |
|
|
|
rmsgrey
Uberpuzzler
Gender:
Posts: 2872
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #23 on: May 27th, 2003, 4:03am » |
Quote Modify
|
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)
|
|
IP Logged |
|
|
|
gruff
Newbie
Posts: 5
|
|
Re: SUPER-VILLAIN TRANSPARENCIES
« Reply #24 on: May 14th, 2007, 7:02am » |
Quote Modify
|
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.
|
|
IP Logged |
|
|
|
|
RIDDLES SITE
WRITE MATH!
Home 
Help 
Search 
Members 
Login 
Register
Reply
Notify of replies
Send Topic
Print