[Date Prev][Date Next][Thread Prev][Thread Next][Date Index][Thread Index]

Re: Graph isomorphism based PK cryptosystems?


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

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?

Version: 2.4


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