Re: Graph isomorphism based PK cryptosystems?

[Eli Brandt <ebrandt@jarthur.cs.hmc.edu>]

> From: jpp@jpplap.markv.com (Jay Prime Positive)
> cryptosystems based on the graph isomorphism problem?  Last I heard
> there weren't any.  But I think I've found one.

Interesting.  Have you tested it against the known methods for the
isomorphism problem?  Van Leeuwen* references an O(n log n)
average-case algorithm, and ones that are pseudopolynomial w.r.t.
degree, genus, and treewidth.  There are also methods based on
"signatures" (hash functions on graphs, basically); there's an O(n^2)
expected-time perfect signature, and an O(n) (worst-case?) one with
exponentially small failure rate.  These might provide attacks,
though none solve the general problem.
	* (in Handbook of Theo. Comp. Sci., Vol. A)

BTW, the graph isomorphism problem is not known to be NP-complete,
and van Leeuwen comments that there is some theoretical basis
for expecting it not to be.  

Disclaimer: I don't know much about graph theory, I'm just getting
paid to do it.  :->

   Eli   ebrandt@hmc.edu