[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