The Fourteenth Algorithmic Number Theory Symposium (ANTS-XIV), that was intended to take place at the University of Auckland in New Zealand, is currently taking place online in what Noam Elkies has named “New Zoomland”. Here is a report on the first half of the conference.
Day one of the conference opened with two papers on isogenies.
- Supersingular Curves With Small Non-integer Endomorphisms, by Jonathan Love and Dan Boneh.
The motivation for this paper is the problem of “hashing” to a random supersingular curve over . A natural solution would be to construct a CM curve with small discriminant, as done in Broker’s algorithm. The paper calls such curves -small (curves whose endomorphism ring contains an isogeny of degree at most ). Equivalently the endomorphism ring contains an order of discriminant at most . For each fundamental discriminant such that let be the set of all -small curves such that the order lies in . The paper proves a number of new results (both mathematical and algorithmic) relating to the structure of the subgraphs within the full isogeny graph, when .
The conclusion is that, given any -small curves one can efficiently compute an isogeny from to , which means this is not a useful way to hash to elliptic curves.
Note that Castryck, Panny and Vercauteren (EUROCRYPT 2020) present a complementary result for hashing into the CSIDH set.
- Computing endomorphism rings of supersingular elliptic curves and connections to pathfinding in isogeny graphs, by Kirsten Eisenträger, Sean Hallgren, Chris Leonardi, Travis Morrison and Jennifer Park.
This paper is about the problem of computing when is a supersingular elliptic curve. There are two approaches to this problem in the literature:
- To compute cycles in the isogeny graph (and hence endomorphisms), giving a subring of . Then to work out which of the maximal orders containing that ring is the right one. This idea first appears in Kohel’s thesis, but all the details were not worked out.
- To compute an isogeny from a nice curve with known endomorphism ring to , and then to deduce the endomorphism ring of . The key step to such approaches is the paper by Kohel, Lauter, Petit and Tignol (from ANTS 2014). Several subsequent papers discuss details of computing , in particular the paper Supersingular isogeny graphs and endomorphism rings: reductions and solutions by Eisenträger, Hallgren, Lauter, Morrison and Petit.
This ANTS paper is the first to give all the details of an algorithm of the first approach (finding cycles) and to work out the complexity carefully. The main focus of the paper is a study of Bass orders. The paper pays close attention to the size of the representation of the endomorphism ring.
At a high level it is not obvious to me which of these two approaches is the better strategy, or whether they both should have basically the same complexity.
Next up was a superb invited lecture by David Harvey on Recent results on fast multiplication. A recording of the lecture is on the YouTube channel mentioned above.
The first day concluded with two more talks on superspecial curves.
- Counting Richelot isogenies between superspecial abelian surfaces, by Toshiyuki Katsura and Katsuyuki Takashima.
The paper has a careful analysis of the isogenies of superspecial dimension 2 abelian varieties. The goal is to distinguish the case of isogenies to a product of two elliptic curves versus isogenies to the Jacobain of a genus 2 curve.
- Algorithms to enumerate superspecial Howe curves of genus four, by Momonari Kudo, Shushi Harashita and Everett Howe.
The paper is about a method to construct superspecial curves genus 4 curves out of elliptic curves and genus 2 curves.
Day two had a number of nice papers, but probably less interesting to a cryptographic audience (also a bit early in the morning for me). Isabel Vogt gave an invited lecture on Arithmetic and geometry of Brill–Noether loci of curves. There was a poster session comprising three of the posters. One of the posters has a crypto context: Samuel Dobson, Steven D. Galbraith, and Benjamin Smith, Trustless Construction of Groups of Unknown Order with Hyperelliptic Curves.
Day three started with three number theory talks (again, too early in the morning for me — who organised this??). The invited talk by Felipe Voloch on Commitment Schemes and Diophantine Equations discussed some ideas for a post-quantum commitment scheme based on diophantine equations that are hard to solve but for which determining the number of solutions is easy.
Day three also featured a wonderful session by Joppe Bos and Michael Naehrig to remember Peter Montgomery. Peter had attended a number of ANTS conferences over the years, and died earlier this year. His name is legendary in computational number theory due to his contributions to factoring and fast arithmetic, such as Montgomery multiplication, the Montgomery model for elliptic curves, and the Montgomery ladder for elliptic curve point multiplication.
Finally on day three was the rump session, which was heavily biased towards isogenies.
- Everett Howe gave a hilarious talk on isogenies of superspecial curves in characteristic 2 (joint work with Bradley Brock).
- Enric Florit (reporting on joint work with Ben Smith) presented some results on the Ramanujan property (or not) of genus 2 isogeny graphs.
- Christophe Petit advertised the Isogeny-based cryptography winter summer school in Bristol in December.
- Péter Kutas talked on joint work with on quantum attacks on unbalanced SIDH.
- Antonin Leroux sketched SQIsign (pronounced “ski sign”) post-quantum signature from quaternions and isogenies. It seems a nice idea and I am very curious to see the details.
- Wouter Castryck (joint work with Thomas Decru and Fre Vercauteren) presented Radical isogenies which is a major breakthrough new idea to speed up CSIDH.
It has been a great 3 days. I will report back again on the rest of the conference, and also the workshop on post-quantum crypto that follows the conference.
— Steven Galbraith