At 2:42 AM -0500 12/26/00, dmolnar wrote:
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.
Has there really been much progress in the last ten years? I remember the flurry of ground-breaking work in the mid-80s, and it was much in the air at the first "Crypto Conference" I attended in 1988 (also the last such conference I attended, for various reasons). Something I expected to have happened long ago was the encapsulization of these protocols into building blocks into libraries/classes/reusable objects that could be bolted together by those building systems. ("Let's take EncryptStream and throw in EscrowService and then add ObliviousTransfer..."). This is partly what I mean by "devolving back to basic ciphers." It seems that when all is said is done, the only real "core module" we have is basic encryption. And even that is not treated as a module (yeah, I know that RSA is only recently unencumbered by patents). Some stuff with signatures, too, but basically very similar. In short, the world doesn't look very different than it did in 1990. The Web is different, but not in how users send messages and files back and forth.
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.
Yes, and those remailers are not much different than what we specc'ed out at the very first Cypherpunks meeting. That they work as well as they do relates to the economics point. A digression: One of the conventional models for a cryptographic attack is that an attacker gets to take a problem back to his lab and torture it to death, i.e., throw as much computer power against a cipher as he wishes. This is a reasonable model for ciphers. However, mix-nets and such need to have some economic considerations. It costs money and effort to subvert certain nodes and alter message padding, times of sending, etc. An attack on a mix-net is not the same as taking the whole net back into NSA basements and proceeding to diddle it to death. Chaum, Pfitzman, et. al. of course refer to n-out-of-m sorts of collaborations, but left unsaid is the cost of such collaborations. A start, but missing a lot. That such a simple implementation of Chaum's mix-net (it had to be simple, as I was the one who specc'ed out most of the features a remailer network needed to have, and Eric Hughes implemented some of them in Perl, then Hal Finney added PGP a few weeks later) has not had a known major attack is a tribute to the difficulty in actually subverting enough nodes in a mix-net. (Nodes in different countries, nodes operated more-or-less on automatic pilot, nodes which mail to _themselves_, nodes which are "middleman only," etc.) Crypto does encompass the idea of a "work factor," of course. Usually expressed as MIPS-years or somesuch. This needs to be extended in some rough way to include the costs of soliciting cooperation or collusion, etc. Without such inputs, how could a heterogeneous mix of remailers be analyzed?
(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?
It could happen absent any action on the legal front. Pure anarcho-capitalism, a la the Law Merchant (law of the seas, with no nation having legal jurisdiction). Lloyds of London was underwriting shipping before there was much concern about international legal dispute resolution. Computer security and information theft is not the same thing as ships going down, so the evolution will be different. But, no, I don't think such systems will have to wait until liability issues are resolved.
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.
Indeed, I cited economics in a major way. Hal Varian at Berkeley is also interested in such issues, and a former Cypherpunks list member, Robin Hanson, got his Ph.D. at Caltech on these kinds of issues. (Robin is the main "idea futures" guy.) One key issue is that not a lot of econ folks are good at crypto-type protocols, and vice versa. Different departments, different standards for advancement and academic fame. But I already alluded to this, so no need to expand on this here. Multi-agent systems, evolutionary game theory, and combinatorial game theory are some of the other areas I think are critical. Ecologies of agents interacting with each other via various protocols for identity, values of goods traded, pricing, auctions, escrows, etc. --Tim May -- Timothy C. May tcmay@got.net Corralitos, California Political: Co-founder Cypherpunks/crypto anarchy/Cyphernomicon Technical: physics/soft errors/Smalltalk/Squeak/agents/games/Go Personal: b.1951/UCSB/Intel '74-'86/retired/investor/motorcycles/guns