Re: Travelling ants

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

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