I've just learned that Laszlo Babai recently found a quasipolynomial time algorithm for the graph isomorphism problem (GIP). http://people.cs.uchicago.edu/~laci/quasipoly.html http://www.scottaaronson.com/blog/?p=2521
Apparently both this algorithm, and the previous best algorithm, also by Babai (1983), depend upon finite permutation group results that themselves depend upon the classification of the finite simple groups (CFSG).* A priori, I'd expect that Babai's new result depends upon refinements in the asymptotic theory of finite permutation groups here that themselves use lots of character theory, but does not necessarily apply the CFSG is new ways. Afaik, there are no direct connection relevance of the GIP to cryptography, but the shortest-vector problem (SVP) and GIP are the two most commonly discussed special cases of the hidden subgroup problem (HSP). And the SVP is the basis for several approaches to post-quantum public-key or Diffie-Hellman, including I think NTRU and Ring LWE. Now Shor's algorithm is basically a HSP solver for abelian groups. It's therefore reasonable to ask : If anyone has a sense as to how applicable even the 1983 permutation group methods for GIP might be to SVP? It could be a step towards to breaking the post-quantum-ness of NTRU and Ring LWE. At minimum, anyone writing a grant application to work on super -singular isogonies might find a reason to mention Babai's work as added justification. ;) Jeff * At present, the proof of the CFSG runs like 15k pages! Although Ron Solomon and Richard Lyons are trying to make a 10k-ish page version. I can explain why you should believe this massive proof nobody reads, as I did my PhD in a branch of infinite group theory that uses methods from the proof of the CFSGs. :)
signature.asc
Description: This is a digitally signed message part
_______________________________________________ Curves mailing list Curves@moderncrypto.org https://moderncrypto.org/mailman/listinfo/curves
