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