Saturday, April 23, 2011

You need to check that your friend, Bob, has your correct phone number…Google Puzzle

You need to check that your friend, Bob, has your correct phone number…

but you cannot ask him directly. You must write the question on a card which and give it to Eve who will take the card to Bob and return the answer to you. What must you write on the card, besides the question, to ensure Bob can encode the message so that Eve cannot read your phone number?


Solution Started From Funniest Way to Deepest Thing of Computer Science

Funny Solutions

it is funny with all these technologies nowadays, I would opt for following as answer for 2.

Write on paper question ....."Bob Can you verify if you have my correct number without revealing to Eve and without talking to me in any of following methods?

1. E-mail me at abc@xyz.com

2. MMS me to my phone number that "If I get this MMS, then Bob has my correct number"

3. Go to my internet website account (facebook) OR even linked.com and write me a message for what number you have

4. Use communicator chat software or gtalk or yahoo messenger and ping me the number that you have

5. mathematically compute like checksum or decode and send me coded number with decoding steps. on paper back to Eve.


Computer Science Way of Thinking

Public key Cryptography
here is my public key, pls encrypt my phone you have with it and send back to me.
key=num-reveres of num

e.g if my no is 9740852296
the key=2818271817 eve can't read it as eva dopn't have my number so she can't predict & she has to lot of computation which only possible she know my number or some its digits ..so she can't decode the my key

(we can also extend the explanation so i write on the paper that bob i am sending you key to decode it reverse the key & then decode using logic you have so the same thing bob has to do in its side & same he write back to me..m not using this in this solution )

then bob decode it using computation he tries all the way +,-*,/, %,xor all possible way to decode if he has my correct phone number then suppose he try to subtract my key from my phone number he has so if has correct phone number then after subtracting the key from my number he will send 9740852296-2818271817=6922580476 & he also write that after decoding reverse it so i will get my original number e.g. 9740852296 so i can say bob has my correct phone number else it would have been some other value & after reversing it i wont get my exact no so i can say bob don't have my correct number..


Hurray i think i have done..Please Correct me if i am wrong

More Depth This Solution provide by Ankul

Click here



Ask Bob to Hash the phone number using a string hashing technique :
T[256] = permutation of 0...255
H[0] = 0
H[i] = T[ H[i-1] xor C[i] ]
H[n] is the final hash value

Since this hash function gives different hash values for permutations of same string, so a hash collision will not occur when two strings are permutation of each other.

This is a one-way hash function and cannot be decrypted back to the original phone number.

When I will get the hash key from Bob, I will find the hash value for my actual phone number and then match it with the hash key given by Bob.

Now, if hash values don't match, Bob has wrong phone number of mine.
Otherwise, there can be two cases :

1. He has correct phone number.
2. He has incorrect phone number but still gives same hash value (collision).

To decide between these two cases, I can ask Bob to also send me the frequency of each digit in the number that he has. This way, I will be able to decide if the two numbers are permutations of each other or not. If, the frequency of any of the digit in my actual number doesn't matches with the frequency given by him, that means the 2nd case is applicable, otherwise 1st case (phone numbers match) because a permutation of same string cannot give same hash value for this hash function.

Thus, I will ask Bob to send me the hash value and the frequency of each digit in his phone number. Eve has no way to find the phone number.

Cheers
WgpShashank