This was the first year I attended a Crypto conference (although for the last two years I have "crashed" the evening rump session, where less formal 5-10 minute presentations are given). A number of list members were present and it was good to meet a lot of new people. I was a bit disappointed that few of the technical sessions were in areas that I am interested in or that seem to have bearing on CP issues. I have read many of the Crypto proceedings and this year the pickings seemed to be unusually slim. Richard Schroeppel gave a very clear presentation on an implementation of elliptic curve cryptography for a diffie-hellman-like key exchange. This is a two-dimensional variation from the regular integers that are used in most of the number theory based crypto, and has some advantages. This new implementation is actually faster than regular DH for apparently the same security level. It looks like elliptic curve crypto is on the threshold of coming into widespread use. I believe the patent situation is one of the main reasons. There were several papers on secret sharing, something we have discussed here as an alternative to escrow for handling lost keys. Amir Herzberg et al had a method for "resharing" a shared secret periodically and securely, so that if an adversary was stealthily sneaking in and learning shares occasionally, he would be put back to square one when the secret resharing phase occured. Only the trustees are involved, not the original secret holder, and the secret does not have to be reconstructed during the resharing. Bruce Dodson presented some results on using the Number Field Sieve factoring algorithm. Their implementation looks to be the fastest available now, considerably better than the Quadratic Sieve that was used for RSA-129. I belive they estimated 1000 MIPS years would have been enough for NFS to do RSA-129 compared to the 6000 MIPS years for QS. They are now going to try another challenge number, RSA-130. (RSA has challenge numbers every 10 digits in size (or maybe it was 5): RSA-140, RSA-150, etc.) There was one paper on electronic cash, by Okamoto. His technology is distinguished by allowing divisibility - you can take a $10 and divide it into 2 $5's without going back to the bank. However he has always had a problem that your various pieces of cash are linkable, although not traceable to the user who withdrew them. His new method uses smaller amounts of data. I was encouraged to see some progress on the linkability issue: for the first time (that I have seen) he admits it as a problem; he now has it so that theoretically the linkability is only within a single divided piece of cash (so that if you didn't divide you wouldn't have linkability). Actually the overheads are too large for this to by quite true, but it is a step in the right direction. He also included elimination of linkability as a future goal. Unfortunately his oral presentation was extremely shallow, mostly describing what electronic cash was. There was also a paper on "fingerprinting", the encoding of hidden information into a document so that if the doc is leaked it can be traced to the leaker. The talk wasn't very clear but I was able to glean enough that I now believe that this is possible whereas I didn't before. I was discouraged to see a whole session on key escrow. One presenter described key escrow as a whole new area of cryptography, analogous to the discovery of public key crypto when all that was known previously was conventional key. Now there are three areas. The academic crypto community seems to be greeting key escrow enthusiastically as a new technical challenge. The rump session had some good stuff, I thought. Matt Blaze et al had a paper on "Master Key" cryptosystems, a variation on escrow where the government can read all the messages using a certain cryptosystem. They pointed out the similarity to the trap door concept used in public key cryptography and concluded that an efficient master key system would be an efficient public key system. If you believe that the latter can't exist then it follows that the master key versions can't exist either. Bruce Schneier gave a talk summarizing the sketchy information known about Skipjack (the cipher in Clipper), including some FOIA'd docs. These included some comments from design reviews by Mycotronix on earlier versions, which included references to F and G boxes or tables. This is the first I had heard of this and helps explain why people thought S-1 was Skipjack or a hoax, since it had F and G tables. (I hadn't felt that the number of rounds and key/block sizes were sufficient coincidence to preclude independent invention.) A new crypto library was announced from AT&T. It is written in C and has a bignum lib (arbitrary size) and the usual crypto suspects, although I think not RSA presuambly due to patent issues. On a reasonably modern PC it could do an RSA 1024 bit signature in 900 milliseconds. Email to lacy@research.att.com with subject CRYPTOLIB to be informed on when it will be released and how to get it. Dhem and Quisquiter described CASCADE, a smart card system with voice recognition for ID rather than the PIN usually used. http://www.dice.ucl.ac.be/~dhem/cascade/. This talk was hard to understand due to the language differences. Eric Hughes, co-founder of the cypherpunks, announced the formation of Cypherpunk Laboratories, a California non-profit corporation. It is intended to be a common resource for people motivated by freely available strong cryptography tools. Among other things it will offer scholarships and prizes to students who create relevant work and papers, consider establishing an online journal focusing on implementations of crypto, and work on software development. One project Eric mentioned was to create a replacement for PGP. Ron Rivest proposed probabilisitic key escrow, which he described as "translucent" crypto. The idea is that with every message you send there is a Law Enforcement Access Field, but there is only some probability p that it is readable, and you can't tell if it will be readable or not. This way you don't lose as much privacy but criminals can't take the risk that maybe they'll be unlucky and this particular message will be readable. Shamir had an interesting paper on preventing "flooding" attacks. A server may check for signatures on incoming messages to reject bogus ones (only certain sigs are valid) but just doing a signature check may take too long if it is really being flooded. Shamir came up with a kind of signature which can be quickly probabilistically checked, based on a variation on the Rabin cryptosystem. You can do almost all the work using single precision and it should be very fast. I will write this up if anyone is interested. Our own Wei Dai, at 19 the youngest author, has spent his summer vacation developing with Josh Benaloh at Microsoft an improved modular reduction algorithm, which unfortunately will be patented (or at least they will try). BTW a number of people from Microsoft were in attendance at Crypto, including other list members. Obviously this crypto stuff is considered very important at MS. One of the more interesting talks I thought was from cypherpunk Doug Barnes, on "identity agnostic" electronic cash. This is basically an idea for creating a Magic-Money-type electronic cash server without violating Chaum's cash patent. What you do is to run the server and publish a spec it will follow. All the server does is do an RSA signature on the raw data it receives and decrement the user's account accordingly. The user has a choice of doing blinding or not on the signature. Chaum's patent covers the blinding, so if the user wants to do that he should be sure to license the patent or live somewhere it doesn't apply (or ignore it if he figures he's too small potatoes for them to care about). But the server isn't responsible for checking all this. It just does RSA sigs, which is prior art as far as Chaum's patent goes. Users can blind or not, it doesn't care. It is "identity agnostic" as Doug says. The implication is that with an RSA license you could run this kind of bank (online cash) and ignore Chaum's patents, while a horde of end users violate the patents but take safety in numbers and get anonymity. Lawyers like to go after big targets but the servers aren't violating anything. The other things I enjoyed in the conference were the non technical talks by Bob Morris (senior), retired NSA, and later Adi Shamir. Morris said, with what I thought was peculiar emphasis, "never underestimate the amount of time, money, and effort your opponent will put into breaking your encryption." He was supposedly speaking in the context of the German (and Allied) mistakes during WWII, but I got the impression he was talking about today, and in fact warning of NSA efforts to spy on people. He went on to describe the many ways mikes and antennas can be planted or used - he looks at a telephone and sees a microphone, and the hand cord is an antenna. All in all a rather chilling talk from someone who obviously can't say as much as he would like to. Shamir had some interesting anecdotes about the invention of RSA. He emphasized what amateurs the three of them were, claiming this was probably an advantage. Some of the other talks I enjoyed without following all the details were the cryptanalysis ones. A lot of systems were broken or weaknesses found. Most were not ones I was familiar with but it just emphasizes how hard it is to really come up with something strong. All those bozos on sci.crypt with their "break this" challenges would benefit from seeing some of these results. All in all there were several interesting results even if the percentage seemed smaller than usual. Hal Finney