Can we Beat the Square Root Bound for ECDLP over 𝔽_p² via Representation?

Definition 2.1

(ECDLP). Let 𝔽_q be a finite field, and let E be an elliptic curve over 𝔽_q. Let P be a point of E(𝔽_q) of prime order r = 𝓞(q). Let G = 〈P〉. Given P and Q in G, solving the discrete logarithm problem overE consists in recovering k ∈ ℤ_r such that kP = Q.

We are interested in the case where q = p², for a prime p > 3. We call this particular variant p²–ECDLP.

Definition 2.2

(Representation). Let ℓ > 0, r ∈ ℕ, k ∈ ℤ_r, and let 𝓢₁, … 𝓢_ℓ be subsets of ℕ. A tuple (k₁, …, k_ℓ) ∈ 𝓢₁ × … × 𝓢_ℓ is a representation of k if k = k₁ + … +k_ℓ mod r.

Lemma 3.1

There are at leastp − 1 representations ofkas the sumk₁ + k₂with (k₁, k₂) ∈ 𝓢₁ × 𝓢₂.

Proof

Let k = k₀ + k₁⌊p⌉ + k₂p ∈ [0, r) be such that k (mod r) = k, and let k̂ = k + r = k̂₀ + k̂₁⌊p⌉ + k̂₂p when decomposed as in Equation 1. We denote by 𝓢₁₁ the subset of 𝓢₁ of the elements s = k₀ + s₂p, and by 𝓢₁₂ the subset of 𝓢₁ of the elements s = k̂₀ + s₂p.

We first show that for any k₁ ∈ 𝓢₁₁ such that k₁ ≤ k, there exists some k₂ ∈ 𝓢₂ such that k₁ + k₂ = k. Then we claim that for any k₁ ∈ 𝓢₁₂, such that k₁ > k, there is a k₂ ∈ 𝓢₂ such that k₁ + k₂ = k̂.

Let k₁ ∈ 𝓢₁₁ be arbitrary such that k₁ ≤ k. From the definition of 𝓢₁₁, k₁ = k₀ + k₁₂p. In particular k₁ ≤ k means that k₂ − k₁₂ ≥ 0, and as k < r, k − k₁ ∈ [0, r). Finally we have

Let now k₁ ∈ 𝓢₁₂, such that k₁ > k. First note that k₁ < r < k̂. From the definition of 𝓢₁₂, k₁ = k̂₀ + k₁₂p, and k̂ − k₁ ≥ 0 means that in particular k̂₂- k₁₂ ≥ 0. Furthermore as k₁ > k, k̂ − k₁ = r + k − k₁ ∈ [0, r). Finally

It follows that the number of representations (k₁, k₂) ∈ 𝓢₁ × 𝓢₂ of k is at least equal to the number N₁ of elements of 𝓢₁₁ that are smaller than k plus the number N₂ of elements of 𝓢₁₂ that are bigger than k. N₁ is the number of k₁ = k₀ + k₁₂p such that 0 ≤ k₁₂ ≤ k₂, meaning that N₁ = k₂ + 1. N₂ is the number of k₁ = k̂₀ + k₁₂p such that k₂ ≤ k₁₂ < rp. From Hasse’s Theorem, r ≥ p² − 2p. It follows that r/p ≥ p − 2, and thus N₂ ≥ p − 2 − k₁₂. It follows that there is at least p − 1 representations of k in 𝓢₁ × 𝓢₂.

□

Out of the p − 1 representations of k as k₁ + k₂, (k₁, k₂) ∈ 𝓢₁ × 𝓢₂ it suffices to compute a single one. Therefore, computing only a 1p-fraction of all points (P₁, P₂)=(k₁P, Q − k₂P) should be sufficient to compute k. In order to compute a 1p-fraction we restrict to those points (P₁, P₂) whose x-coordinate lies in the base field (i.e. P_i = (x, y) with x ∈ 𝔽_p). ^[1]

More precisely, we proceed as follows. We compute a list L of all P₁ = k₁P = (x, y) such that x ∈ 𝔽_p and k₁ ∈ 𝓢₁. Moreover, we compute a list L′ of all P₂ = Q − k₂P = (x′, y′) for k₂ ∈ 𝓢₂ such that x′ ∈ 𝔽_p. Then we search for a collision in L and L′. This gives us k as the sum of the corresponding k₁ and k₂.

This results in RepECDLP, described in Algorithm 2. Notice that the resulting lists L, L′ have expected size only p^1/2, since we impose a 1p restriction on a search space of size p^2/3.

Now let us turn to the tricky part, the computation of L, L′. Let {0 ≤ λ ≤ 12 be a fixed parameter to be determined later, and let 𝓣₁, 𝓣₂, 𝓣₃ be three sets of elements of [0, r) such that

The bit repartition of the elements of 𝓣₁, 𝓣₂ and 𝓣₃ is given by Figure 1b. The reader is advised to use the illustration in Figure 2 for the following description.

Figure 2

Illustration of RepECDLP.

It has already been argued that all s ∈ ℕ can be uniquely split as s = s₀ + ⌊p⌉s₁ + ps₂. Following the same argument, for any fixed λ, s₂ can be uniquely written as s2=s20+⌊pλ⌉s21, where s₂₀ < ⌊pλ⌉ by computing the integer division of s₂ by ⌊pλ⌉. It follows that, in particular, every s ∈ 𝓢₁ can be uniquely written as s = s₀ + p (s₂₀ + s₂₁p^λ), or in other words every s ∈ 𝓢₁ can be uniquely written as s = k₁ + k₂, where k₁ = s₀ + ps₂₀ ∈ 𝓣₁ and k₂ = p⌊pλ⌉ ∈ 𝓣₂. A similar argument can be applied to show that every s′ ∈ 𝓢₂ can be uniquely written as s′ = k₃ + k₄, where k₃ ∈ 𝓣₃ and k₄ ∈ 𝓣₂.

We create the list L₁ of (P₁, k₁) such that P₁ = k₁P for all k₁ ∈ 𝓣₁, the list L₂ of (P₂, k₂) such that P₂ = k₂P for all k₂ ∈ 𝓣₂, the list L₃ of (P₃, k₃) with P₃ = Q − k₃P for all k₃ ∈ 𝓣₃, and the list L₄ of (P₄, k₄) with P₄ = −k₄P for all k₄ ∈ 𝓣₂. From here, we compute the list L = {(P₁₂, k₁ + k₂) : (P₁, k₁) ∈ L₁, (P₂, k₂) ∈ L₂, P₁₂ = P₁ + P₂ = (x, y) with x ∈ 𝔽_p}. In particular, from the argument above, L consists of all the points k₁₂P = (x, y) such that x ∈ L and k₁₂ ∈ 𝓢₁. Then for all (x′, y′) = P₃ + P₄ with x′ ∈ 𝔽_p we check if (x′, y′) ∈ L, and if so return the sum of the corresponding k₁, k₂, k₃, k₄. In other words, we consider the following problem.

Problem 3.2

Given two lists L₁ and L₂ of points P ∈ E(𝔽_p²), compute the list L = {(x, y) = P₁ + P₂, P₁ ∈ L₁, P₂ ∈ L₂, x ∈ 𝔽_p

We claim that any algorithm solving Problem 3.2 can be used as the main routine to solve the p²–ECDLP problem. Our whole RepECDLP algorithm is summarised in Algorithm 2. The BuildLists algorithm, described in Algorithm 1 builds the lists L_i for i ∈ [1, 4] and we denote by ECJoin an algorithm solving Problem 3.2, with a slight modification that does not influence the run time: the input lists contain tuples (P_i, k_i), where k_i is an element of [0, r), the output list must also contain tuples (P₁ + P₂, k₁ + k₂).

The following lemma gives the complexities of BuildLists.

Algorithm 1

BuildLists(E, P)

Algorithm 2

RepECDLP(E, P, Q)

Lemma 3.3

The BuildLists procedure constructs lists of sizes

inOmaxp12+λ,p(1−λ)field operations using memoryOmaxp12+λ,p(1−λ).

Proof

We start by proving the time complexity. It is dominated by the runtime of the two main for-loops: the one at line 5, which fills L₁ and L₃, and the one at line 20, which fills L₂ and L₄. The first one is iterated p^λ times, and each iteration takes time p^1/2. Indeed, each iteration consists in a constant number of elementary operations in 𝔽_p and two for-loops which are each iterated p^1/2, and whose iterations consist in 𝓞(1) elementary operations in 𝔽_p. Thus the whole execution of the for-loop line 5 requires to perform Op12+λ operations. The for-loop line 20 is iterated rp^−(1+λ) times, and each iterations consists in a constant number of elementary operations over 𝔽_p. The claimed complexity follows.

We now show that the memory required is indeed Omax(p12+λ,rp−(1+λ)). The memory complexity is dominated by the storage of the four lists. Now, for i ∈ [1, 4], L_i contains 𝓞(∣L_i∣) elements of 𝔽_p. As such, the memory complexity of the whole procedure is 𝓞(max_i (∣L_i∣)). Furthermore, |L1|=|L3|=p12+λ and ∣L₂∣ = ∣L₄∣ = rp^−(1+λ). As r = 𝓞(p²), ∣L₂∣ = ∣L₄∣ = 𝓞(p^1−λ), which proves the given complexities.□

Remark 3.4

Notice that the choice λ = 14 implies that all lists have size Op34. However, as we will discuss in section 4, unbalanced list sizes might lead to time improvements.

Remark 3.5

Speaking in terms of ideal and algebraic varieties, we claim that (x1(0),x1(1),x2(0),x2(1)) ∈ V(〈f〉) = {(z₁, …, z₄) ∈ Fp4, f(z₁, … z₄) = 0}. This comes from the fact that by definition 〈f〉 ⊆ 〈g′₀, g′₁〉, It follows that V(〈g′₀, g′₁〉) ⊆ V(〈f〉). Since by construction of g′₀ and g1′,1(0),x1(1),x2(0),x2(1))∈V(〈g0′,g1′〉), our claim follows.

We are now ready to define the ZJ–Problem, which lies at the heart of our ECDLP algorithm.

Problem 3.6

(ZJ–Problem). Given two lists A and B respectively of points (x_A, y_A) and (x_B, y_B) in Fp2, and given a polynomial f of 𝔽_p[X₁, … X₄] compute the list C of all ((x_A, y_A),(x_B, y_B)) ∈ A × B such that f(x_A, y_A, x_B, y_B) = 0.

We claim that any algorithm solving the ZJ–Problem can be used as the main routine to solve Problem 3.2. Indeed, given our lists L₁ and L₂ respectively of points P₁ = (x₁, y₁) and P₂ = (x₂, y₂), and given the polynomial f defined as above, we compute the list A of all (x1(0),x1(1)) where x1=x1(0)+αx1(1). Then we compute the list B of all (x2(0),x2(1)) where x2=x2(0)+αx2(1). Now, let us denote by ZeroJoin any algorithm solving the ZJ–Problem. Let C = ZeroJoin(A, B, f).

We claim that for every P₁, P₂ satisfying P₁ + P₂ = (x, y) with x∈Fp,((x1(0),x1(1)),(x2(0),x2(1)))∈C. This comes from the definition of f. However, there may be false positives — meaning tuples ((x1(0),x1(1)),(x2(0),x2(1))) for which f(x1(0)…x2(1))=0 holds, but P₁ + P₂ = (x, y) with x ∉ 𝔽_p. Therefore, we need to check the corresponding sum (x, y), while computing the list L. In other words, for all ((x1(0),x1(1)),(x2(0),x2(1)))∈C, we first retrieve the corresponding (P₁, P₂) ∈ A × B. Then we compute (x, y) = P₁ + P₂. If x ∈ 𝔽_p, we add (x, y) to L.

This is summarized in Algorithm 3. The following lemma provides a reduction from the ZJ–Problem to Problem 3.2.

Lemma 3.7

If ZeroJoin solves the ZJ–Problem in time T and memory M, The ECJoin algorithm solves Problem 3.2 in time T and memory M.

Proof

Let us denote by T_ECJoin the time complexity of the ECJoin algorithm. This algorithm consists of three for-loops and the ZeroJoin procedure. The first for-loop is iterated ∣L₁∣ times, and each iteration takes time 𝓞(1). The second for-loop is iterated ∣L₂∣ times. Once again each iteration requires a constant number of field operations. Then comes the ZeroJoin procedure which has a runtime T. Finally, the last for-loop requires to perform ∣C∣ iterations, each of them consisting of constant time operations. It follows that:

It is clear that T ≥ ∣C∣, as the list C is built during the ZeroJoin procedure. We claim that T also satisfies T ≥ ∣L₁∣ + ∣L₂∣, as each of the ∣L₁∣ polynomial and each of the ∣L₂∣ point have to be considered at least once in order to create C. It follows that

Let us focus on the memory. We denote by M_ECJoin the memory required by the ECJoin procedure. We have:

Once again it is clear that M ≥ ∣C∣. We also claim that M ≥ ∣L₁∣ + ∣L₂∣ as our algorithm requires to store lists A and B of respective size ∣L₁∣ and ∣L₂∣. It follows that M_ECJoin = M.□

We now reduce the ZJ–Problem to p²–ECDLP.

Theorem 3.8

Under our heuristic, if there exists an algorithm ZeroJoin solving the ZJ–Problem in timeT and memory M, then RepECDLP solves the p²–ECDLP problem in time T and memory M.

Proof

We start by proving the time complexity. The RepECDLP algorithm consists basically of three steps. In the first step the lists L_i for i ∈ [1, 4] are created using the BuildLists procedure. According to Lemma 3.3 this can be done in time 𝓞(max_i(∣L_i∣)). The second step consists in creating both the join of L₁ and L₂, and of L₃ and L₄. According to Lemma 3.7, this takes time T. It remains to search for a collision between two lists. This can be done in time proportional to the size of the two lists provided that they are sorted according to the first component. Under our heuristic, we can assume that the points (x, y) contained in the lists are uniformly distributed over 𝔽_p × 𝔽_p², as such the sorting step can be done in time proportional to the size of lists. Recall that T ≥ max(∣L_i∣, ∣L∣, ∣L′∣) for the same argument than the one given in the proof of Lemma 3.7. It follows that the time complexity of the whole algorithm is dominated by T.

We claim that the memory complexity is dominated by the one of the ECJoin routines. Indeed as explained before, the space M required by this routine is at least Omax(p12+λ,p1−λ,|L|,|L′|), which is enough to prove our claim.

For completeness, we now prove that this procedure actually solves the p²–ECDLP problem. For simplicity, we consider only the first component of the lists elements. By construction

We claim that L = ECJoin(L₁, L₂) is the list

Indeed, by construction, it is obvious that ∀ (x, y) ∈ L, x ∈ 𝔽_p. Furthermore (x, y) = k₁₂P for some k₁₂ ∈ 𝓢₁ as (x, y) = k₁P + k₂P = (k₁ + k₂) P for some (k₁, k₂) ∈ L₁ × L₂. It follows that L ⊆ {k₁₂P = (x, y), k₁₂ ∈ 𝓢₁, x ∈ 𝔽_p}. We show that this is indeed an equality.

Recall that f ∈ 𝔽_p [X₁, X₂, X₃, X₄] is constructed so that, for all points P₁ = (x₁, y₁), P₂ = (x₂, y₂) ∈ E(𝔽_p²), if (x, y) = P₁ + P₂ satisfies x ∈ 𝔽_p then f(x1(0),x1(1),x2(0),x2(1))=0. Now for any P_i = (x_i, y_j), let us consider the polynomial f_i ∈ 𝔽_p[X, Y] such that fi(X,Y)=f(xi(0),xi(1),X,Y). It is clear that, for all P_j = (x_j, y_j) such that P_i + P_j = (x, y) with x∈Fp,fi(xj(0),xj(1))=0. As A is the set of the f_i polynomials for all (x_i, y_i) ∈ L₁, and B is the set of the (xj(0),xj(1)) tuples for all (x_j, y_j) ∈ L₂, it follows, from the definition of the ZeroJoin procedure, that if P_i + P_j = (x, y) satisfies that x ∈ 𝔽_p, then (i, j) ∈ C = ZeroJoin(A, B). As such {k₁₂P = (x, y), k₁₂ ∈ 𝓢₁, x ∈ 𝔽_p} ⊆ {P_i + P_j, (i, j) ∈ C}, only those points which indeed satisfy x ∈ 𝔽_p are kept in L. A similar argument is used to show that

It remains to show that a representation (k₁₂, k₃₄) of our solution k is contained in the list L × L′. We argue that our algorithm succeeds in solving p²–ECDLP if there is a representation (k₁₂, k₃₄) ∈ 𝓢₁ + 𝓢₂ of k such that k₁₂P = (x, y) with x ∈ 𝔽_p.

It is clear that if there is no such representation of k our procedure fails, as only k₁₂ ∈ 𝓢₁ for which k₁₂P = (x, y) with x ∈ 𝔽_p are considered. Now, if such a k₁₂ exists, according to Equation 3, k₁₂P is in L. Similarly, if k₃₄ satisfies that Q − k₃₄P = (x′, y′) with x′ ∈ 𝔽_p, then k₃₄ is in L′. Furthermore, as k₁₂P = Q − k₃₄P, it is enough to know that k₁₂ satisfying k₁₂P = (x, y) with x ∈ 𝔽_p exists, to ensure that the algorithm recovers the solution.

We also claim that if the elements of E(𝔽_p²) are uniformly distributed (as we assume by our heuristic), then on expectation, there exists a representation (k₁₂, k₃₄) which satisfies k₁₂P = (x, y) with x ∈ 𝔽_p. First note that the uniform distribution implies

We denote by N_rep the number of representation of k as the sum k₁₂ + k₃₄, k₁₂ ∈ 𝓢₁, k₃₄ ∈ 𝓢₂. In other words N_rep is the number of elements k₁₂ ∈ 𝓢₁ such that there exists k₃₄ ∈ 𝓢₂, with k₁₂ + k₃₄ = k. We denote by Y the number of surviving representations in L + L′. In other words, Y is the number of k₁₂ ∈ 𝓢₁ such that there exists k₃₄ ∈ 𝓢₂ with k₁₂ + k₃₄ = k, and such that k₁₂P = (x, y) with x ∈ 𝔽_p. By Lemma 3.1, we have

Therefore for sufficiently large p we expect that one representation survives.□

Lemma 4.1

([12, Result 4]). For any fixedϵ > 0, a bivariate polynomialf ∈ 𝔽_p[X, Y] of degree inX, Y ≤ d, specified by its coefficients, can be evaluated simultaneously atMgiven points (x, y) ∈ Fp2, with pair-wise differentx-coordinates usingO(M+d2)dω22−1+ϵoperations in 𝔽_p, whereω₂ ≤ 3.257 is the exponent ofn × nbyn × n²matrices multiplications.

We make use of the Schwartz-Zippel Lemma, from which we derive an upper bound on the number of zeroes of F in B in Algorithm 4.

Lemma 4.2

(Schwartz-Zippel). Given a polynomial F ∈ 𝔽_p[X, Y] of degree at mostdinX, Y, a random point (x, y) ∈ Fp2is a zero of F with probability

Theorem 4.3

RepECDLP in combination with MultiEval solves p²–ECDLP in time

Algorithm 4

MultiEval(A, B)

Proof

We start by showing that the time complexity of MultiEval is dominated by the bivariate polynomial multi-point evaluation line 3. At this aim, we denote by T_F, T_E, T_B′ and T_C respectively the time complexity required to compute F at line 2, to perform the multi-point evaluation at line 3, to execute the for-loop in line 4 and to execute the for-loop in line 6. The total runtime of the MultiEval procedure is given by

First we estimate T_F. Notice that the degree of F in X and in Y is bounded by a constant c times p, since F is the product of p polynomials of constant degree in X and Y. It follows that F can be computed in T_F = 𝓞̃(p) operations, using fast polynomial multiplication algorithms, where logarithmic factors are hidden in the 𝓞̃.

Next, we have to evaluate this polynomial simultaneously in all the p points. From Lemma 4.1, this takes time Op12(1+ω22)+ϵ for any fixed ϵ > 0.

There is a small twist, however as lemma 4.1 can only be applied for a list of points (x, y) with pair-wise different x-coordinates. Considering that all x are in 𝔽_p and that ∣B∣ = p, this condition implies that all elements of 𝔽_p are present once and only once as the x-coordinate of an element of B. This is very unlikely. In fact, we proceed as follows. We partition B according to the x-coordinate and apply the Nüsken-Ziegler algorithm with one element of each partition of B. We restart until all elements of each partitions have been processed.

The number of time we have to restart is bounded by the size of the largest partition of B. If the x-coordinated are uniformly distributed over 𝔽_p, we can estimate this size, using maximum-load results [11]. We obtain that the number of time we have to restart is with high probability bounded by a constant times log⁡ploglog⁡p. Replacing ω₂ by the best known bound 3.257 [10], and for ϵ < 10⁻⁴, its follows that T_E = 𝓞̃(p^1.314).

We may assume that for each evaluated value E[j] we kept track of the corresponding (x_j, y_j). Then building B′ from E requires only to scan through each entry of E once, and add (x_j, y_j) in B′ for all E[j] = 0 that are encountered. The runtime of this step is thus linear in ∣E∣ = ∣B∣, and therefore T_B′ = 𝓞(p).

The last step consists in evaluating all f_i simultaneously in all the point of B′. We proceed in a naive way by taking all the polynomials, one by one, and evaluating each of them simultaneously in all the point of B′. This results in the two entwined for-loops in line 6 and 7. The first one iterates over all the polynomials and thus is iterated p times. The second one iterates over all the points of B′ and thus is iterated ∣B′∣ times. Each iteration of the second loop can be performed in 𝓞(1) as all the f_i are of constant degree. It follows that T_C= 𝓞(p ∣B′∣).

It remains to estimate ∣B′∣. From Lemma 4.2, for any random (x, y) ∈ Fp2

Assuming that the points of B are uniformly distributed over Fp2, it follows that the expected size Z of B′ satisfies

and thus the expected time complexity of this third step is 𝓞(p). From Equation 4, it follows that

Building the list A of the polynomials f_i from the list A of points (x_i, y_i) and the polynomial f can be done in time linear in ∣A∣ = p, since f has constant total degree. Thus the ZJ–Problem can be solved in time T too. From Theorem 3.8, we can conclude that RepECDLP solves p²–ECDLP in time 𝓞(p^1.314).□

We hope that the result of Theorem 4.3 may be further improved. A possible direction is to replace the (unnecessary) multi-evaluation of F by some presumably more efficient zero testing method. An other research direction, as pointed out by one of the reviewers, could be to have a look at a different elliptic curve model than the one of Weierstraß (e.g. Edwards Curve). However, we are not sure whether the problem would become easier in this case.