[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
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 [email protected] [email protected]
# ViaCrypt PGP Key IDs 384/C2AFCD 1024/9D6465