Re: Graph isomorphism based PK cryptosystems?

["Perry E. Metzger" <perry@imsi.com>]

Jay Prime Positive says:
>   I've been out of the literature for quite a while now so pardon me
> if this is a dumb question.  Do any of you know of any public key
> cryptosystems based on the graph isomorphism problem?  Last I heard
> there weren't any.  But I think I've found one.

There was a powerful result a while back concerning public key systems
based on NP complete problems -- in particular, I recall that there
was a large class of them that were flawed -- the original knapsack
problem based public key system suffered from the defect from the
limited amount my neurons will disgorge. Sadly, I can't remember the
details any longer. Anyone else have a vague recollection on this?

It would be cool to hear about your graph isomorphism based system in
any case. I have heard of zero knowledge systems based on graph
isomorphism, but never public key systems.

By the way, there is a neat paper circulating in samizdat form from
China about public key systems based on compositions of finite
automata. However, I'm more or less obligated not to spread it about
until the paper has been published (sigh). Its quite tantalizing,
though.

Perry