the public key minefield

["L. Detweiler" <ld231782@longs.lance.colostate.edu>]

 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.