Re: Travelling ants

["Perry E. Metzger" <perry@imsi.com>]

bill.stewart@pleasantonca.ncr.com +1-510-484-6204 says:
> Tim May writes:
> > 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 :-)

There are the finite automata systems that were developed in China and
have been floating around in privately circulated papers. I have no
idea when these will be "officially" published. The systems in
question are quite exciting because they are far, far faster than RSA.
On the other hand, public key system after public key system has been
broken in the last fifteen years, so I'm not holding my breath.

Perry