Tim May writes:

* By the way, there has been little progress in taking known NP-complete decision/computation problems and making cryptosystems out of them. I'm not sure why this is, and I get the impression that not many others understand this either.

In fact, I'll close with a nagging questio. Except for some work on elliptic functions, there has been no real alternative to RSA for public key crypto. Why? One would think that in 16-18 years of work, some alternatives based on something other than the difficulty of factoring or taking discrete logs would have been developed. Why not?

Good one-way transformations are hard to find. Merkle & Hellman's knapsack-based cryptosystem predated RSA; it depended on transforming an easy subproblem of a NP-hard general problem into the general case. Shamir and others found ways to reverse the transformation that was used, reducing it to the easy problem. In general, a symmetric cryptosystem needs to have one easy path through it (using the key); an asymmetric system needs two (encryption & decryption), and that's much harder to find. The inter-relatedness of NP-complete problems probably doesn't help much. There may be some deep mathematical truth hiding somewhere in here, but I'm more of an applied-math type than a real theoretician :-) A separate problem is that signature and encryption are both useful, and it's hard to find a system that can do both securely.

"National borders are just speed bumps on the information superhighway." Lately they've been more like speed limits...

Bill # Bill Stewart AT&T Global Information Solutions, aka NCR Corp # 6870 Koll Center Parkway, Pleasanton CA, 94566 Phone 1-510-484-6204 fax-6399 # email bill.stewart@pleasantonca.ncr.com billstewart@attmail.com # ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465