Tessera
Folgen

Damien Robert

@damienrobert.bsky.social

Researcher in algorithmic number theory, notably on abelian varieties and their moduli spaces, and their applications to elliptic and isogeny based cryptography

247 Posts296 Follower176 Folgt
Gro-Tsen@gro-tsen.bsky.social · last mo.

A long thread about variants of Kőnig's lemma in relation to computability theory, because this caused me a lot of headaches yesterday and today, so maybe this will clarify things for other people. 🧵⤵️ •1/32

Gro-Tsen@gro-tsen.bsky.social · last mo.

I posted a question of MathOverflow asking whether the line of research that sought to relate higher-order computability with computability on large countable ordinals died out post 1980, and if so, why. (I give several examples of such results.) mathoverflow.net/q/512688/17064

Relating higher-order computability and computably large countable ordinals

In the period going roughly from the late 1960's to early 1980's, a number of results appeared in computability that have roughly the following flavor, relating higher-order computability with

mathoverflow.net

Gro-Tsen@gro-tsen.bsky.social · 2mo ago

“How can we construct a non-Borel set explicitly?” is a fascinating question by @arula-ratnakar.bsky.social, and in fact we can do this by a diagonal argument that is deeply analogous to how we construct a noncomputable subset of ℕ, but sadly nowhere written clearly AFAICT.🧵⤵️ •1/17

Andrea Basso@andreavbasso.bsky.social · 3mo ago

New paper out 🎉 We introduce a new UPKE based on FESTA that supports unbounded updates and whose security is equivalent to FESTA! Our main result: a (four-dimensional) variant of FESTA has uniformly random public keys, which means that any random walk is a valid pk update.

ePrint Updates@eprint.ing.bot · 3mo ago

Updatable Public-Key Encryption from FESTA (Andrea Basso, Tako Boris Fouotsa, Fatna Kouider, Péter Kutas, Luciano Maino, Laurane Marco) ia.cr/2026/1014

Abstract. Updatable public-key encryption (UPKE) is a cryptographic primitive that was proposed for secure messaging to provide forward secrecy in public-key settings. It extends standard public-key encryption with a key-update mechanism that lets anyone update a receiver’s public key and issue a corresponding token for updating the secret key. Unlike traditional forward secrecy where all past messages should remain secure after a key leakage, UPKEs guarantee security only as long as at least one honest update has occurred. While classically-secure efficient instantiations of UPKE are known from Diffie-Hellman assumptions, constructing an UPKE scheme with updates remains an open problem. In this work, we propose an isogeny-based UPKE that relies on a dimension-four version of the FESTA public-key encryption scheme. It is practically efficient and supports an unbounded amount of updates. Moreover, we provide a formal security proof based on a problem in isogeny-based cryptography that has received considerable scrutiny.
Gro-Tsen@gro-tsen.bsky.social · 3mo ago

Despite this proof, I don't have much intuition about what this (or Scott's formula) really “means”. But it certainly shows that there are important differences between these two models of computability in higher types. See also this previous thread: 🔽

Gro-Tsen@gro-tsen.bsky.social · 4mo ago

So there ensued an informal discussion of the intuitive content and differences between the (Hyland) effective topos, the Kleene-Vesley topos, and Mulry's recursive topos, and what each one is good for. The sort of remarks you won't find in books. [See also: mathoverflow.net/q/495788/17064 ]

Gro-Tsen@gro-tsen.bsky.social · 4mo ago

I'm beginning to feel more and more that the meaning of the ‘∞’ in “∞-categories” is that you can only explain what an ∞-category is to someone who already knows what an ∞-category is.

Gro-Tsen@gro-tsen.bsky.social · 5mo ago

🔽 So, @jeanas.bsky.social and I are please to announce a new preprint in computability, in which we show that the Turing degrees can be embedded upside down in (what we call) the “Arthur-Nimue-Merlin degrees”. The paper opens with a riddle, which I hope will be of interest!

First page of the paper titled “An order-reversing embedding of Turing degrees into Arthur–Nimue–Merlin degrees” by Jean Abou Samra & David Alexander Madore, arXiv:2603.19946v1 [math.LO] 20 Mar 2026. Abstract reads as follows: «The Arthur–Nimue–Merlin degrees are a generalization of the Turing degrees introduced by Kihara as a tangible description of the partially ordered set of Lawvere–Tierney topologies on the effective topos (equivalently, subtoposes of the effective topos). They are defined in terms of a three-player game that introduces both angelic and demonic non-determinism into oracle queries. We construct an order embedding of the Turing degrees with their order reversed into the Arthur–Nimue–Merlin degrees, whose image we call the “co-Turing degrees”; we then study the order relationship of these co-Turing degrees with the (naturally embedded) Turing degrees within the Arthur–Nimue–Merlin degrees.» The opening paragraph of the introduction reads: «We begin with a riddle. King Arthur is desperate to know whether the Grail is in a particular French castle. He can ask arbitrary questions to the all-knowing mage Merlin, who promises to answer truthfully, but with a twist. Instead of merely answering “yes” or “no” in plain English, the mischievous Merlin provides a Turing machine, which halts if and only if the answer is “yes”. Can Arthur, a mere mortal limited by the Church–Turing thesis, find the Grail’s location before the end of days?»
arXiv math.LO Logic@mathlo-bot.bsky.social · 5mo ago

Jean Abou Samra, David Alexander Madore: An order-reversing embedding of Turing degrees into Arthur-Nimue-Merlin degrees https://arxiv.org/abs/2603.19946 https://arxiv.org/pdf/2603.19946 https://arxiv.org/html/2603.19946

Luca De Feo@bsky.defeo.lu · 5mo ago

We still have a few spots left at MaGIC! Registration closes this week... Hurry up if you want to be on top of all the latest news on Cryptographic Group Actions! magic-workshop.github.io

MaGIC 2026 - Marche Workshop on Group Actions in Cryptography

A workshop dedicated to the study of cryptographic group actions, a rapidly evolving area at the intersection of algebraic geometry, number theory, and post-quantum cryptography. The workshop will bri...

magic-workshop.github.io

Krijn Reijnders @krijn.isogeni.es · 5mo ago

Thomas and I looked at directed isogeny graphs! In dim 1, we often ignore directedness, as there are only 2 "problematic" curves. Not so in dim 2: we analyze the action of automorphisms on level structures and the resulting directed graphs. Crucial: Directed (2,2)-graphs looks Ramanujan after all!

ePrint Updates@eprint.ing.bot · 5mo ago

Expander properties of superspecial isogeny digraphs with level structure (Thomas Decru, Krijn Reijnders) ia.cr/2026/500

Abstract. Charles, Goren and Lauter proved that the supersingular ℓ-isogeny graph is a Ramanujan graph, which is an optimal expander. Jordan and Zaytman argued that this is no longer true in dimension two, but Florit and Smith showed that those graphs exhibit good expansion properties nonetheless. Castryck, Decru and Smith however have pointed out that the higher-dimensional analogue setting should only consider a subset of all edges, namely the paths corresponding to (ℓ^(k), ℓ^(k))-isogenies, so-called good extensions, instead of all (ℓ^(a), ℓ^(b), ℓ^(c), ℓ^(d))-isogenies in general, which contain bad extensions too. Such bad extensions lead to many small cycles in the graph, which are a cryptographic problem due to collisions and a graph-theoretic nuisance as these superfluous edges counteract part of the expansion properties. Restricting to good extensions makes the resulting graph directed, as outgoing edges now depend on the incoming edge. We study (ℓ, ℓ)-level surfaces and (ℓ)^(g)-isogeny digraphs restricted to good extensions for concrete small dimensions and degrees ℓ. These graphs exhibit excellent expander properties: by our heuristic evidence, they are Ramanujan graphs for all primes ℓ in dimension 1, and for ℓ = 2 in dimension 2. Our main conjecture implies that this would still be the case for ℓ = 3 in dimension 2, but not for any larger ℓ in dimension 2, or any ℓ in dimension 3 and up. Furthermore, we generalize the work of Florit and Smith from ℓ = 2 to general primes ℓ, by classifying all abelian surfaces with nontrivial automorphism groups and their actions on their maximal isotropic (ℓ, ℓ)−subgroups.
Luca De Feo@bsky.defeo.lu · 5mo ago

TL;DR: - SQIsign more general than initially thought. - More space for protocol design! - SQIsign NIST v2 still the best signature, by a small margin. Ilinca already foreshadowed some of this in www.youtube.com/watch?v=5tGb..., though that's a different POV we're still writing up.

ePrint Updates@eprint.ing.bot · 5mo ago

The SQInstructor: a guide to SQIsign and the Deuring Correspondence with level structures (Giacomo Borin, Luca De Feo, Guido Maria Lido, Sina Schaeffler) ia.cr/2026/493

Abstract. We explore the use of level structures to generalize the SQIsign signature scheme. We give a general framework where, given the public key and the commitment, the challenge is to exhibit an isogeny between them with an additional requirement, namely to map a chosen level structure to nother. We then instantiate the framework using 1-dimensional and 2-dimensional isogenies. In doing that we provide a new explicit Deuring correspondence for supersingular elliptic curves with level structures and solve new constrained norm equations.
Andrea Basso@andreavbasso.bsky.social · 5mo ago

We're organizing a workshop on cryptographic group actions bringing together the isogeny and code communities. The workshop is just before Eurocrypt, a quick train away from Rome in the beautiful Marche. Early registration ends this week, so grab your spot soon! magic-workshop.github.io

MaGIC 2026 - Marche Workshop on Group Actions in Cryptography

A workshop dedicated to the study of cryptographic group actions, a rapidly evolving area at the intersection of algebraic geometry, number theory, and post-quantum cryptography. The workshop will bri...

magic-workshop.github.io

Damien Robert@damienrobert.bsky.social · 6mo ago

Continuation and end of the thread started here: bsky.app/profile/dami... # Part 4: Speculations Previously: - Part 1: CSIDH bsky.app/profile/dami... - Part 2: SIDH bsky.app/profile/dami... - Part 3: MIKE bsky.app/profile/dami...

Damien Robert@damienrobert.bsky.social · 6mo ago

I am very happy to announce that thanks to the hard work of many people (The "MIKE Team"), we now have a working implementation in SageMath of MIKE (Module Isogeny Key Exchange).

Damien Robert@damienrobert.bsky.social · 8mo ago

Each time I try to use the nLab to look up something it is the same experience: the first sentence has ten words I don't understand, so I recursively open the corresponding links, and before long I end up with 100 tabs open, 30 research papers, and 15 different references to the books by Lurie...

nLab

ncatlab.org

Gro-Tsen@gro-tsen.bsky.social · 9mo ago

If anyone wants to learn a broad overview of computability theory and Turing degrees, I recommend Soare's 2016 book “Turing Computability: Theory and Applications” (not to be confused with his 1987 book, “Recursively Enumerable Sets and Degrees”, which is much denser!).

Gro-Tsen@gro-tsen.bsky.social · 9mo ago

I thought the notion of “sheaf for a Lawvere-Tierney topology” was a very complicated one, but I realized it's actually not so complicated, and it can be defined completely internally (i.e., you don't need to know what a topos is, just how constructive math works). •1/7