From: markh@wimsey.bc.ca (Mark C. Henderson)
Date: Tue, 24 May 94 21:43:15 PDT
To: Eli Brandt <cypherpunks@toad.com>
Subject: Re: Graph isomorphism based PK cryptosystems?
Message-ID: <m0q6AiX-0000VQc@vanbc.wimsey.com>
MIME-Version: 1.0
Content-Type: text/plain


-----BEGIN PGP SIGNED MESSAGE-----

Subject: Re: Graph isomorphism based PK cryptosystems?

> 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.
Luks did the trivalent case and then later the bounded valence case. 
bounded genus is due to Miller. Also bounded eigenvalue multiplicity 
due to Babai and others.

There are also a number of related problems which are believed to be 
difficult. 

Finding a small generating set for the automorphism group of a graph is
polynomial time equivalent. The graph isomorphism problem also reduces
to several of computational problems in permutation groups where these
groups are given by small generating sets (e.g. calculation of the centraliser
of a permutation, group intersection, double coset membership, subset
stabiliser, normaliser)

This is one of those problems where the "average" case is relatively 
easy. Take a random graph (with a reasonable definition), finding the 
automorphism group is usually relatively easy by backtracking. The 
hard cases are ones which superficially look like they have lots of 
symmetry but really have small non-trivial automorphism groups. 
Similarly for graph isomorphism, i.e. take two random graphs (again 
one needs to define this), it is usually pretty easy to determine 
whether they are isomorphic (just look at the degree sequence and 
work from there). Approaches involving backtracking to find 
isomorphisms can be effective in more subtle cases. 

So you need to be careful to avoid the easy cases. I remember some 
really hard (practically) cases for the usual backtracking approaches to 
determining automorphism groups came from graphs derived from certain 
designs. 

I'd sure like to see more details about a public key system based
on Graph Isomorphism. (For a book on graph isomorphism and related 
computational problems take a look at C.M. Hoffmann, Group-Theoretic
Algorithms and Graph Isomorphism, Lecture Notes in Computer Science
#136, Springer-Verlag, 1982. A little old but it covers a fair bit).

There is a point to this, I remember some papers by Magliveras (sp?)
on cryptosystems from problems in permutation groups. Anyone have
copies or remember any details?


-----BEGIN PGP SIGNATURE-----
Version: 2.4

iQBVAgUBLeLV9WrJdmD9QWqxAQHKYAH9EuLksdWKLvnhr6FIRjBZO6O2eyKCY6rI
MsDvo2V8QJTLdXDHR/rDuChdOQRIQtsa7H1k3/ZEZnP331Roeg3/3w==
=yJZr
-----END PGP SIGNATURE-----

-- 
Mark Henderson markh@wimsey.bc.ca - RIPEM MD5: F1F5F0C3984CBEAF3889ADAFA2437433
ViaCrypt PGP key fingerprint: 21 F6 AF 2B 6A 8A 0B E1  A1 2A 2A 06 4A D5 92 46
low security key fingerprint: EC E7 C3 A9 2C 30 25 C6  F9 E1 25 F3 F5 AF 92 E3
cryptography archive maintainer -- anon ftp to ftp.wimsey.bc.ca:/pub/crypto