From: utzoo!decvax!yale-com!leichter
Newsgroups: net.math
Title: Re: random numbers
Article-I.D.: yale-com.1395
Posted: Sat Apr 23 13:44:46 1983
Received: Sun Apr 24 08:06:58 1983
References: allegra.1252

Don remarks that the knapsack method used in Unix secret mail "is crumbling
rapidly".  Just to provide a little further data:  The basic knapsack system
has completely crumbled, in the sense that there is a polynomial time algorithm
that will break it (although it's a slow algorithm...).  A reference is:
"A Polynomial Time Algorithm for Breaking the Basic Merkle-Hellman Crypto-
system", Adi Shamir, Proceedings of the 23rd FOCS (roughly December 82, I don't
have a copy), pg.145-152.  Shamir has proposed some variations on the basic
scheme, including an "ultimate" variation that appears in some sense to be
the strongest one possible ("Embedding Cryptographic Trapdoors in Arbitrary
Knapsack Systems" - I can't provide a reference, I'm afraid - all I have is
a 6-month-or-so old pre-print).  The security of these variations is not known
with certainty, but at best one can say that no one can yet see an attack -
they don't look to healthy.
							-- Jerry
						decvax!yale-comix!leichter
							leichter@yale