derek@cs.wisc.edu (Derek Zahn)
* in broad terms, what would I have to do to develop an algorithm that works from a user's perspective like p.k.c. (ie public/private keys, the central functional point of all the wonderful schemes based on pkc) but doesn't violate patents?
others have well addressed how patent issues are involved in this. but this appears to be a simple technical question on one level. What does it take to come up with a good public key system? Answer: far more than you would think. RSA for example has gained its current degree trust only after about a decade and a half of careful and intense scrutiny in the literature, with many new caveats and modifications invented along the way. Furthermore, the mathematical & computational journals are strewn with failed attempts at getting a workable public key system by the most brilliant experts in the field (actually, in many fields). In particular, there was a lot of excitement about Knapsack cyphers, related to something called the Subset Sum problem, and a flurry of papers proposed, broke, and refined subsequent variations. Currently it appears to have really gotten a stake through its heart from the last authoritative paper (who?). (I would be curious for more details from the academically adept.) The rewards to a public key system are enormous, but the obstacles are tremendous as well. just getting a good *theoretical* model is very difficult, as the above attests. Then, this theoretical model has to be *efficient* when encoded in an algorithm -- another big stumbling block. Then, in the real world of ugly litigation, it has to tiptoe around the field of all the national and international patents, and, ahem, byzantine export laws. A very grim picture currently, in many ways, and to a large degree why RSA--and PGP/PRZ-- are so celebrated. Hopefully the future holds something less bleak. note: the new sci.crypt FAQ will have a much-improved section on public key cryptography. watch for it on the newsgroup or rtfm.mit.edu:/pub/usenet/news-answers/cryptography-faq if you want it right away.