Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58
Wei Dai (weidai@eskimo.com)
Wed, 12 Aug 1998 15:41:38 -0700
On Wed, Aug 12, 1998 at 10:51:49AM -0600, Mike Stay wrote:
> Is anyone familiar with NAUTY (No AUTomorphisms, Yes?)? It's the best
> known test for graph isomorphisms, and I was wondering what order of
> magnitude a graph would have to be to make the test infeasible. A graph
> with 864 vertices and only one automorphism only took 10 minutes to test
> with NAUTY
> (http://www.cs.sfu.ca/cs/people/GradStudents/khopkins/personal/papers/graph_isomorphism/node12.html)
> Apparently even finding hard graphs is non-trivial. Are there any
> implementations of zero-knowledge proofs based on the graph isomorphism
> problem I could try NAUTY on?
Crypto++ had an implementation of zero-knowledge prover for graph
isomorphism (noted as non-secure illustration only) in version 2.1. It was
removed in version 2.2. Version 2.1 can still be found at Mark Henderson's
archive site:
ftp://ftp.mindlink.net/pub/crypto/software/dist/US_or_Canada_only_?????/LIBS/weidai/crypto21.zip
where the "?????" is in
ftp://ftp.mindlink.net/pub/crypto/software/README.html.
I'd be interested in the result of your experiments.
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58