That 70's Crypto Show (Re: Dude! It's wired!)

[dmolnar]

On Mon, 25 Dec 2000, Tim May wrote:

> Some of the foundations are, of course, "mature"...and not very 
> exciting. The core of mathematical crypto is hardly frontier 
> mathematics. (Yeah, I suppose Dave and Eric and a few others could 
> make a case that there's some connection with the proof of Fermat's 
> Last Theorem, stuff about elliptic functions, etc. But we all know 

I don't think I'd go that far. As far as I'm concerned, elliptic curves
are just another group to do Diffie-Hellman & friends in. What I'd call
the "core" of mathematical crypto is the work that Goldreich, Goldwasser,
Micali, et. al. have been doing over the past fifteen years -- trying to
rough out just what kind of assumptions are necessary and sufficient to
give us the kind of cryptography we want.

That being said, almost none of it works without those pesky one-way
functions. or trapdoor one-way functions. and we have too few examples of
either. 

> that such connections are tenuous. Most of crypto still is built 
> around good old number theory, basically what has been known for 
> dozens of years, even centuries. Euler would not have had a problem 
> understanding RSA.)

That's true, and in some sense it's a good thing - we have some confidence
that these problems are hard because "Euler worked on them." (On the other
hand, Euler didn't have the ability to experiment today's mathematicians
do). In another sense, it's a bad thing, because the number of one-way
functions we have is so small. To say nothing of trapdoor one-way
functions...

> 
> The "far out" stuff of reputations, multi-player games, digital 
> money, etc., is much less-grounded in theory. More interdisciplinary, 
> more "fuzzy," more prone to hand-waving. Doesn't mean this this isn't 
> the interesting area, just means it's not as "foundational" as math 
> areas are. Reductionists who seek the rigor of a pure science often 
> end up throwing out what's interesting.

So I have noticed. (and so I have to caution myself against every day).


> By academic coverage I mean researchers studying weaknesses in 
> various kinds of data havens, digital currencies, reputation systems, 
> etc., in the same way that the "Crypto Conference" folks looked at 
> various ciphers. (And specific digital currency systems, for example.)

Reminds me of the reaction I got when I asked some friends about
doing a term project on mix-nets.
"So, has there been any recent academic work on this?" 

There's some hope. There was a workshop on "Design Issues in Anonymity and
Unobservability" this past summer which brought people together to talk
about these issues. The Info Hiding Workshops are still going strong.
With luck, this year's IHW may have a paper on reputations in it...

This year's ACM CCS conference had two papers of special interest. 
The "Hordes" paper, _A protocol for anonymous communication over the
Internet_ by Clay Shields and Brian Neil Levine, gives a definition of
anonymity which seems convincing. 

Then the paper by Franklin and Durfee on "Distribution Chain Security"
discusses the problems of dealing with contracts in a distribution chain.
They have to balance the rights of buyers, sellers, and various middlemen
- and develop some cute cryptographic tricks to do it. Obfuscated
contracts, zero-knowledge proofs, and special "contract certifiers" make
an appearance. It wouldn't surprise me if this ended up having application
beyond the content distribution network scenario they propose. 



 > 
> Crypto systems, using a mix of crypto tools, is only slowly taking 
> off. In fact, the focus keeps moving back to simple encryption, 
> depressingly enough!
> 

Depressingly enough, we keep finding that the focus *needs* to move back
to simple encryption. Birgit Pfitzmann published a paper in the 1980s on
"How To Break the Direct-RSA Implementation of MIXes." Today, nearly
fifteen years later, we still don't know "really" what we need from 
an encryption system for MIXes; David Hopwood has some good thoughts,
but we're not done yet. 

On the other hand, we can oppose this to the fact that we have a bunch of
remailers, and they seem to work. They may be unreliable, but no one seems
to have used padding flaws to break a remailer, as far as we know. 

 > (And, as I have been saying for close to 10 years, the
insurance 
> industry will be a driver of new approaches. Newer safes were bought 
> not because store and bank owners were "educated" about security (the 
> precise analogy to security today), but because insurance premiums 
> were lessened with better safes. Discounted present value, DPV, 
> speaks louder than all of the moralizing and lecturing.)

This may have to wait until liability issues in general for software are
straightened out, won't it? 

More than that, if the "tragedy of the commons" really happens for
Gnutella and Napster and friends, then people will look for ways to avert
it. Maybe it won't happen ("The Cornucopia of the Commons"), but if
it does, reputation systems might see some sudden interest. 



> 
> In other words, it's time to get crypto out of the math and computer 
> science departments and put it in the engineering departments where 
> it belongs.

Actually, to read this message, it sounds more like it should be part of
the economics department! There are people working on that. Joan
Feigenbaum came to speak at Harvard last spring on her recent work on fair
pricing for multicast trees; this was a case of finding the best algorithm 
in the face of an "adversary" model specified by economic considerations.

Noam Nisan has a list of some academic research groups also working on
this at http://www.cs.huji.ac.il/~noam/econcsgrps.html

I suppose the next step is to apply this to cypherpunkish
considerations...

-David