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

Perry E. Metzger perry at piermont.com
Thu Nov 12 11:55:58 EST 2015


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?

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

Perry
-- 
Perry E. Metzger		perry at piermont.com


More information about the cryptography mailing list