-----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