Spy Control Problem - Peter Winkler
Source: Video of a course in Algorithms on Udacity - Asked by Prof. Peter Winkler
Problem:
A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way.
Well, surprisingly, she can actually do that.
Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I'm a spy in enemy territory. Fortunately, there is a radio broadcast tower in enemy territory, and everyday it sends out a 15-bit message. There's an example of a 15-bit message. Now, I can use that message to communicate with my boss, but I can't just change it arbitrarily to something completely different, because then people will know that something weird has happened. But I can flip just 1 bit. I can zap the message and change just one of the bits, and my boss then is going to hear that, and we'd like him to actually interpret that as the message that I want to send. How should I do that such that, when the boss receives the broadcast, he is like - Hmm...based on the 15-bit broadcast I'm hearing, and the protocol that my spy and I arranged in advance, I know that the message he is sending to me is 0110. Nice work, agent P.
Peter Winkler's video with Problem and Solution:
Update:
Peter Winkler gave the solution in the video. Wrote the solution in comments!
Problem:
A spy in an enemy territory is trying to convey information to her control, but the only means she has for conveying information is that there is a 15-bit radio broadcast every morning, and she has the ability if she wishes to alter 1 bit of that broadcast. But she doesn't know in advance what the broadcast will be. So, this is a case where, potentially, there are 16 different things she can do. There are 15 bits she can alter, or she can choose not to alter any bit, which means that in theory perhaps she could convey as many as 4 bits of information this way.
Well, surprisingly, she can actually do that.
Repeating the problem to make sure that we understand the setup here. So, I'm a spy, and I'm in enemy territory, and I've got a message --0110-- that I need to transmit to my boss. Now, that's going to be tricky to do, because I don't want anybody to know that I'm a spy in enemy territory. Fortunately, there is a radio broadcast tower in enemy territory, and everyday it sends out a 15-bit message. There's an example of a 15-bit message. Now, I can use that message to communicate with my boss, but I can't just change it arbitrarily to something completely different, because then people will know that something weird has happened. But I can flip just 1 bit. I can zap the message and change just one of the bits, and my boss then is going to hear that, and we'd like him to actually interpret that as the message that I want to send. How should I do that such that, when the boss receives the broadcast, he is like - Hmm...based on the 15-bit broadcast I'm hearing, and the protocol that my spy and I arranged in advance, I know that the message he is sending to me is 0110. Nice work, agent P.
Peter Winkler's video with Problem and Solution:
Update:
Peter Winkler gave the solution in the video. Wrote the solution in comments!
I checked the solution. It is like a secret key.the receiver and sender share a code which is ex-ored with the missing place holder's binary value. But my brute force approach would be check the 15 digit code and change the one bit which u want to send in binary. Like if u want to send 0011 then flip the value of 3rd bit and send it across.I agree that this is not a secure method and it can be tapped. But just a thought. The approach he used reminds me of CDMA.
ReplyDeletebut how would the handler know that the third bit has been flipped when you want to send 1111??
DeleteEncryption Algorithm:
ReplyDeleteTo be sent message x (a 4 bit number)
Broadcast message (a 16 bit number)
Cipher Text = Broadcast message xor (A 16 bit number with 0s at all places but 1 at one place) such that (Sum of all the positions where cipher text is 1 mod 16 = x)
Decryption Algorithm:
Take positions of 1 in the message broadcast. Take sum of all these numbers. Do mod 16 on the number. Represent the result in binary format. You get the message back.
Is it always possible? If my number is 1111010000010100 (sum of the positions is 70), mow I want to transmit 0 (I can't do it by flipping only one bit).
ReplyDelete