From: wcs@anchor.ho.att.com (bill.stewart@pleasantonca.ncr.com +1-510-484-6204)
Date: Sat, 23 Jul 94 23:53:50 PDT
To: cypherpunks@toad.com
Subject: Re: Travelling ants
Message-ID: <9407240652.AA08911@anchor.ho.att.com>
MIME-Version: 1.0
Content-Type: text/plain


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