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
bram (bram@gawth.com)
Thu, 13 Aug 1998 18:25:55 -0700 (PDT)
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).
Hmmm, Applied Cryptography says it is, I guess that's a major boo-boo.
> Graph 3-coloring is an NP complete problem for which a relatively simple
> ZK proof exists, and for which there are reductions from other NP problems
> like boolean satisfiability. So this is much more widely used as a way of
> proving things in zero knowledge.
3-coloring has the disadvantage of requiring some care to generate hard
instances. max-clique has the advantage that it's average case difficulty
is really nasty - just pre-pick a clique of size 2*sqrt(n), turn about
half of the remaining edges on (making it just a bit more likely that
members of the clique have edges to non-members turned on, to avoid
letting them have too few edges) and presto, one *hard* problem. Encodings
using max-clique tend to be a bit inefficient though, so it does have
disadvantages.
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 :)
-Bram
The following archive was created by hippie-mail 7.98617-22 on Sat Apr 10 1999 - 01:10:58