Other Directory Sites: SeekWonder | Directory Owners Forum
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58
Anonymous (nobody@replay.com)
Fri, 14 Aug 1998 08:50:40 +0200
On Thu, 13 Aug 1998, Anonymous wrote:
> I don't think graph isomorphism is used much in actual ZK work because
> it is not NP complete (probably).
Bram replied:
> Hmmm, Applied Cryptography says it is, I guess that's a major boo-boo.
Subgraph isomorphism is NP complete but graph isomorphism is thought not
to be. However the simple perfect ZK proof of graph isomorphism (create
a random graph isomorphic to the two isomorphic graphs, by permuting one
of them, and show that it is isomorphic to the verifier's choice of the
two) does not carry over to subgraph isomorphism.
Bram asked:
> Does anyone know of any actual use of zero knowledge techniques for
> signatures? That has the nice feature of being just as hard to crack as an
> arbitrary ordinary hash function, and has small private keys. Of course,
> it also has large signatures, although hopefully smaller that a gigabyte,
> and it's subliminal channel is more like a subliminal broadcast network,
> but hey, you pick and choose :)
You can turn a 3 move ZK proof (prover commits, verifier challenges,
prover responds) into a signature by making the challenge be a hash
of the message to be signed and the prover commitment. An example is
the Schnorr signature, which is based on a ZK proof of knowledge of a
discrete logarithm. Many kinds of signatures can be thought of in this
way, as based on zero or minimum knowledge proofs of knowledge of the
secret.
You could apply the same technique to graph isomorphism. The public
key is a pair of graphs and the secret key is a mapping between them.
To sign a document using an n-bit hash, the signer creates n random
graphs which are isomorphic to the two, hashes all of them plus the
message, and uses each of the n bits of output of the hash to select
which of the two graphs he must show is isomorphic to each of the n
random graphs. This whole thing constitutes the signature on the
message.
Do you have in mind a different way of using ZK techniques for signatures?
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58