Last class, we talked about using Graph Isomorphism as the basis for a zero knowledge proof, based on the assumption that it is a computationally hard problem to determine if two graphs are isomorphic.

Yesterday, Laszlo Babai presented a result that claims a quasipolynomial time algorithm for graph isomorphism (that is, shows graph isomorphism is not a hard enough problem to use as the basis for a zero knowledge proof).

Jeremy Kun’s summary of Babai’s presentation

*A Big Result on Graph Isomorphism*

Note that this has no bearing on the zero knowledge proofs based on the hardness of graph three-coloring, which, unlike graph isomorphism, is know to be NP-Complete.