From: thad@hammerhead.com (Thaddeus J. Beier)
Date: Tue, 28 Nov 1995 12:31:23 +0800
To: cypherpunks@toad.com
Subject: Re: Directed Hamiltonian Path Problem
Message-ID: <199511280404.UAA03020@hammerhead.com>
MIME-Version: 1.0
Content-Type: text/plain


>  I am curious on whether there are any applications of the directed
> Hamiltonian path problem to cryptography, zero-knowledge proofs, etcetera. My
> reaosn for asking is that I've come across something in my field (molecular
> genetics) that can be used to solve such problems in a couple of weeks or so.
>  -Allen
> 
> 
Secret sharing can be done by Hamiltonian paths.  No public key code has been
found to take advantage of those, or any other NP complete problem, so far as
I know.  DNA computing really doesn't solve the Hamiltonian graph problem, it
just makes the biggest one that you can solve a little bit bigger.  500 point
graphs remain insoluble (pun unitended) for earth-sized vats of DNA. 

Really.

-- Thaddeus Beier                   email:  thad@hammerhead.com
   Technology Development             vox:  408) 286-3376
   Hammerhead Productions             fax:  408) 292-2244