[curves] Babai's graph isomorphism algorithm

[Jeff Burdges]

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.  :)






-------------- next part --------------
A non-text attachment was scrubbed...
Name: signature.asc
Type: application/pgp-signature
Size: 819 bytes
Desc: This is a digitally signed message part
URL: <http://moderncrypto.org/mail-archive/curves/attachments/20151107/56ad30ef/attachment.sig>