cryptoanarchy.wiki

Arise, you have nothing to lose but your barbed wire fences!

1994-05-24 - Re: Graph isomorphism based PK cryptosystems?

Header Data

From: “Perry E. Metzger” <perry@imsi.com>
To: jpp@jpplap.markv.com (Jay Prime Positive)
Message Hash: 6e19da6ea0a39c71aa15d90e34e78212397af91176749d37b9078920b52a2334
Message ID: <9405242211.AA03230@snark.imsi.com>
Reply To: <m0q62wr-0003pXC@jpplap>
UTC Datetime: 1994-05-24 22:12:15 UTC
Raw Date: Tue, 24 May 94 15:12:15 PDT

Raw message

From: "Perry E. Metzger" <perry@imsi.com>
Date: Tue, 24 May 94 15:12:15 PDT
To: jpp@jpplap.markv.com (Jay Prime Positive)
Subject: Re: Graph isomorphism based PK cryptosystems?
In-Reply-To: <m0q62wr-0003pXC@jpplap>
Message-ID: <9405242211.AA03230@snark.imsi.com>
MIME-Version: 1.0
Content-Type: text/plain



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

Thread