Conflict in Communication Networks
September 2, 2010, 1:51 pm
Filed under: Uncategorized | Tags: , , ,

Imagine that Alice wants to send a message to Bob, and that Carol wants to prevent this. Assume there is a communication channel between Alice and Bob, but that Carol is periodically able to block this channel. Further, it costs Alice $a dollars each time she sends on the channel, Bob $b dollars each time he listens on the channel, and Carol $c dollars each time she blocks the channel. If Alice, Bob and Carol all play this game optimally, how much more will Carol need to spend than Alice and Bob in order to block the message?

This problem abstracts many types of conflict on information networks including: web censorship by nation-states, denial of service attacks on the Internet, and jamming  attacks on wireless networks, where the costs to Alice, Bob and Carol can represent expenditure of both computational and human resources. The problem allows us to quantitatively ask: Does information really “want” to be free?

In a new result, Max Young, Valerie King and I answer this question in the affirmative by showing that under optimal play, it is significantly harder for Carol to block the message than for Alice to communicate it to Bob. Specifically, if a,b and c are fixed constants, and Carol spends $X dollars to try to block the message, then Alice and Bob need spend only proportional to $X^{phi – 1} or about $X^{.62} dollars to transmit the message, where phi = (1+ sqrt(5))/2 is the golden ratio. Surprisingly, this result holds even if Alice and Bob do not know the value X, and there are no cryptographic assumptions.


1 Comment so far
Leave a comment

[…] on a Communication Channel.  This is a paper that I had previously blogged about here.  I’m still very excited about the idea of maintaining security invariants while spending […]

Pingback by PODC 2011 « Machinations

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 )

Twitter picture

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

Facebook photo

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

Google+ photo

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

Connecting to %s

%d bloggers like this: