cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-05-25 - Re: Graph isomorphism based PK cryptosystems?

Header Data

From: Eli Brandt <ebrandt@jarthur.cs.hmc.edu>
To: cypherpunks list <cypherpunks@toad.com>
Message Hash: 73feae805f732b6577174809a930f6252c63aed4b99d65cd10b2529b9cd80185
Message ID: <9405250008.AA01719@toad.com>
Reply To: <m0q62wr-0003pXC@jpplap>
UTC Datetime: 1994-05-25 00:08:13 UTC
Raw Date: Tue, 24 May 94 17:08:13 PDT

Raw message

From: Eli Brandt <ebrandt@jarthur.cs.hmc.edu>
Date: Tue, 24 May 94 17:08:13 PDT
To: cypherpunks list <cypherpunks@toad.com>
Subject: Re: Graph isomorphism based PK cryptosystems?
In-Reply-To: <m0q62wr-0003pXC@jpplap>
Message-ID: <9405250008.AA01719@toad.com>
MIME-Version: 1.0
Content-Type: text/plain


> 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

Thread