Here is a discussion thread for the second session of The Isogeny Club, where Bruno Sterner presents his talk titled: git commit -m “isogenies”
Abstract:
Supersingular isogeny graphs possess many properties that make it an interesting object to study mathematically as well as attempt to apply for cryptographic purposes. In this talk, Bruno will present one of these properties and showcase how it can be applied to construct a commitment scheme. This commitment scheme has strong security properties and doesn’t require random oracles.
If you’d want to do something similar in genus 2 using Richelot isogenies, what kind of problems would you get?
This is not necessarily a question for Bruno, but more in general to people who work more with genus 2. I think the graph is not (proven to be) Ramanujan, but its properties might still be good enough? Do we get more problems with backtracking, and can we avoid those by using this work by Castryck-Decru-Smith?
Like, what prevents us from just using the above hash function in the same construction as Bruno did?
You certainly could use genus 2 stuff in this setting, it was something that was suggested to me recently. If one wanted to do this sort of thing in that setting, the main ingredient needed is to understand how the mixing constant looks with respect to these graphs. It might be the case that one would need to do relatively more computation to obtain the same security guarantees given that these graphs are not Ramanujan. I’m sure there are people that can give a better understanding of this
I’d also say it’s not fully clear that taking good extensions in the (2,2)-graph is, well, a graph. By this I mean that, while locally it is clear which isogenies are allowed (those that avoid trivial loops), it may be possible that you cannot write down an adjacency matrix.
On the other hand, you also cannot write down an adjacency matrix for non-backtracking walks (they are not Markov chains as far as I know) but it is entirely possible to prove they have a quasi-uniform stationary distribution. Hence a possible first step would be to compute the stationary distribution of good extensions (I’d be surprised if it changed at all), then try to estimate the convergence rate and/or mixing constant.
As said by Enric above (and I should credit this observation to Benjamin Smith), the good extensions in the (2,2)-graph is not a subgraph. For example say you take a good extension from some surface A. Then if you take a walk that cycles back to A, it is not true that the good extensions from A will be the same. Indeed, the good extensions from a node depend on the previous step so if you have come into A from two different paths, the good extensions from A will not be the same. In this way, it is somewhat ill defined and hard to study. But, it would be interesting to determine whether the good extensions give you “good enough” mixing in the graph.
What if we take a variation of the (2, 2) graph? For example, instead of just superspecial \mathcal{A}, if we take as nodes \mathcal{A}_1 \xrightarrow{\varphi} \mathcal{A}_2 where \varphi is a (2, 2)-isogeny and the edges are the good extensions from \mathcal{A}_2 given \varphi?
