[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]
Re: Graph isomorphism based PK cryptosystems?
-----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
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
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
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-----
-----END PGP SIGNATURE-----
Mark Henderson [email protected] - 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