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
Anonymous (nobody@replay.com)
Thu, 13 Aug 1998 00:45:40 +0200
> Are there any
> implementations of zero-knowledge proofs based on the graph isomorphism
> problem I could try NAUTY on?
Wei Dai's Crypto++ library has an experimental implementation of a
zero knowledge proof of graph isomorphism. You can create a random
graph of a specified size, then either permute it or create another
random graph, and prove in zero knowledge whether the two graphs are
isomorphic.
I don't think graph isomorphism is used much in actual ZK work because
it is not NP complete (probably). Therefore there is no reduction to
graph isomorophism from other problems and about all it is good for is
actually showing whether two graphs are isomorphic, which isn't all that
useful.
Graph 3-coloring is an NP complete problem for which a relatively simple
ZK proof exists, and for which there are reductions from other NP problems
like boolean satisfiability. So this is much more widely used as a way of
proving things in zero knowledge.
H
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58