## May 2020, What’s new?

Things have been quiet on this blog lately. As with everyone else on the planet, I have been distracted by COVID-19 and its impact on academic and family life. But I have decided it is time to write something.

Hopefully the next post will not be too far behind: EUROCRYPT is coming up next week, as an online conference. I plan to report on some of the activities that take place (although it is mostly taking place in the middle of the night with respect to my time-zone).

In the meantime, I thought I would mention some recent isogeny papers that I like.

• Craig Costello and Ben Smith, The Supersingular Isogeny Problem in Genus 2 and Beyond, PQCrypto 2020.

Supersingular abelian varieties of dimension $d > 1$ are isogenous to a product of supersingular elliptic curves. Superspecial abelian varieties are isomorphic to a product of supersingular elliptic curves, though generally only as unpolarized abelian varieties.

If one considers the isogeny graph of superspecial abelian varieties of dimension $d$ then some vertices (isomorphism classes of polarized abelian varieties) are simple and some are products of abelian varieties of lower dimension with a product polarization. The idea of the paper is to use a set of “easily-identifiable distinguished vertices” in the isogeny graph, namely those corresponding to $E \times A$ where $E$ is a supersingular elliptic curve and $A$ is an abelian variety of dimension $d-1$.

This leads to an iterative approach to find an isogeny between two superspecial abelian varieties $A_1$ and $A_2$ of the same dimension $d$: Take random walks from each until hitting distinguished vertices of the form $E_i \times A_i'$ for $i \in \{1,2\}$. If one can compute isogenies $E_1 \to E_2$ and $A_1' \to A_2'$ then one can “lift” them to an isogeny $A_1 \to A_2$. Since we are reducing the dimension, the search problems to find the isogenies are in smaller spaces, and hence easier to find.

This is a really nice application of the structure of products with the space of polarized abelian varieties.

• Ali El Kaafarani, Shuichi Katsumata and Federico Pintore, Lossy CSI-FiSh: Efficient Signature Scheme with Tight Reduction to Decisional CSIDH-512, PKC 2020.

The paper is about digital signatures from isogeny problems. The SeaSign paper by De Feo and me contained a signature scheme in the random oracle model and also, in an appendix, a scheme based on lossy keys that would have tight security in the quantum random oracle model (based on a result by Kiltz, Lyubashevsky and Schaffner). The drawback is working with a massive class group and hence larger parameters.

This paper introduced a new way to get lossy keys, that is simpler and does not require such a large increase in parameters. I like the idea. Here is an analogy of the idea in the DLP setting.
Let the system parameters be $(g_1, g_2)$ in some group.
Suppose a user has private key $a$ and public key $(h_1,h_2) = (g_1^a,g_2^a)$.
Here is an interactive way to prove knowledge of $a$:

1. Prover chooses random $r$ and sends commitment $(t_1, t_2) = (g_1^r,g_2^r)$ to verifier.
2. Verifier responds with a challenge bit $c \in \{0,1\}$.
3. Prover replies with $s = r$ (if $c=0$) or $s = ar^{-1}$ (if $c=1$).
4. Verifier checks that $(g_1^s, g_2^s) = (t_1,t_2)$ if $c=0$, or $(t_1^s,t_2^s) = (h_1,h_2)$ if $c=1$.
5. Repeat.

One can see that this makes sense as a proof of knowledge, and can be turned into a signature scheme using the Fiat-Shamir transform.

The lossy key setting is to choose a random pair $(h_1,h_2)$ as a “lossy public key”, in which case one can see that there is not a single $s$ that works for each $r$. The indistinguishability of real and lossy keys is the computational assumption.

Unlike the lossy keys scheme in the SeaSign paper, this approach does not need such large parameters.

• Daniel J. Bernstein, Luca De Feo, Antonin Leroux and Ben Smith, Faster computation of isogenies of large prime degree, to appear at ANTS.

Computing degree $d$ isogenies essentially boils down to evaluating some polynomials of degree $O(d)$ at some points. For example we have polynomials such as $f(x) = \prod_{i=1}^{(d-1)/2} (x - x( [i]P ))$

and wish to evaluate them on the $x$-coordinate of some points. The classical Vélu formulae compute this in $O(d)$ steps.

The starting point of the paper is the observation (going back to Pollard and Strassen) that there are fast methods to evaluate polynomials with a certain “structure” in their roots. The paper explains how to make this idea work for isogenies, using biquadratic polynpomials to encode the addition operation on a Montgomery model.

In short, the paper shows how to compute isogenies in $\tilde{O}( \sqrt{d} )$ operations. In practice, this approach becomes useful for $d \approx 200$, which means it could be useful for CSIDH, CSURF or BSIDH. The approach is not interesting for SIDH/SIKE.

• Samuel Jaques and André Schrottenloher, Low-gate Quantum Golden Collision Finding, eprint 2020/424.

This paper is about quantum algorithms for the claw-finding problem, which is a basic “meet-in-the-middle” approach to solving the computational problem behind SIDH/SIKE. More precisely, in a claw-finding problem we have functions $f : X \to Z, g : Y \to Z$ and seek $x \in X, y \in Y$ such that $f(x) = g(y)$. In SIDH, $X = Y$ corresponds to degree $2^{n/2}$ isogenies, and $f$ is taking an isogeny from $E$ while $g$ is taking an isogeny from $E_A$.

Two types of algorithm have previously been considered:

1. Tani’s algorithm. This was already mentioned in the original paper on SIDH by Jao and De Feo. A recent paper by Jaques and Schanck argued that managing the quantum random access storage in Tani’s algorithm would likely mean it performs less well that originally expected.

2. The van Oorschot and Wiener algorithm. This is a classical algorithm, whose relevance to SIDH was first noted by Adj, Cervantes-Vázquez, Chi-Domínguez, Menezes and Rodríguez-Henríquez. The main idea is to transform the problem of claw-finding into a collision-finding problem on the set $X$. The problem is that useless collisions arise, and so one needs to compute many collisions until finding a collision (the so-called “golden collision”) that solves the claw-finding problem.

The new paper considers variants of these quantum random walk algorithms. I’m still digesting the details. However, the conclusion is that SIDH/SIKE is still holding up well against quantum attack. The paper states “SIKE parameters still meet the NIST security levels claimed in their NIST submission.”

— Steven Galbraith

This entry was posted in Uncategorized. Bookmark the permalink.