[Cryptography] Does anyone use ZKP systems based on graph isomorphism?

[Jonathan Katz]

On Thu, Nov 12, 2015 at 11:55 AM, Perry E. Metzger <perry at piermont.com> wrote:
> When I first learned about Zero-Knowledge Proof systems, the example
> used for an underlying was graph isomorphism. Graph isomorphism has
> always been known to be in NP but never known to be NP complete, but
> until now the best algorithms were all well above polynomial time.
>
> It appears, however, that a very recent breakthrough result by
> Laci Babai (first described two day ago in a seminar)
> places the graph isomorphism problem into quasi-polynomial time.
>
> So my question is, are there any real world ZKP systems deployed in
> the field that actually depend on the graph isomorphism problem?

I doubt it.

It's not clear that ZKPs based on GI ever had any benefit as compared
to those based on factoring or discrete log. Moreover, it turns out
that even before Babi's result, there were several heuristic
algorithms that solved GI very quickly. See also this recent post:
  https://lucatrevisan.wordpress.com/2015/11/05/what-does-it-mean-when-its-hard-to-find-hard-instances/
which explains that it was never known how to generate instances of GI
that were believed to be hard in the first place.

> (And at the very least, all the textbook examples using graph
> isomorphism might want updating.)

Are there any?

> Perry
> --
> Perry E. Metzger                perry at piermont.com
> _______________________________________________
> The cryptography mailing list
> cryptography at metzdowd.com
> http://www.metzdowd.com/mailman/listinfo/cryptography