Isogeny based Constructions
In 2019, Luca de Feo et al [FMPS19] constructed a VDF based on isogenies of supersingular elliptic curves and pairing. Their construction is motivated by the BLS signature, which uses a bilinear pairing. [FMPS19].
For more information about elliptic curves and isogeny graph \(G_{F_q}(l)\), we refer the reader to see the Elliptic Curve chapter I wrote earlier.. Before continuing, we introduce some notations. Let \(l\) be a small prime. Let \(N\) be a large prime and \(p\) be another prime such that \(p+1\) is divisible by \(N\). For an elliptic curve \(E/\mathbf{F}\), define \(E[N]=\{P \in E | N_(P)=O\}\) where \(O\) is the infinity point. The definition and properties of Weil pairing can be found in [Unknown bib ref: BLS03]. In the construction, the authors consider the pairing \(e_N: E[N]\times E'[N] \rightarrow \mu_N\). As the authors stated in their paper, the main important property the pairing is that, for any curves \(E\), isogeny \(E \rightarrow E'\) and \(P \in E[N]\) and \(Q \in E'[N]\) we have \(e_N(P,\hat{\phi(Q)})=e_N(\phi(P),Q)\). Now we move to describe the VDF Construction.
\(\mathsf{Gen}(1^\lambda,t)\): The algorithm selects a supersingular ellpitic curve \(E/ \mathbb{F}\), then choose a direction of the supersingular isogeny graph of degree \(l\), then compute the isogeny \(\phi E \rightarrow E'\) of degree \(l^t\) and its dual isogeny \(\hat{\phi}\).
\(\mathsf{Eval}(Q)\): For a point \(Q \in E'[N]\cap E(\mathbf{F})\), outputs \(\hat{\phi(Q)}\).
\(\mathsf{Verify}(E,E',P,Q,\phi(P),\hat{\phi(Q)})\): Check that \(\hat{\phi(Q)} \in E[N]\cap E(\mathbf{F})\) and \(e_N(P,\hat{\phi(Q)})=e_N(\phi(P),Q)\).
The security of the VDF is based on the assumption that, to compute the isogeny the map \(\hat{\phi}\), we are expected to walk \(t\) times between some vertices in the isogeny graph \(G_{F_q}(l)\). Currently, there is no efficient algorithm to find shortcut between these vertices of the graph. Finally, while the VDF is isogeny-based, it is not completely quantum secure, due to of the relation \(e_N(P,\hat{\phi(Q)})=e_N(\phi(P),Q)\) of bilinear pairing. Since Shor's algorithm can break the pairing inversion problem [FMPS19], it can trivially recover the output \(\hat{\phi(Q)}\) from the relation above.