That 70's Crypto Show (Re: Dude! It's wired!)
Tim May
tcmay at got.net
Tue Dec 26 10:38:36 PST 2000
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 at 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
More information about the cypherpunks-legacy
mailing list