That 70's Crypto Show (Remailers, science and engineering)

[dmolnar]

On Thu, 28 Dec 2000, Tim May wrote:

> I hear the focus of Mojo Nation is shifting from "better living 
> through piracy," to something more mundane involving deals to deliver 
> video content. If so, much of the motivation to be absolutely robust 
> will go away. Sad, if true.

So maybe it takes away the incentive for the original Mojo folks. So? That
may actually be a good thing, if it gets the technology spread far and
wide so that other people can produce an absolutely robust Mojo++ which
rides on top of Mojo. Plus it raises the profile of these kinds of
services.

Today's teenager reading about Mojo on slashdot (or wherever) is going to
be tomorrow's data haven architect...

> I think Bill was a bit harsh. There are some _economic_ issues 
> involved, as usual. So long as the "value of what is being sent 
> through remailers" is LESS THAN "the cost of subverting remailers," 
> they will tend not to be subverted.

Yes, BUT
I think one of the reasons why a maximally powerful adversary model is so
appealing, however, is that it sidesteps the question of evaluating "value
of what is being sent through remailers." If you can prove security
against a maximally powerful adversary, then you don't have to answer that
question - no matter how much it's worth to the adversary, it won't win.
If you take this tack, then you seem to start worrying about what the
adversary wants -- and as Terry Ritter often points out on
sci.crypt, you don't know much about your adversary. Plus putting a
"value" on what is sent through remailers seems to require that you be
sensitive to the way the system is used after it's designed.

This is *not* to discourage an economic analysis, but to point out a
potential benefit to the "modern" approach. It wouldn't be much of a
benefit, EXCEPT that in encryption and digital signatures, we have
actually been able to achieve security against maximal adversaries (or at
least probabilistic polytime ones assuming some problems are hard).

> 
> But crypto is really more of an N-party game, with Alice and Bob (and 
> maybe others) making moves and countermoves. (This is one reason many 
> such games are in an important sense "harder" than being merely 
> NP-complete.)

Hmm. I know of some results on some two-player games which shows that
playing them "optimally" is PSPACE-complete. The two I can think of,
however - Hex and Go - are perfect information games. I'm not sure how
hiding information changes things.


Maybe one way to cast crypto as a game would be to consider protocol
verification. "Here's a state machine. Here's Alice's state. Here's Bob's
state. Can an eavesdropper learn their shared key if he has the following
moves...?"


 > (* A standard assumption--it probably has a name that I have 
> forgotten--is that the attacker of a cipher has complete knowledge 
> except for the key. That is, he can take the cipher back to his lab 

Kerchoff's principle, I think. 

-David