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