Bad Santa
August 8, 2009, 8:25 pm
Filed under: Uncategorized | Tags: , ,

Imagine you are a child pitted in a battle of wits against a malevolent Santa Claus.  Santa has lined up 1,000 boxes on a table and has stipulated that you must consider each box, in the order they are lined up, exactly once and must either choose to open that box or pass on it to never return to it again.  Santa has hidden presents in half of the boxes and tells you that you must play the game until you find a present and that further, you must play the game in such a way that you are guaranteed to find a present.  Now here’s the terrible part, and if there are any kids in the room, you may want to send them out while you read this: every time you open a box, you receive a mild electric shock.

So your problem is to design an algorithm for opening the boxes that 1) always finds a present; and 2) opens the smallest number of expected boxes.  Think you need to open 501 boxes?  Think again!  32 boxes are actually possible in expectation.  And no, it’s not as simple as opening a random sample of boxes of log size, because remember your algorithm must always find a prize.

Now comes the part in my blog where I need to justify the government paying me money to think up these twisted stories.  Well this problem is actually related to robust communication in sensor networks.  The boxes represent time steps; opening a box corresponds to listening on a channel in a given time step; a box with a present corresponds to a time step in which someone has sent a message; and the shocks represent power expenditure for being awake in a give step.  And the bad Santa?  Well that’s just a story we use to scare undergrads.

If you’re interested in the solution to this problem and some variants, take a look at our paper Sleeping on the Job: Energy-Efficient and Robust Broadcast for Radio Networks from PODC ’08.

Addendum: The reason I find this problem interesting is not because of the sensor network application or even because of the cute puzzle.  Rather the problem gives rise to an interesting model for security based on attacker-defender games. For example, a big goal of cryptography is to allow a defender to spend a polynomial time budget to defend the privacy of a message against an attacker that spends an exponential time budget.  One implication of the above “bad santa” result that we’re currently working on is allowing a defender to spend a bandwidth budget of x to defend against a denial of service attack from an attacker spending a budget of x^2.  I really think these types or games  are the way we need to be thinking about security in general. More on this later.

4 Comments so far
Leave a comment

I haven’t read your paper, but this feels like it might be related to Merkle puzzles. These are cryptographic key-generation techniques (I hope that’s the right term) that have information-theoretic security of the type you talk about: if the players invest n units of effort, the adversary needs to invest Omega(n^2) units. This was recently shown to be optimal by Barak and Mahmoody-Ghidary.

I don’t know the bibliography on Merkle puzzles, but you can find information in the paper of Barak and Mahmoody-Ghidary, “Merkle Puzzles are Optimal – an O(n^2) attack on key exchange from a random oracle”, here:

Click to access merkle.pdf

Comment by elad

Thanks! – I’ll definitely check out this paper. I’m glad to see that the crypto community has studied such a attack/defend model for providing information theoretic security. I am pretty surprised that they get the same n vs n^2 tradeoff that we do, especially given that we are considering a very different problem: power consumption in sensor networks. Probably, the similarity comes about because both of us are making use of the birthday paradox.

Comment by Jared

Aha, yes. the quadratic behavior in Merkle comes from the birthday paradox. I wonder if you can reduce one of the problems to another. Barak et al worked very hard recently to prove that one cannot do better than n^2. Maybe you can use this result to easily derive optimality for your result?

(Again, I haven’t read it yet, so maybe this is an irrelevant question).

Comment by elad

hmm – in our paper we do show asymptotic optimality for our result using Yao’s Lemma. The proof is a bit tricky but is only about a page or two, so it sounds like showing optimality for our problem is easier than what Barak et al. showed for Merkle.

Comment by Jared

Leave a Reply

Fill in your details below or click an icon to log in: Logo

You are commenting using your account. Log Out /  Change )

Google photo

You are commenting using your Google account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

%d bloggers like this: