[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Graph isomorphism based PK cryptosystems?
> Date: Tue, 24 May 94 17:08:05 PDT
> From: Eli Brandt <[email protected]>
>
> 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)
No I haven't tested it against any known GI algorithm. Your
references are all very interesting and I will investigate them. If
you had a publisher handy, along with the city the publisher is in, I
would happily phone them up and get a copy. But if not, I can operate
a card catalog.
> 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.
No, I didn't expect GI to be NP-complete at all. I expect rather
that P < GI < NP. That is one of the reasons that GI is an
interesting problem. Especialy because (as you point out) GI is amost
always in P.
In any case, my PK cryptosystem is not interesting except for the
new complexity point. (Although, the general construction may be
interesting.) I can prove that my cryptosystem has a level of
security which is reduceable to GI, and GI to it. (The reduction is
only in polynomial time. I will try to see about getting the slow
parts down to O(n) time.)
PGP will almost certainly never include my PK system as an
alternative to RSA. For one thing it needs a k^3 to 1 expantion in
communication costs for a security parameter of k. For another the
'fast' decrypt routine requires O(n^3) in the number of nodes in the
graphs. But there is no known GI algorithm which is O(n^3) in
general. (And if there is one for *my* graphs, then I will give you a
polynomial time algorithm for all of GI.)
> Eli [email protected]