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.