[14101] in Cypherpunks
Re: Graph isomorphism based PK cryptosystems?
daemon@ATHENA.MIT.EDU (Eli Brandt)
Tue May 24 20:14:20 1994
To: cypherpunks list <cypherpunks@toad.com>
Date: Tue, 24 May 94 17:08:05 PDT
From: Eli Brandt <ebrandt@jarthur.cs.hmc.edu>
In-Reply-To: <m0q62wr-0003pXC@jpplap>; from "Jay Prime Positive" at May 24, 94 1:19 pm
> 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
