A New Class of Trapdoor Verifiable Delay Functions

Abstract

A verifiable delay function (VDF) is a function whose evaluation involves lengthy sequential operations, yet its outcome is publicly verifiable. As an extension, a trapdoor-VDF is a VDF with a shortcut that speeds up the evaluation process. This paper presents a new class of trapdoor-VDFs featuring a large ensemble of trapdoors for each instantiation of the function. This way, a client can randomly choose a private trapdoor from the ensemble, thereby using it to encapsulate a secret to the future as a unique puzzle. To solve the puzzle, the server, which does not know the trapdoor, requires a prescribed number of sequential steps to evaluate the function. Any client can efficiently verify the correctness of the server’s evaluation with zero knowledge of the trapdoor being used. We present an approach for constructing the proposed class of trapdoor-VDFs based on bilinear pairings and a long walk on supersingular isogeny graphs. Finally, we examine the security of our construction under trapdoor-VDF security notions.

1 Introduction

This work examines a remedy for the vulnerability that arises from knowing or predicting a protocol’s outcome. The vulnerability stems from malicious participants influencing the outcome or gaining an advantage by knowing the outcome beforehand. One way to solve this problem is to impose a prescribed number of sequential steps to obtain the desired outcome. This solution has been introduced in the previous works such as time-lock puzzle (TLP) [29], proofs of sequential work (PoSW) [1, 15, 22, 26], and verifiable delay functions (VDFs) [6]. These primitives are all time-sensitive in that they only release the outcome after a prescribed delay (T). The outcome of VDF and PoSW is publicly verifiable, while that of TLP requires a secret. The public verification of the outcome’s uniqueness is more efficient in VDF than in PoSW since the latter requires all T steps. The uniqueness property ensures that there are no multiple valid proofs for different outcome.

This work focuses more on the properties, specifically uniqueness and public verifiability, that make VDF stand out from others. Furthermore, we are interested in a VDF-like primitive that allows any participant (other than the trusted setup) to predict the outcome in advance by knowing a secret trapdoor. In the absence of the secret trapdoor, participants obtain the desired outcome through a prescribed number of sequential evaluations. It is, however, possible to verify the result efficiently and publicly. We refer to primitives with such characteristics by trapdoor-VDF. Considering its importance, trapdoor-VDF is suitable for time-sensitive applications that require both public verification and timely release assurances. There are many possible applications, such as sealed-voting, delayed decapsulation [9, 25], and front-running attack prevention [14].

Related Work. Since the work of Boneh et al. [6], several VDF constructions have been proposed based on Rivest, Shamir, and Wagner’s time-lock assumption [29], including [5, 17, 24, 28, 30], and [34], which use different verification techniques, provide additional properties and offer enhancement. Several other constructions [12, 18, 31] are based on the difficulty of shortening the evaluation of isogeny with a large degree, which was first introduced by [18]. The verification proof of [18] is based on the bilinear pairing of the Boneh-Lynn-Shacham (BLS) signature scheme [8]. Similar to time-lock functions, Shani’s [31] proof requires releasing a secret shortcut to the puzzle to recompute the puzzle’s answer. In [12], Chavez-Saab et al. propose an inefficient verification method based upon succinct non-interactive arguments (SNARGs).

Later, a delay encryption scheme [9] was developed using Boneh and Franklin’s identity based encryption (IBE) scheme [7] in conjunction with Feo et al.’s delay function [18]. The scheme in [9] can operate in batch mode so that the function can be evaluated once to perform many decryptions. However, the method requires a trusted, unpredictable seed, along with a considerable amount of storage to perform computations (e.g., 12 TB for 1 h delay [9]). Furthermore, their approach does not employ a trapdoor mechanism to predict the answer in advance. Hence, trapdoor-VDF is more comparable to TLP even though the former offers efficient public verification without revealing any secrets (i.e., the secret trapdoor). We note that recent work has extended the security of TLPs and discusses the notion of its public verifiability, some of which are [2, 3, 13, 20].

In addition, the term “trapdoor-VDF” has been used previously in [34], though their approach differs from that presented in this paper. In [34], each participant constructs independent instances of trapdoor-VDF. Every instance has a secret trapdoor that shortens the long evaluation process. Therefore, an instance generator can answer any challenge faster as it has the secret trapdoor. Our work presents a new class of trapdoor-VDFs, where each instantiation includes a description of a finite trapdoor ensemble. Hence, any participant can generate a unique challenge, together with its answer, using a hidden trapdoor sampled at random from the ensemble.

Contributions. In this paper, we first formalize the security notions of trapdoor-VDF. We then introduce a novel approach to trapdoor-VDF; the proposed trapdoor-VDF is a VDF with a large ensemble of distinct efficient shortcuts called trapdoors. The delay function involves sequentially evaluating a large smooth degree supersingular isogeny, which was first proposed by Feo et al. [18]. The trapdoor ensemble is a set of isogenies of a smaller degree defined over $\mathbb {F}_p$, where p is a prime. In public verification, a bilinear pairing equality serves as proof of the correct evaluation of a secret trapdoor (i.e., a randomly sampled isogeny). Finally, we show that our proposal is secure under trapdoor-VDF security notions.

2 Preliminaries

General Notations. If n is a positive integer, the set $\{1,\ldots ,n\}$ is denoted by [n]. In general, a finite set is denoted by calligraphic font (e.g., $\mathcal {S}$). The cardinality of a set $\mathcal {S}$ is denoted by $| \mathcal {S} |$. Let $e\leftarrow _R\mathcal {S}$ denote the process of uniformly sampling a random element e from $\mathcal {S}$. The deterministic selection of e from $\mathcal {S}$ is denoted by $e\leftarrow \mathcal {S}$. If $\textsf {Exe}$ is an algorithm, $a\leftarrow _R\textsf {Exe}$ denotes running $\textsf {Exe}$ on fresh random coins and assigning the output to a. The deterministic execution of $\textsf {Exe}$, on the other hand, is denoted by $a\leftarrow \textsf {Exe}$. The notation $\textsf {Pr}[ Evnt : P_1, P_2, \ldots ,P_n ]$ is used to represent the probability of an event Evnt occurring after the ordered processes $P_1, P_2, \ldots ,P_n$. We denote the composition of two functions by $\circ$ such that $\textsf {f}\circ \textsf {g}(x) =\textsf {f}(\textsf {g}(x))$ for some input x. Let $\boldsymbol{m} \leftarrow _R\mathcal {S}^{n}$ be the vector $(m_i)_{i\in [n]}$ of size n such that $m_i \leftarrow _R\mathcal {S}$ for all $i\in [n]$. The set of all odd prime numbers that are less than or equal to k is referred to as $\textsf {Primes}(k)$. For an integer a and an odd prime b, the Legendre symbol is denoted by $( \,\frac{a}{b}\,)$.

Supersingular Elliptic Curve. Throughout this work, we consider a curve $E/\mathbb {F}_p$ to be a supersingular elliptic curve defined over a prime field $\mathbb {F}_p$ with a large prime p. A point P on $E/\mathbb {F}_p$ is the pair $(x,y)\in \mathbb {F}_p\times \mathbb {F}_p$. The set of $\mathbb {F}_p$-rational points on $E/\mathbb {F}_p$ is denoted as $E(\mathbb {F}_p)$ and the set size as $| E(\mathbb {F}_p) |$. Let $\infty _E$ be the point at infinity on $E/\mathbb {F}_p$ and $\infty _E\in E(\mathbb {F}_p)$. The field $\overline{\mathbb {F}}_p$ is the algebraic closure of $\mathbb {F}_p$. The subgroup of points of order N is called the N-torsion points which is defined as $E[N]=\{P\in E(\overline{\mathbb {F}}_p): [N]P=\infty _E\}$.

Definition 1

([32]). An elliptic curve $E/\mathbb {F}_p$ is supersingular if the following equivalent properties are true

• There is no $P\in E(\overline{\mathbb {F}}_p)$ with order p (i.e., $E[p]= \{\infty _E \}$).

• $| E(\mathbb {F}_p) | = p+1-t$ and p|t (i.e., $\textsf {gcd}$(p, t)$\ne 1$).

• The endomorphism ring of $E/\overline{\mathbb {F}}_p$ is an order in a quaternion algebra.

Otherwise, $E/\mathbb {F}_p$ is said to be an ordinary curve.

Isogenous Curves. An isogeny between curves ($\phi : E_1 \rightarrow E_2$) is a surjective morphism that has a finite kernel such that $\phi (\infty _{E_1}) = \infty _{E_2}$. We say $\phi$ is defined over $\mathbb {F}_p$, if the non-constant rational map representing $\phi$ has coefficients in $\mathbb {F}_p$. Let $\langle S \rangle$ be a cyclic subgroup of $E(\overline{\mathbb {F}}_q)$ generated by S. In this work, we compute an isogeny $\phi$ with kernel $\langle S \rangle$ using Vélu’s formulas [33]. Also, we will focus on separable isogenies where the isogeny degree is its kernel size (i.e., $\deg \phi =| \textsf {ker} (\phi ) |$). An isogeny of degree l is denoted by l-isogeny. Furthermore, an isogeny ${\phi }$ has a unique dual isogeny $\hat{\phi }$ with the same degree ($\deg {\phi } = \deg {\hat{\phi }}$) such that $\hat{\phi } : E_2 \rightarrow E_1$, and $\phi \circ \hat{\phi } = [\deg {\phi }]$ on $E_2$, where [m] is multiplication-by m mapping (see [32, Theorem 6.1]). The non-backtracking walk is a sequence of isogenies that is not cyclic or followed by any dual isogeny(s).

The set of all group homomorphisms (i.e., isogenies) from E to itself is called the endomorphism ring of E (${\textbf {End}}(E)$). The endomorphism ring defined over $\mathbb {F}_p$ is denoted as ${\textbf {End}}_{\mathbb {F}_p}(E)$. An isogeny is called horizontal isogeny if ${\textbf {End}}_{\mathbb {F}_p}(E_1)\cong {\textbf {End}}_{\mathbb {F}_p}(E_2)\cong \mathcal {O}$ [21] where $\mathcal {O}$ is an order of an imaginary quadratic field. Furthermore, we donate the set of supersingular elliptic curves defined over $\mathbb {F}_p$ with $\mathcal {O}$ by $\mathcal {E}_{\mathbb {F}_p}(\mathcal {O})$. By definition, curves in $\mathcal {E}_{\mathbb {F}_p}(\mathcal {O})$ are connected by horizontal isogenies.

A Supersingular Isogeny Graph Over $\mathbb {F}_p$. The structure of a supersingular isogeny graph over $\mathbb {F}_p$ is studied by Delfs and Galbraith, which is described in [16, Theorem 2.7]. Let $\mathcal {L}$ be a set of distinct primes such that $p\not \in \mathcal {L}$, $( \,\frac{-p}{l_i}\,) =1$ for all $l_i\in \mathcal {L}$. For $p>3$, the graph $\mathcal {G}( \mathbb {F}_p,l_i )$ is a directed supersingular isogeny graph where the vertices are a $\mathbb {F}_p$-isomorphism classes of supersingular elliptic curves represented by j-invariants with an extra information to classify them into their $\mathbb {F}_p$-isomorphism class (i.e., to differentiate between elliptic curve twists). The graph edges are equivalence classes of $\mathbb {F}_p$-rational isogenies of a degree $l_i$. In our work, we employ a graph that represents the union of all $\mathcal {G}( \mathbb {F}_p,l_i ),\, \forall l_i\in \mathcal {L}$.

Isogeny and Pairing. Let N be a large prime such that $N\ne p$ and $N|| E_1(\mathbb {F}_p) |$. Let $\mu _N$ be the group of Nth roots of unity in $\mathbb {F}_{p^{u}}^*$, where u is the smallest integer such that $N|p^u-1$. The Weil pairing is the map $\hat{\textsf {e}}^{E}_N : E[N] \times E[N] \rightarrow \mu _N$ that satisfies several properties. In particular, the Weil pairing has the property of being compatible with isogenies (see [32, Proposition 8.2]); and it is trivial to show that

$$\begin{aligned} \hat{\textsf {e}}^{E_1}_N(P, [{\deg {\phi }]Q)} = \hat{\textsf {e}}^{E_2}_N(\phi (P), \phi (Q)), \end{aligned}$$

(1)

where $P\in E_1[N]$, $Q = \hat{\phi }(Q^{\prime })$ for $Q^{\prime }\in E_2[N]$, and $\phi \circ \hat{\phi } = [\deg {\phi }]$ on $E_2$.

3 Proposed Trapdoor-VDFs

By $\lambda \in \mathbb {N}$, we indicate the security level of a scheme. A function difficulty is denoted by T, which quantifies the amount of sequential work/steps necessary to produce/compute its output against any random input and with a polynomially large number of parallel processes. A function with a small T is identified as a short function, whereas one with a large T is called a long sequential function. Generally, we will denote the long sequential function by $\textsf {EVAL}$, with T being super-polynomial in $\lambda$.

An Informal Exposition. The proposed trapdoor-VDF is a VDF with a large ensemble of distinct shortcuts denoted by $\mathcal {F}$, called trapdoors. We say two trapdoors are equivalent if they produce the same output for the same inputs. The set of equivalent trapdoors is called a class. The class difficulty is the shortest trapdoor difficulty. Hence, the ensemble $\mathcal {F}$ is a collection of trapdoor classes.

Trapdoor-VDF Setup Agreement. Participants of a setup protocol agree on a long function $\textsf {EVAL}$ with a difficulty T, a large ensemble of trapdoors $\mathcal {F}$, and possibly additional parameters for a security level $\lambda$.

Generation of a Challenge. In trapdoor-VDF, a Challenger can select a secret trapdoor $\textsf {tr}_{sk}$ indexed (identified) in $\mathcal {F}$ by a random secret (sk). Using the trapdoor, the challenger can efficiently generate a challenge (${\textbf {c}}$) and its unique answer (${\textbf {a}}$). With the same parameters, distinct trapdoors produce different challenges (and accordingly different answers).

Obtaining the Answer. In the absence of sk, a Solver can only evaluate $\textsf {EVAL}$ function in time no less than T to output the answer to ${\textbf {c}}$ with a proof $\varPi$. Akin to VDF, the Solver gains no advantage from parallel computation. The Challenger can, however, get the answer ${\textbf {a}}$ via the trapdoor $\textsf {tr}_{sk}$ (i.e., in time less than T).

The Public Verification. The answer ${\textbf {a}}$ is publically verifiable that is also in a zero knowledge of the secret sk. In a timeframe less than T, a perfect trapdoor-VDF is one in which the Challenger, who owns ${\textbf {c}}$ and knows ${\textbf {a}}$, cannot pass the public verification protocol. This is because the required proof cannot be fully computed before the specific time T.

A Formal Definition. We present our formal definition of trapdoor-VDF, which naturally overlaps with [6] and [34]’s VDF definition.

Definition 2

Let $\mathcal {C}$, $\mathcal {S}$, $\mathcal {Y}$ be the challenge, secret, answer spaces, respectively. Our trapdoor-VDF is a tuple of algorithms ($\textsf {Setup}$, $\textsf {Challenger}$, $\textsf {Solver}$, $\textsf {Verify}$) defined below

• $\textsf {Setup}$: a randomized algorithm (runs in time $\textsf {Poly}(\lambda$)) that takes a security parameter $\lambda$ and a difficulty T and outputs public parameter pk.

• $\textsf {Challenger}$: a randomized algorithm (runs in time $\textsf {Poly}(\log T, \lambda$)) that takes pk and selects a secret trapdoor $\textsf {tr}_{sk}$ from the trapdoor ensemble $\mathcal {F}$ using a random secret sk (i.e., $\textsf {tr}_{sk}\leftarrow \mathcal {F}$ given $sk\leftarrow _R \mathcal {S}$); then, it generates a challenge ${\textbf {c}} \in \mathcal {C}$.

• $\textsf {Solver}$: an algorithm that takes pk and a challenge ${\textbf {c}} \in \mathcal {C}$ and outputs the answer ${\textbf {a}} \in \mathcal {Y}$ and a “possibly empty” proof $\varPi$. This algorithm must at least run in time T with $\textsf {Poly}(\lambda )$ parallel processors.

• $\textsf {Verify}$: is a deterministic algorithm (runs in total time polynomial in $\log T$ and $\lambda$) takes a challenge ${\textbf {c}}$, an answer ${\textbf {a}}$, a proof $\varPi$, and pk; the algorithm outputs $\textsc {accept}$ if ${\textbf {a}}$ is indeed the corresponding answer to ${\textbf {c}}$ under a given $\varPi$, otherwise $\textsc {reject}$.

Trapdoor-VDF Properties. The following assumes that all statements are true for any $\lambda$, T and $pk\leftarrow _R\textsf {Setup}(1^\lambda ,T)$. A trapdoor-VDF construction is well-defined if it is correct, unique, and efficient.

• Correctness: A trapdoor-VDF is correct only if the Verifier accepts, with probability one, an honest Solver’s answer ${\textbf {a}}$ for any honest challenge ${\textbf {c}} \leftarrow _R \textsf {Challenger}(pk)$.

• Uniqueness: A trapdoor-VDF is unique only if there is only one valid answer ${\textbf {a}}$, accepted by $\textsf {Verify}$, to every challenge ${\textbf {c}} \leftarrow _R \textsf {Challenger}(pk)$ with a secret sk.

• Efficiency: A trapdoor-VDF is efficient if the $\textsf {Verify}$ algorithm runs in a time $\textsf {Poly}(\log T,\lambda )$ that is significantly faster than the $\textsf {Solver}$ algorithm, which has a total running time polynomial in T and $\lambda$. Further, trapdoor-VDF must retain efficiency for any public parameters generated by $\textsf {Setup}$, runs in $\textsf {Poly}(\log T, \lambda )$, and any challenge generated by $\textsf {Challenger}$, which runs in time $\textsf {Poly}(\log T,\lambda )$.

Let $\mathcal {A}$ be a polynomially bounded adversary who has no knowledge of the secret sk. Let $\mathcal {A}_1$ be an algorithm that outputs pre-computation on pk. Let $\mathcal {A}_2$ be an online efficient evaluating algorithm that runs in parallel time with $\textsf {Poly}(\lambda )$ processors and returns an answer ${\textbf {a}} '$. Let $\mathcal {A}_3$ be an online forging algorithm that runs in time $\textsf {Poly}( T,\lambda )$ and returns a malicious answer and proof $( {\textbf {a}} '\ne {\textbf {a}} , \varPi ^{\prime })$. To be secure, a well-defined trapdoor-VDF should satisfy two key properties: sequentiality and soundness.

• Sequentiality: A trapdoor-VDF is sequential only if there is no adversary $\mathcal {A}:=(\mathcal {A}_1, \mathcal {A}_2)$ that has an online attack ($\mathcal {A}_2$) running in time less than T and has a probability of success

  $$ \textsf {Pr}\left[ \begin{array}{l} {\textbf {a}} ^\prime = {\textbf {a}} \end{array}:\begin{array}{l} pk\leftarrow _R \textsf {Setup}(1^\lambda ,T),\\ \textsf {pc} \leftarrow \mathcal {A}_1(pk),\\ {\textbf {c}} \leftarrow _R\textsf {Challenger}(pk),\\ ( {\textbf {a}} ^{\prime },-) \leftarrow \mathcal {A}_2(pk, {\textbf {c}} ,\textsf {pc}),\\ ( {\textbf {a}} ,\varPi )\leftarrow \textsf {Solver}(pk, {\textbf {c}} ). \end{array} \right] $$

  that is greater than a negligible function of $\lambda$.

• Soundness: A trapdoor-VDF is sound only if the Verifier rejects any proof $\varPi ^\prime$ for any answer ${\textbf {a}} ^\prime$ that is not an output from $\textsf {Solver}(pk, {\textbf {c}} )$ on any ${\textbf {c}} \leftarrow _R\textsf {Challenger}(pk)$. The probability of success for the adversary $\mathcal {A}:=(\mathcal {A}_1, \mathcal {A}_3)$ to output a proof $\varPi ^\prime$ for an answer $( {\textbf {a}} ^\prime , -) \ne \textsf {Solver}(pk, {\textbf {c}} )$ is

  $$ \textsf {Pr}\left[ \begin{array}{l} \textsc {accept}\leftarrow \textsf {Verify}(pk, {\textbf {c}} , {\textbf {a}} ^\prime , \varPi ^{\prime })\\ \text {and } {\textbf {a}} ^\prime \ne {\textbf {a}} \end{array}:\begin{array}{l} pk\leftarrow _R \textsf {Setup}(1^\lambda ,T),\\ \textsf {pc} \leftarrow \mathcal {A}_1(pk),\\ {\textbf {c}} \leftarrow _R\textsf {Challenger}(pk),\\ ( {\textbf {a}} ,\varPi )\leftarrow \textsf {Solver}(pk, {\textbf {c}} ),\\ ( {\textbf {a}} ^{\prime }, \varPi ^{\prime })\leftarrow \mathcal {A}_3(pk, {\textbf {c}} ,\textsf {pc}). \end{array} \right] $$

  that is a negligible function of $\lambda$.

Additionally, a well-defined trapdoor-VDF may comprise further properties, and one that is most relevant to our work is given below.

• Perfectness: The knowledge of $\textsf {tr}_{sk}$ and the pair $( {\textbf {c}} , {\textbf {a}} )$ solely does not provide an advantage in passing the public verification protocol. Let $\hat{\mathcal {A}}$ be an algorithm implementing $\textsf {Challenger}$, which outputs the pair (${\textbf {c}} , {\textbf {a}}$) and an algorithm $\hat{\mathcal {A}}_2$. The probability of success for $\hat{\mathcal {A}}_2$ to output an acceptable proof $\varPi ^\prime$, in time less than T, for any pair $( {\textbf {c}} , {\textbf {a}} )$ is

  $$ \textsf {Pr}\left[ \begin{array}{l} \textsc {accept}\leftarrow \textsf {Verify}(pk, {\textbf {c}} , {\textbf {a}} , \varPi ^{\prime })\\ \text {and } \textsc {accept}\leftarrow \textsf {Verify}(pk, {\textbf {c}} , {\textbf {a}} , \varPi ) \end{array}:\begin{array}{l} pk\leftarrow _R \textsf {Setup}(1^\lambda ,T),\\ ( {\textbf {c}} , {\textbf {a}} , \hat{\mathcal {A}}_2) \leftarrow \hat{\mathcal {A}}(\textsf {Challenger}, pk),\\ (-,\varPi ^{\prime }) \leftarrow \hat{\mathcal {A}}_2(pk, {\textbf {c}} , {\textbf {a}} ),\\ ( {\textbf {a}} ,\varPi )\leftarrow \textsf {Solver}(pk, {\textbf {c}} ).\\ \end{array} \right] $$

that is a negligible function of $\lambda$.

Further on Trapdoor-VDF Properties. A secure well-defined trapdoor-VDF accounts also for the trapdoor properties and assumption(s). This is due to the fact that a secure well-defined Challenger requires a secure well-defined trapdoor. Formally, a trapdoor $\textsf {tr}_{sk}\in \mathcal {F}$, associated with a domain $\mathcal {D}(\textsf {tr}_{sk})$ and range $\mathcal {R}(\textsf {tr}_{sk})$, is defined as follows

• $\textsf {tr}_{sk}$: a short function in $sk\leftarrow _R \mathcal {S}$, with evaluation time $\textsf {Poly}( \log T, \lambda$), that takes an input pk; the function evaluation returns a challenge and answer pair (${\textbf {c}} , {\textbf {a}} ) \in \mathcal {C}\times \mathcal {Y}$.

For any random secret $sk\leftarrow _R \mathcal {S}$ and $\textsf {tr}_{sk}\leftarrow \mathcal {F}$, the trapdoors in trapdoor-VDF feature several properties.

• Challenger correctness: Let $( {\textbf {c}} , {\textbf {a}} )$ be a challenge and its answer pair generated by $\textsf {tr}_{sk}$. The correctness property requires that the answer $( {\textbf {a}} ',-)\leftarrow \textsf {Solver}(pk, {\textbf {c}} )$ be equal to ${\textbf {a}}$ with probability one (i.e., we must have ${\textbf {a}} '= {\textbf {a}}$ with probability one). There is, however, an extension to the previous statement. For instance, we can allow ${\textbf {a}} '\ne {\textbf {a}}$ only if there is a one-way public function ($\textsf {f}$) such that ${\textbf {a}} \leftarrow \textsf {f}( {\textbf {a}} ')$ and $\textsc {accept}\leftarrow \textsf {Verify}(pk, {\textbf {c}} ,\textsf {f}( {\textbf {a}} '),\varPi )$ is true for all ${\textbf {c}} \in \mathcal {C}$ and all valid proofs $\varPi$. Having such an extension allows us to construct a prefect trapdoor-VDF in which the Challenger, who owns ${\textbf {c}}$ and knows ${\textbf {a}}$, cannot pass the public verification protocol before time T.

• Challenger efficiency: All trapdoors in a trapdoor-VDF must also be efficient. For any $\lambda$, T and $pk\leftarrow _R\textsf {Setup}(1^\lambda ,T)$, the efficiency implies that (as in [4]):

  • There is an algorithm that runs in time $\textsf {Poly}(\log T, \lambda$) and implements the process of sampling $\textsf {tr}_{sk}$ from $\mathcal {F}$ for all $sk \in \mathcal {S}$.

  • There is an algorithm that runs in time $\textsf {Poly}(\log T, \lambda$) and implements the process of sampling an element from $\mathcal {D}(\textsf {tr}_{sk})$ (and/or $\mathcal {R}(\textsf {tr}_{sk})$).

  • There is an algorithm that evaluates $\textsf {tr}_{sk}$ in time $\textsf {Poly}(\log T, \lambda$) for any element of $\mathcal {D}(\textsf {tr}_{sk})$.

• Challenger security: To be secure, the following problems must be hard for any $\lambda$, T and $pk\leftarrow _R\textsf {Setup}(1^\lambda ,T)$.

  • Given any challenge ${\textbf {c}} \in \mathcal {C}$ generated under the secret $\textsf {tr}_{sk}\in \mathcal {F}$, find the challenge’s answer ${\textbf {a}} \in \mathcal {Y}$ in time less than T.

  • Given any challenge and answer pair $( {\textbf {c}} , {\textbf {a}} )\in \mathcal {C}\times \mathcal {Y}$ generated by $\textsf {tr}_{sk}\in \mathcal {F}$, find $sk\in \mathcal {S}$.

  • Let $( {\textbf {c}} ', {\textbf {a}} ')\in \mathcal {C}\times \mathcal {Y}$ be any challenge and answer pair generated by $\textsf {tr}_{sk'}\in \mathcal {F}$. Given a challenge ${\textbf {c}} \in \mathcal {C}$ under $\textsf {tr}_{sk}\in \mathcal {F}$, find its answer ${\textbf {a}} \in \mathcal {Y}$.

Similar to VDF, the difficulty T is restricted to subexponential in $\lambda$. It is therefore cheaper to perform the T-sequential evaluation than to compromise the trapdoor-VDF security.

4 Design Rationale

This section discusses our approach to construct a proof-of-concept instance of trapdoor-VDF. To construct trapdoor-VDF, we begin by defining a long sequential public function $\textsf {EVAL}:\mathcal {X}\rightarrow \mathcal {X}$ with a public challenge and answer (i.e., $x,y\in \mathcal {X}$ such that $y\leftarrow \textsf {EVAL}(x)$). The secret is a random string ($sk\leftarrow _R \mathcal {S}$) that indexes a secret short map ($\textsf {tr}_{sk}:\mathcal {X}\rightarrow \mathcal {X}$) in the ensemble $\mathcal {F}$. Using a random secret map, one may craft a trapdoor. A new challenge ($x'$) can be obtained by masking x with $\textsf {tr}_{sk}$ (i.e., $x'\leftarrow \textsf {tr}_{sk}(x)$). The secret map $\textsf {tr}_{sk}$, which can also determine $y'\leftarrow \textsf {tr}_{sk}(y)$, becomes the trapdoor. This statement is true assuming that the action $\textsf {tr}_{sk}\circ \textsf {EVAL}$ is equivalent to $\textsf {EVAL}\circ \textsf {tr}_{sk}$. In the absence of $\textsf {tr}_{sk}$, one can obtain $y'$ by evaluating $y'\leftarrow \textsf {EVAL}(x')$, which involves a large number of sequential steps.

Lastly, the verification procedure involves validating $\textsf {tr}_{sk}$’s correct computation statement with zero knowledge of $\textsf {tr}_{sk}$, where the Solver’s answer ($y''$) serves as the statement witness. The validation arguments should be efficient, validating only the unique answer (i.e., a Verifier accepts only if $y''=y'$).

In the following, we present a sketch construction of the proposed trapdoor-VDF. Essentially, the construction consists of evaluating a series of non backtracking horizontal isogenies with a large degree (representing $\textsf {EVAL}$), whereas the secret trapdoor is a shorter horizontal isogeny walk in graphs over a finite field $\mathbb {F}_p$ (representing $\textsf {tr}_{sk}$). Our public verification protocol uses bilinear pairings similar to BLS signature scheme [8], which is also used in [9] and [18].

4.1 Construction Elements

First, we define the public parameters that we will use to construct our scheme. Following that, we will briefly describe the supersingular isogeny graph, upon which both the long evaluation function and short trapdoor operate. Lastly, we will discuss the scheme group structure and the scheme’s public verification method.

Selection of the Scheme Parameters. The parameters for our scheme are generated with the help of the following algorithms.

• $(p, \mathcal {L}, N, \mathcal {S}, \boldsymbol{t} , E_0)\leftarrow \textsf {GGen}(1^\lambda ,T)$ is a public parameter generation algorithm that takes a security parameter $\lambda$ and difficulty T as an input and outputs:

  • a large odd prime p such that $p=7\bmod 8$,

  • a set $\mathcal {L}$ of n small distinct primes defined as follow

    $$\begin{aligned} \mathcal {L}:=\{2\}\cup \{l\in \textsf {Primes}( 6\log (p)^2) : ( \,\frac{-p}{l}\,) =1 \}, \end{aligned}$$

  • a large prime N such that $N\not \in \mathcal {L}$ and $N\mid p+1$,

  • the set $\mathcal {S}:=\{-e,\ldots , e\}$ for a positive integer e where $| \mathcal {S} |=2e+1$,

  • the vector $\boldsymbol{t} \leftarrow \mathcal {T}^n$ of n elements, where $\mathcal {T}:= \{-{\lceil }\frac{m_{\text {max}}}{n}{\rceil },\ldots , {\lceil }\frac{m_{\text {max}}}{n}{\rceil }\}$, $\sum _{m\in \boldsymbol{t} } \textsf {abs}(m) = T<2^{o(\lambda )}$, and a positive integer $m_{\text {max}}< 2^{o(\lambda )}$,

  • a supersingular elliptic curve $E_{0} /\mathbb {F}_p$ on the surface of $\mathcal {G}( \mathbb {F}_p,2 )$, where $| E_{0} (\mathbb {F}_p) |= p+1$ and possibly with j-invariant $\textsf {j}( E_{0} ) \in \{0,1728\}$.

• $E\leftarrow _R \textsf {Alg}(1^\lambda , E',\mathcal {L})$ is a randomized algorithm that takes an initial curve $E'$, the set $\mathcal {L}$, and security parameter $\lambda$. The algorithm $\textsf {Alg}$ outputs a random supersingular elliptic curve $E/\mathbb {F}_p$ on the graph surface. Basically, this algorithm involves taking a random horizontal isogeny walk (see [18]) of a length of at least $\textsf {Poly}(\log p)$. It is required that the probability of finding isogeny (path) between the output curve E and an initial curve $E'$ be a negligible function in $\lambda$.

4.2 The Graph in Use and the Single Step of Computation

The graph over $\mathbb {F}_p$ described in [16, Theorem 2.7] is the abstraction behind our scheme. In our scheme, the graph consists of two levels, namely a surface (i.e., $\mathcal {E}_{\mathbb {F}_p}(\mathbb {Z}[\frac{1+\sqrt{-p}}{2}])$) and a floor (i.e., $\mathcal {E}_{\mathbb {F}_p}( \mathbb {Z}[\sqrt{-p}])$). In this graph, surface and floor have one-to-one connection by 2-isogenies, and there are no odd-degree isogenies connecting them. On the graph surface, there are two horizontal isogenies of degree $l_i\in \mathcal {L}$ from each vertex, whereas the floor is connected by isogenies of degree $l_i\in \mathcal {L}/\{2\}$.

In our construction, a sequential walk on the graph is represented by the group action of the ideal class group ${\textbf {cl}}(\mathcal {O})$ of an imaginary quadratic order $\mathcal {O}\cong \mathbb {Z}[\frac{1+\sqrt{-p}}{2}]$ on the set $\mathcal {E}_{\mathbb {F}_p}(\mathcal {O})$. Hence, both $\textsf {EVAL}$ and $\textsf {tr}_{sk}$ act on the set $\mathcal {E}_{\mathbb {F}_p}(\mathcal {O})$. The choice of $\mathcal {L}$’s elements enables us to represent the elements of ${\textbf {cl}}(\mathcal {O})$ as a product of ideals of small norm $\textsf {N}(\mathfrak {l})$ such that $\textsf {N}(\mathfrak {l})\in \mathcal {L}$. Thus, we represent a single step in the sequential walk by the group action of an ideal of a norm in $\mathcal {L}$ that acts on $\mathcal {E}_{\mathbb {F}_p}(\mathcal {O})$.

The elements of $\mathcal {L}$ are chosen to be Elkies primes. Hence, the ideal $l_i\mathcal {O}$ splits into $\mathfrak {l}_i=(l_i,\pi -1)$ and $\hat{\mathfrak {l}}_i=(l_i,\pi +1)$ for every $l_i\in \mathcal {L}$ (i.e., $l_i\mathcal {O}=\mathfrak {l}_i\hat{\mathfrak {l}}_i, \forall l_i\in \mathcal {L}$). This defines the direction of a single step. From every vertex in the graph surface, there are two actions of an ideal with norm $l_i$ that can be applied, either $\mathfrak {l}_i$ or $\hat{\mathfrak {l}}_i$. Further, each direction can be computed via an isogeny using Vélu’s formulas [33]. In other words, a single step in one direction, denoted by $\phi _{l_i}$, is an isogeny of a kernel of order $l_i$ intersecting with $\textsf {ker} (\pi -[1])$. As for the step in the opposite direction, denoted by $\phi ^{-1}_{l_i}$, represents an isogeny of a kernel of order $l_i$ intersecting with $\textsf {ker} (\pi +[1])$. Finally, for an integer $m_i$, we denote $l_i$-sequential walk by $\phi ^{m_i}_{l_i}$, which represents $m_i$ sequences of $l_i$-isogeny evaluation in the same direction.

The Long Evaluation Function. As with [18] and [31], the long evaluation is represented by an isogeny of large degree, exponential in T,

$$\begin{aligned} \textsf {EVAL}:= \phi ^{ \boldsymbol{t} }_{\mathcal {L}} : E_{} \rightarrow E_{A}\end{aligned}$$

which is a composite of all $\phi ^{ m_i}_{l_i}$ for all $l_i\in \mathcal {L}$ and $m_i\in \boldsymbol{t}$ (i.e., $\phi ^{ \boldsymbol{t} }_{\mathcal {L}} := \phi ^{ m_n}_{l_n}\circ _{n}\cdots \circ _1\phi ^{ m_1}_{l_1}$, where $m_i\in \boldsymbol{t}$ and $| \boldsymbol{t} |=n$). The degree of $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$ is $\prod ^{n}_{i=1}l^{\textsf {abs}(m_i)}_i$ and it has a difficulty of $\sum ^{n}_{i=1} \textsf {abs}(m_i)=T$. The presumption is that to compute $\textsf {EVAL}$ efficiently, all T composites of $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$ must be evaluated sequentially.

The Secret Trapdoor and Secret Trapdoor Set. As with [11, 31], we want to be able to efficiently sample a random trapdoor from their ensemble $\mathcal {F}$. We will therefore randomly sample $sk:= \boldsymbol{s} \leftarrow _R\mathcal {S}^{n}$ to represent the trapdoor as

$$\begin{aligned} \textsf {tr}_{sk}:= \phi ^{ \boldsymbol{s} }_{\mathcal {L}} : E_{} \rightarrow E_{B}. \end{aligned}$$

The set $\mathcal {S}$ is chosen so that the trapdoor $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$ is much shorter than $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$. However, the size of $\mathcal {S}$ must be large enough to ensure that there exist $|\mathcal {S}|^{n}\ge 2^{2\lambda }$ possible secrets.

4.3 The Scheme Group Structure and Its Public Verification

Let ${G}_{i}^{ E_{} }$ be a subgroup of $E_{} [N]$ where $E_{} \in \mathcal {E}_{\mathbb {F}_p}(\mathcal {O})$ and $i \in [N]$. The trace-zero and the base-field subgroup of $E_{} [N]$ are represented by subscripts 1 and 2, respectively¹. Under the assumption that (i) N is coprime to $| \textsf {ker} ( \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ) |$ and $N\ne p$, and (ii) $E_{}$ and $E_{A}$ are isogenous (so that $| E_{} [N] |=| E_{A}[N] |$), the surjective morphism $\phi ^{ \boldsymbol{t} }_{\mathcal {L}} : E_{} [N]\rightarrow E_{A}[N]$ must also be injective induced by the Lagrange’s theorem; hence it is a bijective group homomorphism on the N-torsion subgroup (similar argument applies for $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$). Let $\sigma ^{-1}$ be a quadratic twist defined as follows

$$\begin{aligned} \sigma ^{-1}&: E_{} \rightarrow E^{(d)}_{}\in \mathcal {E}_{\mathbb {F}_p}(\mathcal {O}) \\ \sigma ^{-1}&: {G}_{i\in \{1,2\}}^{ E_{} } \rightarrow {G}_{2i \bmod 3}^{ E^{(d)}_{}} \end{aligned}$$

where $E^{(d)}_{}$ is a twist of the curve $E_{}$. The inverse quadratic twist (i.e., $\sigma : E^{(d)}_{}\rightarrow E_{}$) is efficiently computable and it is defined as follows

$$\sigma :(x,y) \rightarrow (x/w^2, y/w^3) $$

where $w\in \mathbb {F}_{p^{2}}$, $w\not \in \mathbb {F}_p$, and it has $w^2\in \mathbb {F}_p$. In our configuration, it should be noted that $\sigma \circ \phi ^{m_i}_{l_i}(E)$ and $\phi ^{-m_i}_{l_i}\circ \sigma (E)$ are equivalent.

Pairing Based Public Verification in a Nutshell Let $\hat{\textsf {e}}^{ E_{} }_N: E_{} [N] \times E_{} [N] \rightarrow \mu _N$ be a non-degenerate Weil pairing map on $E_{}$, where $\mu _N\subset \mathbb {F}_{p^{2}}^*$. A non-trivial bilinear Weil pairing can be defined as $\hat{\textsf {e}}^{ E_{} }_N: {G}_{1}^{ E_{} } \times {G}_{2}^{ E_{} } \rightarrow \mu _N$. This definition is equivalent to $\hat{\textsf {e}}^{ E_{} }_N: \sigma ( {G}_{2}^{ E^{(d)}_{}} )\times {G}_{2}^{ E_{} } \rightarrow \mu _N$, which is efficiently computable with inputs of short representation. Let $E_{} ,\, E_{A}= \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( E_{} ),\, E_{B}= \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( E_{} ),\, E_{AB}= \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( E_{A}),$ and $E_{BA}= \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( E_{B})$ be a set of isogenous supersingular elliptic curves. The public verification proceeds as follows:

• A Challenger, Verifier, and Solver all share as an input the description of the isogeny $\phi ^{ \boldsymbol{t} }_{\mathcal {L}} : E_{} \rightarrow E_{A}$ of difficulty T, and the point pair $( x^{ {G}_{1}^{ E_{} } } , y^{ {G}_{1}^{ E_{A}} } )\in {G}_{1}^{ E_{} } \times {G}_{1}^{ E_{A}}$ such that $y^{ {G}_{1}^{ E_{A}} } = \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( x^{ {G}_{1}^{ E_{} } } )$. All inputs are chosen for a security parameter $\lambda$.

• A Challenger selects $\boldsymbol{s} \leftarrow _R\mathcal {S}^{n}$ that defines the secret short isogeny $\phi ^{ \boldsymbol{s} }_{\mathcal {L}} : E_{} \rightarrow E_{B}$; then, it

  • randomly samples integers $k_A$, $k_B$, and $k_{AB}$ such that $k_Ak_B^{-1} k_{AB}^{-1} =\deg \phi ^{ \boldsymbol{s} }_{\mathcal {L}} (\bmod {N})$,

  • computes and broadcasts the challenge $([k_A] Q^{ {G}_{2}^{ E_{A}} }_{ } , \hat{x}^{ {G}_{1}^{ E_{B}} } , Q^{ {G}_{2}^{ E_{AB}} }_{ } )\in$ ${G}_{2}^{ E_{A}}$ $\times$ ${G}_{1}^{ E_{B}}$ $\times {G}_{2}^{ E_{AB}}$ such that $\hat{x}^{ {G}_{1}^{ E_{B}} } = [k_B] \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( x^{ {G}_{1}^{ E_{} } } )$, $Q^{ {G}_{2}^{ E_{A}} }_{ } \leftarrow _R {G}_{2}^{ E_{A}}$, and $Q^{ {G}_{2}^{ E_{AB}} }_{ } = [k_{AB}] \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( Q^{ {G}_{2}^{ E_{A}} }_{ } )$.

• A Solver computes the answer $\hat{y}^{ {G}_{1}^{ E_{BA}} } \leftarrow \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( \hat{x}^{ {G}_{1}^{ E_{B}} } )$, which requires T sequential isogeny evaluations, and then broadcasts $\hat{y}^{ {G}_{1}^{ E_{BA}} }$.

• A Verifier outputs $\textsc {accept}$ if $\hat{y}^{ {G}_{1}^{ E_{BA}} }$ satisfies the following equality

  $$\begin{aligned} \hat{\textsf {e}}^{ E_{A}}_N( y^{ {G}_{1}^{ E_{A}} } , [k_A] Q^{ {G}_{2}^{ E_{A}} }_{ } ) = \hat{\textsf {e}}^{ E_{AB}}_N( \hat{y}^{ {G}_{1}^{ E_{BA}} } , Q^{ {G}_{2}^{ E_{AB}} }_{ } ), \end{aligned}$$

  (2)

  otherwise returns $\textsc {reject}$.

From Eq. (1), the above-mentioned verification is complete, as shown below.

$$\begin{aligned} \begin{array}{rl} \hat{\textsf {e}}^{ E_{A}}_N( y^{ {G}_{1}^{ E_{A}} } , [k_A] Q^{ {G}_{2}^{ E_{A}} }_{ } ) &{}= \hat{\textsf {e}}^{ E_{AB}}_N( \phi ^{ \boldsymbol{t} }_{\mathcal {L}} \circ [k_B] \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( x^{ {G}_{1}^{ E_{} } } ), [k_{AB}] \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( Q^{ {G}_{2}^{ E_{A}} }_{ } )),\\ \hat{\textsf {e}}^{ E_{A}}_N( y^{ {G}_{1}^{ E_{A}} } , [{\deg \phi ^{ \boldsymbol{s} }_{\mathcal {L}} }] Q^{ {G}_{2}^{ E_{A}} }_{ } ) &{}= \hat{\textsf {e}}^{ E_{AB}}_N( \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( y^{ {G}_{1}^{ E_{A}} } ), \phi ^{ \boldsymbol{s} }_{\mathcal {L}} ( Q^{ {G}_{2}^{ E_{A}} }_{ } )). \end{array} \end{aligned}$$

Moreover, it is obvious that the correctness of the scheme depends on the terminal elliptic curves (i.e., $E_{AB}$ and $E_{BA}$) being identical. To be consistent with previous work [18], Fig. 1 shows the proof system’s structure.

Fig. 1.

The diagram illustrates the structure of the proposed trapdoor-VDF’s proof system. The map $\phi ^{- \boldsymbol{t} }_{\mathcal {L}}$ is the $\mathcal {L}$-sequential walk $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$ in the opposite direction (and similar for $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$).

4.4 An Instance of the Trapdoor-VDF

The following is a formal description of a trapdoor-VDF instance constructed from the action of class groups on supersingular elliptic curves with bilinear pairings being used for public verification. They are all defined by the parameters chosen in the previous section.

Fig. 2.

The proposed trapdoor-VDF instance is defined by the four algorithms described above.

Discussion. It is imperative that a trusted process runs $\textsf {Setup}$ due to an attack that exploits an elliptic curve with known endomorphism rings (see [18]). To generate the public parameters, the $\textsf {Setup}$ must select $E_{}$ and then compute $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$, which takes O(T) steps. A $\textsf {Challenger}$ must sample a one-time secret $\boldsymbol{s}$ to compute $\hat{x}^{ {G}_{1}^{ E_{B}} }$ and $Q^{ {G}_{2}^{ E_{AB}} }_{ }$, with the evaluation time being a polynomial function in $\lambda$. Essentially the challenge consists of three elliptic curve points. To obtain the answer, the $\textsf {Solver}$ must compute $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$, which is a separable isogeny of a degree exponential in T. Typically, the best approach for computing $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$ is to sequentially compute each of its T compositions, of degrees $l_i\in \mathcal {L}$, using Vélu’s formulas. A single point on the target curve $E_{BA}$ serves as both the answer and the proof. The verification involves two bilinear pairings. It also involves determining whether all points are members of the appropriate group, a relatively trivial operation.

5 Security

We will show that the trapdoor-VDF proposed in Sect. 4.4 is secure well-defined with an honest challenge and the aforementioned setup that takes O(T) steps.

Theorem 1

The trapdoor-VDF instance in Sect. 4.4 is a secure well-defined trapdoor-VDF with a O(T) steps long $\textsf {Setup}$ and under the assumption of an honest Challenger.

Correctness, and Uniqueness. The following assumes that all statements are true for any $\lambda$, T, $pk\leftarrow _R\textsf {Setup}(1^\lambda , T)$. For all honest ${\textbf {c}} \leftarrow _R \textsf {Challenger}(pk)$, the correctness argument implies that any honest evaluator should be able to obtain the answer ${\textbf {a}} \leftarrow \textsf {Solver}(pk, {\textbf {c}} )$ which is $\textsf {Verify}$’s acceptable answer.

However, the correctness argument is not complete yet. We also require that the $\textsf {Challenger}$ and $\textsf {Solver}$ must land on the same terminal elliptic curve and not only curves on the same isomorphism class. In other words, the evaluation output ($\phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( {\textbf {c}} . \hat{x}^{ {G}_{1}^{ E_{B}} } )$) and the challenge (${\textbf {c}} . Q^{ {G}_{2}^{ E_{AB}} }_{ }$) have to be on the same curve (i.e., $E_{BA}= E_{AB}$). This is required so that the Verifier can evaluate Eq. (2). The verification in Eq. (2) is likewise unique, as we employ a similar version of the [8]’s (and [18]) verifier.

Lemma 1

Given any $\lambda$, T, and $pk\leftarrow _R\textsf {Setup}(1^\lambda , T)$, a Solver’s honest output ${\textbf {a}} . \hat{y}^{ {G}_{1}^{ E_{BA}} }$ is indeed a point on the Challenger’s terminal curve ($E_{AB}$) such that ${\textbf {a}} . \hat{y}^{ {G}_{1}^{ E_{BA}} } = \hat{y}^{ {G}_{1}^{ E_{AB}} }$ and $\textsc {accept}\leftarrow \textsf {Verify}(pk, {\textbf {c}} , {\textbf {a}} )$, for all honest ${\textbf {c}} \leftarrow _R \textsf {Challenger}(pk)$; further, there is no answer ${\textbf {a}} '$ that is a valid answer (i.e., $\textsc {accept}$ $\leftarrow \textsf {Verify}( pk, {\textbf {c}} , {\textbf {a}} ')$) unless ${\textbf {a}} '= {\textbf {a}} = \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( {\textbf {c}} . \hat{x}^{ {G}_{1}^{ E_{B}} } )$.

Proof

The proof to the first part of the lemma follows from the result of Leonardi [23, Theorem 3.1]. Leonardi’s result implies the equivalency between the action of $\phi ^{ \boldsymbol{s} }_{\mathcal {L}} \circ \phi ^{ \boldsymbol{t} }_{\mathcal {L}}$ and $\phi ^{ \boldsymbol{t} }_{\mathcal {L}} \circ \phi ^{ \boldsymbol{s} }_{\mathcal {L}}$ when all computed with Vélu’s formulas. As for the uniqueness, we have set our parameters so that (i) as mentioned in Sect. 4.3, the surjective morphism $\phi ^{ \boldsymbol{t} }_{\mathcal {L}} : E_{B}[N]\rightarrow E_{BA}[N]$ is a group isomorphism on the N-torsion subgroup and (ii) as discussed in [18], Eq. (2)’s right-hand side is a group isomorphism from ${G}_{1}^{ E_{BA}}$ to $\mu _N$ for a given ${\textbf {c}} . Q^{ {G}_{2}^{ E_{AB}} }_{ }$. Hence, $\textsf {Verify}((pk, {\textbf {c}} ), {\textbf {a}} ')$ outputs $\textsc {accept}$ if and only if ${\textbf {a}} '= {\textbf {a}} = \phi ^{ \boldsymbol{t} }_{\mathcal {L}} ( {\textbf {c}} . \hat{x}^{ {G}_{1}^{ E_{B}} } )\in {G}_{1}^{ E_{BA}}$.

Soundness. Since there is only one valid answer, the verification is unique, as is a property of [8]’s verifier. Thus, and similar to [18], our trapdoor-VDF is perfectly sound.

Sequentiality. In the following, we introduce the concept of sequentiality in our trapdoor-VDF by presenting the shortcut game.

Definition 3

(The shortcut game). Let $\lambda$ and T be a security and a difficulty parameters, respectively. Let $\mathcal {A}:= (\mathcal {A}_1,\mathcal {A}_2)$ be a party that participates in the following game. (i) A trusted process computes and publishes $pk\leftarrow _R \textsf {Setup}(1^\lambda ,T)$, (ii) $\mathcal {A}$ preforms a pre-computation in time $\textsf {Poly}(T,\lambda )$ and outputs $\textsf {pc}\leftarrow \mathcal {A}_1(pk)$, (iii) a trusted process then computes and publishes ${\textbf {c}} \leftarrow _R \textsf {Challenge}(pk)$, (iv) $\mathcal {A}$ computes and outputs $\hat{y}^{ {G}_{1}^{ E_{BA}} } \leftarrow \mathcal {A}_2(pk, {\textbf {c}} , \textsf {pc})$ in parallel time less than T, where $\hat{y}^{ {G}_{1}^{ E_{BA}} } \in {G}_{1}^{ E_{BA}}$.

To win the game, $\mathcal {A}$’s output, $\hat{y}^{ {G}_{1}^{ E_{BA}} }$, is required to be the correct evaluation of $\phi ^{pk. \boldsymbol{t} }_{pk.\mathcal {L}}$ on ${\textbf {c}} . \hat{x}^{ {G}_{1}^{ E_{B}} }$ (i.e., to be equal to ${\textbf {a}} \leftarrow \textsf {Solver}(pk, {\textbf {c}} )$).

The proposed trapdoor-VDF is sequential if there is no polynomially bounded player $\mathcal {A}$ with a non-negligible probability of winning the above shortcut game. A player $\mathcal {A}$ can win the game by finding (i) a shorter isogeny than $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$, (ii) a faster method for computing $\phi ^{ \boldsymbol{t} }_{\mathcal {L}}$, (iii) the inverse of pairing Eq. (2), or (iv) the secret isogeny $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$ (or a short equivalent isogeny). The three former points have already been discussed in [18, Section 6]. With regards to the last point, the sequentiality is also determined by recovering the secret isogeny $\textsf {tr}_{sk}:= \phi ^{ \boldsymbol{s} }_{\mathcal {L}}$ or obtaining a short equivalent isogeny. In other words, this is equivalent to recovering the ideal class $[\mathfrak {b}]\in {\textbf {cl}}(\mathcal {O})$ that is computed via the secret isogeny $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$.

Definition 4

(Key recovery [11]). Given two supersingular elliptic curves $E_{}$ and $E_{B}$ defined over $\mathbb {F}_p$ with the same $\mathbb {F}_p$-rational endomorphism ring $\mathcal {O}$, find an ideal $\mathfrak {b}$ such that $[\mathfrak {b}] E_{} = E_{B}$ and $\mathfrak {b}$ is the product of ideals of small norm in $\mathcal {L}$.

There are several possible attacks for recovering the secret, some of which are discussed in [11].

Brute-force Attack on the Secret Key. A basic attack searches over all potential keys. For a secret $\boldsymbol{s}$, its corresponding secret ideal class $[\mathfrak {b}]$ is represented as $[\mathfrak {l}^{m_1}_1\mathfrak {l}^{m_2}_{2}\cdots \mathfrak {l}^{m_n}_{n}]\in {\textbf {cl}}(\mathcal {O})$ such that $\textsf {N}(\mathfrak {l}_i)=l_i\in \mathcal {L}$ and $m_i\in \boldsymbol{s}$. Thus, it can be argued that $[\mathfrak {b}]$ has several representations (i.e., there are an equivalent $\hat{ \boldsymbol{s} }\leftarrow \mathcal {S}^n$ that yields $[\mathfrak {b}]\in {\textbf {cl}}(\mathcal {O})$), which is vulnerable to exhaustive search. Castryck et al. [11] show that the expected number of equivalent representations is $|\mathcal {S}|^{n}/\textsf {ord}(G)$, assuming that ${\textbf {cl}}(\mathcal {O})$ is almost cyclic with a very large cyclic component of order $\textsf {ord}(G)$ close to $| {\textbf {cl}}(\mathcal {O}) |$. Therefore, it suffices to choose $n \log |\mathcal {S}| \approx \log (\sqrt{{p}})$, where $| {\textbf {cl}}(\mathcal {O}) |\approx \sqrt{{p}}$.

Pohlig-Hellman-style Attack. To our knowledge, the Pohlig-Hellman style attacks cannot be effectively applied to the construction in Sect. 4.4 to recover the secret degree ($\deg { \phi ^{ \boldsymbol{s} }_{\mathcal {L}} }$) or the answer ($\hat{y}^{ {G}_{1}^{ E_{BA}} }$).

Castryck-Decru-style Attack [10]. As in [19], we mask the torsion points in pairing-based verification. Therefore, the point pairs ($y^{ {G}_{1}^{ E_{A}} } ,[k_A] Q^{ {G}_{2}^{ E_{A}} }_{ }$) on $E_{A}$ and ($\hat{y}^{ {G}_{1}^{ E_{AB}} } , Q^{ {G}_{2}^{ E_{AB}} }_{ }$) on $E_{AB}$ are not images of the secret isogeny $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$. In addition, the secret isogeny $\phi ^{ \boldsymbol{s} }_{\mathcal {L}}$ has a hidden degree determined by $\boldsymbol{s}$, which is similar to the countermeasure suggested in [27]. Hence, to the best of our knowledge, our proposal is naturally resistant to a Castryck-Decru-style attack because we conceal torsion points’ preimage and the secret isogeny degree.

Meet-in-the-middle Attack (MITM). To find the path ($\phi ^{ \boldsymbol{s} }_{\mathcal {L}} : E_{A}\rightarrow E_{AB}$) in the isogeny graph $\bigcup _{l_i\in \mathcal {L}} \mathcal {G}( \mathbb {F}_p,l_i )$, MITH starts from $E_{A}$ and $E_{AB}$ to construct search trees. The attacker looks for the collision in the tree. The halfway point between $E_A$ and $E_{AB}$ is the isogeny evaluation of the halves of the set $\mathcal {L}$, $\mathcal {L}_{{\textbf {left}}}:=\{l_1,l_{2},\ldots ,l_{{n/2}} \}$, and $\mathcal {L}_{{\textbf {right}}}:=\{ l_{\frac{n}{2}+1},\ldots ,l_{n} \}$ (for simplicity assume that n is even). Let $\mathcal {J}$ be the set size of all elliptic curves defined over $\mathbb {F}_p$ that are isogenous to $E_{A}$, constrained to $\mathcal {S}$, in the halfway to $E_{AB}$. We observe that the set size is $| \mathcal {J} | = |\mathcal {S}|^{n/2}-1$; thus the attack average-case isogeny computation is about $\approx 2^{n\log ( |\mathcal {S}|)/2}$. Setting $n\log ( |\mathcal {S}|)$ to be $\approx \log {(p)/2}$, the attack’s average-case complexity is $2^{\log {(p)}/4}$.

6 Conclusion

We have presented a new class of trapdoor-VDFs that have a large ensemble of trapdoors for each VDF instantiation. In the proposed scheme, a secret trapdoor, chosen randomly from the ensemble by Challenger, is used to generate a challenge. In a few steps, Challenger can obtain the answer to a challenge by using the secret trapdoor. Without knowing the secret trapdoor, a Solver on the other hand must perform the long sequential computations. We have also presented a trapdoor-VDF construction based on [11, 18, 31].

Our future work will focus on proving that the proposed construction eliminates computational advantage of the instance generator (i.e., not being able to obtain the trapdoor or break the scheme sequentiality). Further, the setup of the proposed instantiation requires evaluating the lengthy sequential computations, so it is beneficial to examine newer approaches to make the procedure efficient.