SIAM Conference on Applied Algebraic Geometry (AG23)

The SIAM conference on Applied Algebraic Geometry took place in Eindhoven last week.

The “mini symposia” included:

• Applications of Algebraic Geometry to Post-Quantum Cryptology
• Elliptic Curves and Pairings in Cryptography
• Applications of Isogenies in Cryptography

Despite having promised myself to attend talks outside of my domain, I ended up attending all the talks in the “Applications of Algebraic Geometry to Post-Quantum Cryptology” mini-symposium. The first day was mostly about multi-variate crypto. Bo-Yin Yang gave two talks about the recent history of attacks on multivariate schemes, and some insights into the new UOV and TUOV submissions to NIST’s on-ramp signature call. The rest of the talks was about cryptanalysis. The day was closed by something more palatable to the audience of this blog and my personal highlight of the conference: Guido Lido took over Giulio Codogni’s spot and delivered a spectacular double talk on the spectral properties of isogeny graphs with level structure. At Eurocrypt, Guido and coauthors had shown that supersingular isogeny graphs with Borel level structure are Ramanujan, and applied this to construct statistically zero-knowledge proofs of isogeny knowledge. Here Guido and Giulio generalize the result to arbitrary level structures, showing that, modulo an obstruction coming from the Weil pairing, they are all “somewhat Ramanujan”. Guido barely said “crypto”, mistook the audience for the SGA seminar, and took us along in a journey through modular curves and Hecke operators that was easily the most AG talk in SIAM AG!

The second day was nearly all isogenies, and very much Italian. I essentially remade Guido’s talk for the layman, presenting along the way a still unpublished attack against “SIDH with a single torsion point”. Federico Pintore followed up with hard facts and numbers on still-unbroken SIDH-like signatures: nothing NIST-worthy, but some good cleanup. Annamaria Iezzi presented some progress on computing the endomorphism ring of supersingular curves: nothing new complexity-wise, but some heuristics are removed. Unfortunately I missed Valerie Gilchrist’s talk on supsersingularity testing. Thomas Decru presented his attack on SIDH, I don’t suppose the readers of this blog need to know more about this. Boris Fouotsa presented some counter-measures against the SIDH attacks that appeared at the last Eurocrypt, and then presented some nice improvements using what he calls “artificial orientations” (which, by the end of the symposium, everyone understood as being nothing else than Cartan level structures). Wouter Castryck gave the only non-isogeny talk of the day: he presented an attack against a key-exchange scheme based on “disguised” Veronese varieties, that one would be tempted to classify into the multi-variate bucket. The attack uses what Wouter calls “the Lie algebra method”; as he puts it: it’s all linear algebra, although quite advanced one.

The audience of the blog would certainly have found the workshop “Elliptic Curves and Pairing in Cryptography” interesting, however I attended other workshops, so I cannot report on it.

The week was closed by the well attended “Applications of Isogenies in Cryptography” workshop. The quick summary is: 50% SQIsign, 50% isogenies of abelian surfaces, and a vanishingly small set of other stuff.

Michael Meyer presented the state of the art on generating SQIsign-friendly primes and reported on the searches that have been run for the current NIST submission. Lorenz Panny and Antonin Leroux gave nice presentations on the effective Deuring correspondence, both in the general case and in the specific case of SQIsign. When asked how optimistic he is about SQIsign’s potential for standardization, Antonin gave a pretty pessimistic answer. Benjamin Wesolowski came to the rescue giving the audience some hope back with his presentation on SQIsignHD, the SIDH-attacks-based variant of SQIsign that promises much simpler and faster (and slightly shorter) signatures at the cost of a considerably more complex verification. Gustavo Banegas explained how to implement all of this in (maybe) constant time. Continuing on the “using SIDH attacks for good” topic, we had talks by Giacomo Pope on algorithms for computing isogenies between products of elliptic curves, and by Luciano Maino on using the SIDH attacks for making a PKE scheme named FESTA.

In the vanishingly small set, Peter Kutas gave a nice talk on a quantum break of pSIDH, an obscure (and totally impractical) key exchange that had always looked too risky to be true. More than by the breaking of pSIDH, I was impressed by the underlying technique. In past work, Peter and coauthors had defined a group action of GL₂ on the set of j-invariants at a certain distance from a starting curve, and used that to give a subexponential quantum attack (essentially, Kuperberg) on overstretched variants of SIDH. I wasn’t impressed at the time, given that we already had classical attacks on overstretched SIDH. What’s new is that Peter & co. found a way to express the problem of breaking pSIDH as a hidden subgroup problem, where the ambient group is GL₂ and the hidden subgroup is a Borel subgroup. By sheer coincidence, this non-abelian HSP turns out to be solvable in quantum polynomial time! Interestingly, the same idea would apply to SIDH and M-SIDH too if only they contained enough torsion point information (pSIDH contains an arbitrary amount of torsion point information, and seems to have been invented on purpose to make this attack possible!). To me, this is a strong indication that M-SIDH should be set up with a starting curve of unknown endomorphism ring.

For a change of scenery, Ward Beullens presented his attacks on signature schemes based on alternating trilinear forms. The only connection with isogenies seems to be the appearance of nice volcano-like graphs when studying the case of dimension 9 (one among many parameter sets), however the explanation appears to have more to do with an abelian surface acting on some bilinear forms.

But all of the above can be easily found on eprint, and the audience of the blog was probably already familiar with many of the results. The surprise of the workshop were the talks by David Kohel and Chloe Martindale. Both reported on work in progress and in both cases the audience was left with a feeling that, despite the beautiful theory, some fundamental ingredient is still missing.

David talked about formal orientations of elliptic curves. In the spirit of his and Leonardo Colò’s pioneering work on orienting supersingular elliptic curves, they are now trying to give a sense to, and possibly make cryptography out of, attaching some endomorphism ring information to the formal group of an elliptic curve. The algebra looks quite different from what we have been used to so far, as there is essentially a unique endomorphism ring for all curves. David concluded on a rather disconsolate note, arguing that all useful information seems to be extremely hard to compute.

Chloe presented ideas about recasting SQIsign in the framework of Bruhat-Tits trees. Although most of it is about using different terminology for the same objects that appear in the Deuring correspondence, her hope is to push much of the complexity of SQIsign into the key generation, making signing blazing fast. However, she and Ross Bowden appear to be stuck at some lattice problem that would let them describe the way the Bruhat-Tits tree folds, and sent a cry for help.

Overall, SIAM AG was intense and fun, remaining one of my favorite conferences. There exist video recordings of all the sessions, and you may get a hand on them if you ask the speakers politely (I don’t think we were asked for authorization to publish, so I don’t expect them to ever become available on youtube, unfortunately).

— Luca De Feo