Importance of supersingularity of elliptic curves

Question

I'm struggling to understand the high-level idea of "Verifiable Delay Functions from Supersingular Isogenies and Pairings" (https://eprint.iacr.org/2019/166.pdf) by De Feo et al.

I will shortly outline the construction (p.12):

setup:

1. (choose appropriate parameters)
2. Select a supersingular elliptic curve $E/\mathbb{F}_p$.
3. Choose a direction on the horizontal l-isogeny graph and compute a cyclic isogeny $\phi : E \rightarrow E'$ of degree $l^T$ and its dual.
4. Choose a generator P of X1 = $v^{-1}$($\tilde{E}[N] \cap \tilde{E}(\mathbb{F}_p)$) and compute $\phi(P)$.

eval:

5. Compute $\hat{\phi}(Q).$

verify:

6. Verify the condition ($e_N(P, \hat{\phi}(Q)) = e_N(\phi(P), Q)$) for the pairing $e_N$.

For step 2, I wonder: Why does the curve need to be supersingular? I think that it has a certain implication on the structure of the isogeny graph from $E$, but that is only my guess.

For step 3: I assume that we do a random walk on the isogeny graph. I think that means: for any elliptic curve $E_0$, we construct an isogeny, compute it, jump to the new curve $E_1$ and repeat this process. I wonder: Isogenies project points between curves, but their result isn't really a new curve. So how can we compute an isogeny from $E_1$ without really knowing it? Why is it important that the isogeny graph is "horizontal"? How can we prove that the isogeny actually takes T steps (.. which is necessary for the delay property of VDFs)? Or do we just publish all T intermediate isogenies? Why can we assume that all of them have order l?

The idea in step 5 and 6 looks clear to me: The condition (which is quick to evaluate) only holds for correctly computed isogenies, which can only be calculated with delay T.

Concerning P: $v : E \rightarrow \tilde{E}$ is defined as $(x,y) \rightarrow (u^2 x, u^3 y)$, $\tilde{E}$ is the quadratic twist of E. I understand that $E$ and $\tilde{E}$ are isomorphic, but I don't see why X1 is constructed in such a complicated way. Why can't we use the points on E as X1?

If my questions are too specific, I'd be more than happy for the explanation of supersingularity in this case! Would the construction also work for ordinary elliptic curves?

Answer 1

Your questions are a bit too rambly, so I'll just answer the title question. We use supersingular curves because ordinary curves don't have enough isogenies. Specifically, for supersingular curves, the graph of $\ell$-isogenies defined over $\mathbb{F}_{p^2}$ has good expansion properties. For ordinary curves, the graph of $\ell$-isogenies does not have good expansion properties. In most cases the latter graph is just a union of disjoint cycles. You can get graphs of ordinary isogenies with good expansion properties, but in order to do so you have to do something like take the union of $\ell$-isogeny graphs over various different $\ell$.