Friday, February 1, 2008

Shamir's Three Pass Protocol and Kandam Betcha Kottu!

It all started from a Car Talk weekly Puzzler (http://www.cartalk.com/content/puzzler/transcripts/200750/index.html).
Just in case you have trouble going to the website, here is the puzzle:
------------------------------------------------------------------------------------------------- RAY: This came from a fellow named Michael Wortman and it is from my lock and key series, which I just started today. I had to add a few things to make it sufficiently bogus.

Imagine you have a friend who lives in Russia where the KGB spies on everyone and everything and you want to send a valuable object to this friend. So you have a box which is more than large enough to contain the object and you have several locks with keys.

Now this box, I suppose you could call it a strongbox, has a lock ring which is more than large enough to have a padlock attached to it. In fact it's large enough to accommodate several locks. But your friend does not have to the key to any lock that you have. Now you can't send a key in the mail because the KGB will intercept it and they will copy it. And you can't not lock the box, because the object is very valuable. So you have to send it through the mail. You can't hand deliver it. You want to lock it so that your friend can open it, but the KGB can't.

The question is, how would you do it?

-------------------------------------------------------------------------------------------------
I heard it, thought about it a little bit, and decided that I had not heard some important part of the question - or maybe it is something silly. I put the puzzle in front of some of my friends, but none had an answer. But for sure I was interested in the answer, and the answer was so GREAT. I marvelled at the puzzle after I heard the answer - It was the best puzzle I had heard for a long time.
-------------------------------------------------------------------------------------------------
Here is the answer (again copied from cartalk.com):

RAY: So the question is how do you package your valuable objects so that the KGB cannot open it, but your friend can? Now instead of a key, I would have mailed a hacksaw. But in the spirit of the puzzler that wouldn't have been fair.

TOM: Sure.

RAY: You put the valuable thing in the box. You put as many locks as you want on the clasp, making sure you leave room for at least one more.

TOM: Yeah.

RAY: You mail the thing to Russia. Your friend gets it. He doesn't have a key to any of these locks that you put on it. He puts another lock on it for which he has the key. He mails it back to you. You remove all of your locks and you can't get it open now. But you don't have to.

TOM: He can.

RAY: When you mail it back to him.

TOM: Oh.
-------------------------------------------------------------------------------------------------
I found out later that this is a well known puzzle and is known in the field of secure communications as "Shamir's three pass protocol".

Now that I was so impressed by the puzzle, I started posing it to everybody I talked to - and, surely, I posed it to my parents on one of the calls home. After posing the puzzle, puzzling them for some time, and then giving the answer, my father goes:

"bEndaatha chOdyangalonnum chOdikkaathE bedakke!"
(for non-mallus: it means "Do not ask un-necessary questions" with a Muslim accent)

And then follows a song:

thalayum kaatti nadannaalE,
peNNungalkkuLLoru haalu
theeyaaluLLoru makkana ittu
nadakkaNam avarude gathikEdu

mudi narEzhaayi keeReeTTu,
neriya paalam kETTeeTTu,
athile nadakkaNam ennalE,
parENathu marichu chenniTTu.

adiyilu kathaNa theeyaNu,
theeyilu kothaNa paampaaNu,

This it seems is from Basheer's "Kandam Betcha Kottu". A grandpa is singing this to his grand-daughter explaining the plight of Muslim women who do not wear the veil (for non-mallus: It basicaly says that they will have to walk on a bridge made of hair hanging above a fire). In the course of the song the girl gets a doubt - Wouldn't the hair burn because of the fire underneath?

The grandpa's response goes:
"bEndaatha chOdyangalonnum chOdikkaathE bedakke!"

I always liked Basheer's writing - have to try to get the book if possible. I could not get the full lyrics after extensive Googling ...

By the way, I tried transliterating the Malayalam above at http://www.google.com/transliterate/indic/Malayalam. It does not do composite words properly ...

ciao ...
any corrections welcome ...