A Guess and Determine Attack on the Elliptic Curve Discrete Logarithm Problem Ayan Mahalanobis∗
arXiv:2607.09814v1 [cs.CR] 10 Jul 2026
Abstract This paper is a continuation of our earlier work, in which, we described a Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. The Las Vegas algorithm reduces the elliptic curve discrete logarithm problem to finding a zero minor in a matrix. Using intersection poset of a hyperplane arrangement, we develop an algorithm to find a zero minor in a rectangular matrix. Our methods are elementary. We discuss the complexity of our algorithm, success probability and provide implementation details. We also provide simulation details. Finding a zero minor in a matrix is also of independent interest. Keywords:– Elliptic Curve Discrete Logarithm Problem, Hyperplane Arrangements, Matrix Completion
1
Introduction
This work follows our earlier work and develops a new attack on the elliptic curve discrete logarithm problem. We will refer to this problem as the discrete logarithm problem in this paper. We expect our reader to be familiar with our earlier work [1, 2, 8], which will be referred often and be comfortable with the fact that a matrix M can be computed from points P and Q of a non-singular elliptic curve E over a field F; whose left-kernel is K. Furthermore, the dimension of K is ℓ where ℓ is an even integer. The attack we develop do not depend on the field F or the non-singular elliptic curve E chosen. Discrete logarithm problem still holds sway in public key cryptography. Though it is not quantum secure, still it is used in many cryptographic protocols and signature schemes. One prime example is the Transport Layer Security, in particular secp256r1. The signature scheme based on the discrete logarithm problem is also used in cryptocurrencies like the bitcoin. The signature scheme Ed25519 is a popular signature scheme based on elliptic curves. The discrete logarithm problem is under constant attack since its inception [5,9]. We will not review any of these attacks, but will focus narrowly on the attack that we developed. For a general introduction to elliptic curve cryptography, we recommend Hoffstein et al. [4]. This new attack falls under the paradigm of a guess and determine algorithm. The job at hand is to find a zero minor in a rectangular matrix. For this, we will guess a part of a zero minor and then determine the rest of it. To develop this attack, we used ideas from hyperplane arrangements, especially central hyperplane arrangements and also from Grassmann coordinates. Hyperplane arrangements are interesting in their own right and is an important class of geometric lattice. Its use in this algorithm is interesting, giving rise to interesting theorems and questions. Simply put, the algorithm we present is a marriage of Grassmann coordinates and hyperplane arrangements. There is an eerie similarity of our work with matrix completion which is so popular these days because of its application in machine learning. As Neal Koblitz quotes [6] ”...in the real world if your cryptography fails, you lose a million dollars or your secret agent gets killed.”, thus we should pay attention to new attacks. Our attack has the potential to be a polynomial time algorithm. ∗
IISER Pune, Pune, INDIA; Email: [email protected]
1
1.1
Contributions in this paper
The main contribution in this paper is a guess and determine attack on the discrete logarithm problem. However, we are looking for a maximal zero-minor in K. We have shown earlier, a zero-minor solves the discrete logarithm problem (See [1, Section 3] or [2, Section 3]). The study of singular matrices have a long history, see Lovász [7]. In our attack, we guess a part of the minor by choosing randomly a few of its columns and then determine the other columns that makes it a zero minor. There are two steps in this attack. The first one uses the guess in a recursive step and reduces the size of the matrix by half. The other step determines a central hyperplane arrangement(see Section 4). These hyperplanes are the left-kernel of the columns of the reduced matrix. For this determine step we use a positive integer d, the defect. As long as d is small the worst case complexity of the determine step of the attack is in polynomial time. In practical implementations, we saw, if d increases, the number of guesses that we need to make decreases and vice versa. We present probability estimate for the probability of success of the whole algorithm in Table 1. It is easy to show that our earlier algorithm using almost principal minor [1, Section 5] can be described in this current format; where the guesses are almost principal minors. And with this new determine step, it would be interesting to see how our earlier work fares. However, we are not repeating our earlier experiment. Instead, we focus on random choices for the guess in the recursive step. One fundamental difference of this work from our earlier work is; we were able to exploit the anti-diagonal format of the kernel-matrix K. This gave rise to an efficient algorithm. The idea behind defect is similar to deviations from our earlier work.
Notations We reserve the following notations: H for hyperplanes or its basis-matrix which is the leftkernel of some column in a matrix. The matrix K will always be the left-kernel of M or its basis-matrix and is of size ℓ × 2ℓ. We also assume that ℓ is an even integer throughout this paper and that 2ℓ′ = ℓ. Furthermore, d is a positive integer and stands for defect. For a matrix A, A[a] for an array a, whose length is less than the number of columns of A, is the submatrix of A, formed by taking those columns of A whose indices belong to a. The index-origin for matrices, vectors and arrays is 1, i.e., the first element is indexed by 1, and vectors are written as rows in a matrix. We use RREF for row reduced echelon form of a matrix. We use positive integer integral, in which, [n] stands for the set {1, 2, . . . , n}.
2
An overview of our earlier work
We start by defining the discrete logarithm problem, solving which is the purpose of this paper. Definition 1 (The discrete logarithm problem). Let E be the group of rational points of an elliptic curve E over the field F. Without loss of generality we assume that the group E is of prime order p and is generated by P. The discrete logarithm problem is; in E we are given P and Q, find the integer m, such that, mP = Q. Our attack can be summarized in one line: find a zero minor and solve the discrete logarithm problem. And, this paper is in search for that zero minor. To understand our matrices: we first construct a matrix M from 2ℓ distinct points on E over a field F [1, Algorithm 1]. Here ℓ = 3n′ is the number of points a homogeneous plane projective curve of degree n′ is expected to intersect E. The integer n′ is chosen to be approximately equal to log2 (p), where p is a prime. We assume that the size of the group of the discrete logarithm problem is also p. From now onwards, p will denote a prime and also the size of the group for the discrete logarithm problem. Then we compute the left-kernel K of M which is of dimension ℓ. We will use K for both the subspace and the basis-matrix of the subspace, this will be true for all other subspaces and their basis-matrices as well. Both matrices M and K are defined over the field F. When we think of K as a basis-matrix, it has size ℓ × 2ℓ, where ℓ = O (log2 p). Since it is a basis-matrix, we can row-reduce this matrix to a simpler form while keeping the subspace it generated fixed. The form that we adopted earlier is the anti-diagonal format. This means, by row reduction we reduced the matrix K, such that, the last ℓ columns represent a ℓ × ℓ matrix with one on the antidiagonal [1, Equation (3)] and zero everywhere else. We will call this the anti-diagonal format. After reduction, we call the first ℓ columns the dense part. If there is a zero entry in the dense part, we have solved the discrete logarithm problem (see, Problem L, [8]). So, we will safely assume in this paper that the dense part has no zero entry.
2
A zero minor in the dense part corresponds to a zero maximal-minor in K [1, Theorem 3.1]. A maximal-minor is a minor of size ℓ × ℓ in K. In this paper, we will work mostly with maximal-minors. Thus when we use a minor, we mean a maximal-minor unless explicitly stated otherwise. The way our Las Vegas attack works is that we choose distinct random integers ni and −nj and create distinct points Pi = ni P and Qj = −nj Q on E. The complement of the indices of a zero minor in K gives rise to a linear relation of the form: X X ni − m nj = 0 mod p. (1) i
j
Since we know ni and nj , we can solve for m. In this paper, we take ℓ many ni and −nj points, totalling to 2ℓ points. Then we order the rows in M, so that, Pi are on the top of the matrix, where the rows are indexed by ni and follows the same ordering in the set of ni . In other words, n1 creates P1 which creates the first row of M. This is followed by n2 and so forth. Once ni are exhausted, it is followed by −nj the same way as before and which acts on Q while the ordering remains the same. Thus the first ℓ rows of M are a scalar multiples of P followed by ℓ rows that are scalar multiples of Q. Then the first ℓ columns of K are indexed by scalar multiples of P and the next ℓ columns indexed by scalar multiples of Q. Now in the guess and determine attack that we develop we guess half the number of columns from the dense P Ppart of K, this is the same as choosing the i ni in the above equation and then we determine the j nj , such that, the above equation is satisfied and that solves for m, the discrete logarithm. Our current experiments show, this way of dividing the problem is successful. Not only that, we can simulate solving the discrete logarithm problem without using matrices which reduces computational overhead and is much faster. To determine columns from the sparse part, we use ideas from central hyperplane arrangements. This has two advantages: first it reduces the complexity to polynomial time by introducing defect. The second one is more important, it is the introduction of signatures. The signatures reduce the problem of finding a zero minor to a much smaller matrix. However, in it lies the bottleneck of our computation. We need to do many kernel computations, though the matrices are all of the size (d − 1) × d, which is small, but still it takes up a lot of time. However, there are algorithmic optimizations, viz., Gray codes [10] and rank-one column replacement to create kernels of matrices which differ only by one row and parallelization. All these will improve the bottleneck that occur due to a large number of choices.
3
Finding a mate is finding a zero minor
The next idea defines the recursion in the algorithm that we present. The root of this idea is from Hodge and Pedoe [3, Chapter VII]. In this they describe the geometry for a Grassmann coordinate to be zero. Recall that a Grassmann coordinate is zero is the same as a maximal-minor is zero. The condition they describe is: suppose Sk is a k dimensional subspace in a n-dimensional vector space V. Then the basis matrix of Sk is a k × n matrix. The ordered vector of all minors of this matrix is the Grassmann coordinate of the subspace. Clearly, Grassmann coordinate is not unique as many different basis may generate the same subspace, however it is unique upto a scalar multiple. Thus one can ask the question, when is a Grassmann coordinate zero? Let ei = (0, 0, . . . , 1, . . . 0) be the standard basis of V with 1 in the ith place and 0 everywhere else. Let E be the subspace generated by k such standard basis elements. Then Sk has a zero Grassmann coordiante if and only if Sk ∩ E ̸= 0 for some E and the zero Grassmann coordinates are given by the basis vectors that generate E. Grassmann coordinates are also known as Plücker coordinates, see [11, Chapter 10]. Recall, the left-kernel K is in the anti-diagonal format and is of size ℓ × 2ℓ. The first index of rows and columns is 1. The following theorem is a formalization of the above argument. Theorem 1. Let S be the set {nr + 1, nr + 2, . . . , nr + ℓ} which is the set of all column indices in the sparse part. For 0 < k < ℓ, let c1 , c2 , . . . , ck be a set of columns from the dense part of K. Let K′ be the submatrix of K formed by these columns. Then K′ is of size ℓ × k. There is a zero minor of K′ , if and only if, there is a zero minor in K. Note, K′ is a tall matrix. If the zero minor of K′ is from rows r1 , r2 , . . . , rk , and S ′ = S ∖ {2ℓ − r1 + 1, 2ℓ − r2 + 1, . . . , 2ℓ − rk + 1} then the zero minor of K consists of columns {c1 , c2 , . . . , ck } ∪ S ′ . Clearly, S ′ is of size ℓ − k and thus the total number of columns is ℓ.
3
Proof. The proof of this theorem is fairly straightforward and involves no Grassmann coordinates. First assume that K has a zero minor and that it consists of both the dense and sparse part. Then there is are column operations in that minor that makes a zero column in that minor. This means that those columns in the dense part, by column operations, will produce a vector that will have zeros which will match with the zeros coming from the sparse part. This is due to the special structure of the columns in the sparse part. Thus column operations of columns from the dense part will have a zero in a particular position, if and only if, the column with 1 in that position was not included. Conversely, if there is a zero minor in K′ with rows r1 , r2 , . . . , rk then there is are row operations on ′ K that gives rise to a vector with zeros in the r1 , r2 , . . . , rk rows. Then if we add columns to K′ from the sparse part that have zeros in those positions, we will get a zero column in the extended minor. It is a simple exercise to see, the number of columns from the dense part and the number of columns from the sparse part add to ℓ. This completes the proof. ‡ Remark 1. In our earlier work [1, Theorem 3.1], we proved, there is a one-one correspondence between (non-maximal) zero minors in the dense part and maximal minors of the whole matrix. We now look at this situation through the above theorem. If there is a (non-maximal) zero minor in the dense part, create a submatrix of columns from the zero minor. The zero minor is then a maximal minor of the submatrix. The above theorem gives us the columns from the sparse part that gives rise to a maximal minor in the original matrix. Thus (non-maximal) zero minors gives rise to maximal zero-minors. Conversely, for a maximal zero minor in the original matrix, the columns from the sparse part gives rise to rows of a maximal zero minor in the submatrix of the dense part obtained from the columns in the dense part. Thus we have rows and columns for a (non-maximal) zero-minor in the dense part. This theorem leads us to a finding a mate algorithm; which is fairly straightforward to describe and defines our recursion! First select k(< ℓ) columns a from the dense part of K and form the submatrix K′ = K[a]. Then take the transpose of K′ which is now a k × ℓ matrix. Then do row operations on this transpose to convert it to the anti-diagonal format. Then take another set of columns from the dense part of this converted matrix and keep doing that; until the resultant matrix is small enough to do an exhaustive search for a zero minor. If there is a zero minor in the resultant matrix there is a zero-minor in the original matrix K. However, from our computational experience the above method do not work. In particular, if the number of steps in the recursion is too many, we will end up with a matrix with no zero minor. In the first case, k choices were made and it is a set of columns from the sparse part that completes this choice by producing a zero minor. When we do the next step in the recursion, we are making more choices from the columns of K. These choices that we make consecutively reduces the possibility of finding a mate and we end up being single. Thus in describing the attack algorithm, we use recursion only once, which reduces the size of the matrix by half and makes our algorithm computationally efficient. We are not saying that higher order recursions will never help. As the size of the matrix K grows with the size of the field, so will the number of zero minors in it. Then we might be able to use two step recursion with the same effect as we have now.
4
Hyperplane arrangements and singular matrix
A square matrix A is singular if its determinant is zero. This paper is about a search for a square matrix A (maximal-minor) in the rectangular matrix K (left-kernel). In a vector space V of dimension n, any subspace of dimension n − 1 is called a hyperplane. In the literature, there is a distinction between linear hyperplanes and affine hyperplanes. Since all our hyperplanes are linear hyperplanes, we will use hyperplanes for linear hyperplanes. A finite collection of hyperplanes is called a hyperplane arrangement, we will use arrangement from now on. The set of all intersections of these hyperplanes form a poset and is called the intersection poset of the arrangement, which is ordered by reverse inclusion and is known to form a geometric lattice. Our standard reference for arrangement is Stanley [13, Chapter 3] or [12]. Corresponding to a n×n matrix A with columns c1 , c2 , . . . , cn we can define n hyperplanes K1 , K2 , . . . , Kn as the left-kernel of these columns respectively. We will refer to this particular arrangement as the arrangement from the matrix A. Implicit is the assumption that the columns are of rank one. We will assume this throughout this paper. In a straightforward way, one can extend this arrangement from a square matrix A to a rectangular matrix K where the hyperplanes are the left-kernel of its columns. However, the intersection poset has to be defined carefully. We define the poset to be the set
4
of intersections of at most ℓ many hyperplanes ordered by reverse inclusion. The vertices of this poset is labelled by the subspace formed by the intersection of hyperplanes. The matrix K being a rectangular basis-matrix of size ℓ×2ℓ is a proper subspace of V with the vectors written as rows. Thus, in our context, V is of dimension 2ℓ and K is of dimension ℓ. Our main interest is in the intersection of ℓ hyperplanes from the set of all hyperplanes {Ki } for i in {1, 2, . . . , 2ℓ}. The intersection of ℓ hyperplanes is the ultimate intersection and the intersection of ℓ − 1 hyperplanes will be called a penultimate intersection. One can define a subarrangement of an arrangement in an obvious way. So, instead of using all the columns of K, we can take a subset of columns of K and the corresponding left-kernels will form a subarrangement. Needless to say, we are interested in subarrangements of ℓ hyperplanes of K. We briefly review the concept of general position that applies to intersection posets (see, [13, Page 287]). It says that a set {H1 , H2 , . . . , Ht } of hyperplanes is in general position, if dim(H1 ∩H2 ∩· · ·∩Ht ) = ℓ − t whenever t ⩽ ℓ. Furthermore, if t > ℓ, the dimension of the intersection is 0. Here ℓ is the size of the arrangement. Translated in our context of finding a zero minor, if we find a set of t hyperplanes that are not in general position, we have found at least one zero minor. This is because, those columns are linearly dependent, and a minor containing those columns will be a zero minor. In our experiments, we have not seen this happen, except when t = ℓ, and we do not check for general position in the rest of this work and in our algorithms. Though that can be easily implemented. A hyperplane arrangement is called central if there is an ultimate intersection that is non-zero, we will refer to this as a non-trivial ultimate intersection. Thus, in a central arrangement for K there is a non-zero vector v ∈ V, such that, v ∈ ∩i∈Υ Ki for some subset Υ of [2ℓ] of cardinality ℓ. We call this vector v a central element of the hyperplane arrangement. Next theorem follows, in which we talk about a square matrix. n
Theorem 2. In a hyperplane arrangement {Ki }i=1 for a n × n matrix A over the field F the following are equivalent: a) The matrix A is a singular matrix. b) There is a nonzero vector v of length n over F such that vA = 0. c) The ultimate intersection
n T
Ki ̸= 0.
i=1
Proof. The proof revolves around the fact, for a singular matrix A, the corresponding hyperplane n arrangement {Ki }i=1 is central. One way to think about it, is to construct these n intersections K1 , K1 ∩ K2 , . . . , K1 ∩ · · · ∩ Kn . Then compute a matrix T whose first row is a non-zero element from K1 , the second row is a non-zero element from the second intersection K1 ∩ K2 and continue selecting non-zero elements from respective intersections till the nth row which is a non-zero element from K1 ∩ K2 ∩ · · · ∩ Kn . This construction follows: using the Gaussian elimination algorithm to transform A to a upper-triangular matrix using row operations. In other words, TA is a upper-triangular matrix. Furthermore, when A is singular, the last row is zero in this reduced upper triangular matrix and the last row of T is non-zero. This last row of T is a scalar multiple of v. This proves the existence of a non-zero v ∈ K1 ∩ K2 · · · ∩ Kn . This v is a central element of the arrangement. Furthermore, vA = 0. This is because v belongs to the left-kernel of all columns of A. This proves (a) implies (b). Similarly, (b) implies (c) follows from the fact that vA = 0 says that all hyperplane intersections are non-zero. Similarly (c) implies (a) follows from the fact that T can be constructed as described above with no zero rows. ‡ In other words, finding a zero minor is finding a central subarrangement of size ℓ in the intersection poset of K. In the arrangement of K we have 0̂ = V as the minimal element of the intersection poset, which is the empty intersection of hyperplanes. The atoms of this poset are the hyperplanes. However this poset might not have a 1̂ – the maximal element. Though one can introduce a 1̂ in the intersection poset of K as the top element. As we saw earlier, an arrangement being central is the same as the existence of a central element v. This v will also be the intersection of all penultimate intersections. Thus this will make some maximal chains in the poset shorter by one unit than it would have been if there was no central element. The intersection poset of K looks different when K has a zero minor compared to when it does not. If the
5
minor under consideration is non-singular, then its intersection poset will be a Boolean lattice with a 1̂. However, if it is singular, the top of the poset will not exist as v will generate the ultimate and all penultimate intersections. Thus finding a zero minor is to look for this anomaly and finding its properties in the intersection poset of K. The next theorem is vital to the algorithm that we describe later. In this theorem, we define the signature of an intersection of a hyperplane H with a subspace T. Recall, the span of a matrix is its row-span. This means that we write the vectors of V as rows in a matrix. Theorem 3. Let H be a basis-matrix of a hyperplane in a vector space V of dimension n. Let T be a basis-matrix of a subspace of dimension k of V, where 0 < k < n. Then there is a vector of the form s = (s1 , s2 , . . . , sk ), where the first non-zero element in s is 1. If S is a basis-matrix of the left-kernel of the transpose of s, then ST is a basis-matrix of the intersection of the subspace spanned by H and the subspace spanned by T. The vector s is the signature of this intersection and can be 0. Proof. Let the rows of H be {h1 , h2 , . . . , hn−1 } which are a basis of the span of H. Then any element h ∈ H is of the form α1 h1 + α2 h2 + · · · + αn−1 hn−1 , where αi ∈ F. Similarly, any element t in the span of T can be written as β1 t1 + β2 t2 + · · · + βk tk where ti are the rows of T for 1 ≤ i ≤ k, βi ∈ F. Then t is an arbitrary element of the span of T. Now consider the matrix U which is formed by the transpose of H followed by the transpose of T. Thus U has n rows and n − 1 + k columns. Now we do a RREF on U. We will end up with a matrix with the last row made of n − 1 zeros followed by the signature s = (s1 , s2 , . . . , sk ). A row operation ensures that the first non-zero element of s is 1. T We need to show that span(ST) = span(H) span(T). Let b ∈ span(ST) then clearly b ∈ span(T), and we only need to prove that b ∈ span(S). Since each row b of the matrix ST is a basis, it is enough to prove when b is a row of ST. Then b = si1 t1 + si2 t2 + · · · + sik tk where (si1 , si2 , . . . , sik ) is the ith row of S. Recall U and the RREF and the (si1 , si2 , . . . , sik ) is in the kernel of the signature. This says, there is a solution to the equation HT x = b and thus b ∈ H. Conversely, assume that b is in the intersection. Then HT x = b has a solution. Furthermore, if b = β1 t1 + β2 t2 + · · · + βk tk where βi ∈ F, then (β1 , β2 , . . . , βk ) must belong to the kernel of the signature (s1 , s2 , . . . , sk ). For this recall U and then the RREF on that. ‡ Corollary 3.1. Using notations from the above theorem, if the signature s ̸= 0, the span of the matrix ST is of dimension k − 1. If s = 0, the span of T is a subspace of the span of H. Proof. A linear combination of rows of ST is α1 c1 T + α2 c2 T + · · · + αk ck T where c1 , c2 , . . . , ck are the rows of S and αi are scalars. Thus α1 c1 T + α2 c2 T + · · · + αk ck T = 0 implies that α1 c1 + α2 c2 + · · · + αk ck is in the left-kernel of T. Since T is a basis matrix of size k × n the left-kernel is 0 and the fact that c1 , c2 , . . . , ck are linearly independent, implies αi = 0 for all i. This proves that the row-span of ST is of dimension k − 1. If s = 0, then S is the identity matrix and the assertion follows. ‡ The above theorem is useful for the algorithm we develop. In the determine step, we start with a matrix K′ of size ℓ′ × ℓ where ℓ = 2ℓ′ . This matrix is in the anti-diagonal format. From this matrix a ℓ′ − d columns from the left-half is extracted and a submatrix thus formed is called M. The subspace T in the above theorem, in this context, is the left-kernel of M. Clearly, the matrix M is of size ℓ′ × (ℓ′ − d) and dimension of T is d. The indexing of the columns in M is the same as in K′ . In the determine part of the algorithm, we want to extend these columns of M to form a central ultimate hyperplane arrangement in K′ . To do this, we can check for each hyperplane of K′ computed from columns that are not in M. But, this theorem gives us an efficient way to do that computation. The signature s in the above theorem can be easily computed from the RREF of the hyperplane and T and can be considered as a representative of their intersection. Moreover, the kernel of the signature behaves well with the intersection. In other words, since the dimension of T is d, ST will have dimension d − 1 as a subspace, where S is the kernel of s and the kernel of two signatures when multiplied to T will be a subspace of dimension d − 2 and the kernel of d − 1 signatures when multiplied to T will be a subspace of dimension 1 – a vector. Since the subspace T is fixed, instead of multiplying T with the kernel of signatures, we can use the signatures and their kernels as representatives of the intersection of the hyperplanes with T. This is particularly relevant in
6
the d − 1 case where the kernel of the signatures becomes one-dimensional. Then the intersection of d − 1 hyperplanes and T can be represented by a signature, which is a vector of size d and by making the first non-zero entry of this vector one, it is even unique.
4.1
Creating the Signature-Matrix
A signature is a row-vector of length d, which is much smaller than the size of vectors in T or H which is ℓ′ . This provides a major computational advantage. Once we have the signatures, we will create the signature-matrix for the left-kernel T of M. In a signature-matrix, we will stack all signatures of all hyperplanes from all columns of K′ , which are not in M, as rows. This matrix will be a tall but slim matrix with d columns and ℓ′ + d rows. It is straight forward to argue, if we have a zero minor in this signature-matrix, we have a zero minor in the original matrix K. However, in practice, we will not compute d × d minors of the signature matrix, which corresponds to an ultimate intersection in K′ . Instead, we will compute all possible penultimte intersections, which is the kernel of matrices of size (d − 1) × d from the signature-matrix. These kernels will be one-dimensional and, we can make the first non-zero element of the generator of this kernel 1. This will make the generator unique. We can save this vector in an array and look for duplicates in that array. Duplicate penultimate intersections will give rise to a zero minor in the signature-matrix. We can also use a hashtable in an obvious way by hashing the unique generator vector to speed up looking for duplicates. Furthermore, one can do this check for duplicates even when creating the hashtable. Using this idea, we can stop at the first occurrence of a duplicate. This will stop the waste of resources to create the whole table and then check for duplicates. We will see next, hyperplanes for columns in the sparse part are easy to compute and computing their signatures are free! Thus ℓ′ signatures in the signature-matrix are free and we actually need to compute only d of them by RREF. Let A be a minor of K. Except for one case, A will have columns from both the dense and the sparse part of K. Let c1 , c2 , . . . , ck be the columns of the minor from the sparse part of K. Then ci is a column-vector of length ℓ with only one 1 and rest zero. The position of the one in ci is (i, 2ℓ − i + 1) in K for i ∈ [ℓ]. Then the left-kernel of a ci is easy to determine. It is the ℓ × ℓ identity matrix with one row deleted. The deleted row is the one which is the transpose of ci . When we are talking about columns c1 , c2 , . . . , ck , the left-kernel of the submatrix of these columns are the ℓ × ℓ identity matrix with the k rows deleted corresponding to each ci . If v belongs to this left-kernel, then v is a linear sum of these rows and has k zeros, exactly where each ci had a 1 for i in {1, 2, . . . , k}. This argument applies to K′ as well, when it is in anti-diagonal format. Now let us look at the columns of A from the dense part of K. There will be ℓ − k of those. While computing signatures from these hyperplanes coming from (sparse) columns, we note that RREF is then just a row exchange of the transpose of T. To see this, note that the hyperplane for the column ci where i ∈ [ℓ, 2ℓ] is the ℓ × ℓ identity matrix with the ℓ − i + 1 row removed. Then for the RREF we first have to transpose it and then send this row to the bottom. That will not be in RREF form but good enough for our purpose. Then that exchanges the last row of the transpose of T with the ℓ − i + 1 row. Thus to compute the signature of the hyperplane from ci from the sparse part of K we just have to find the ℓ − i + 1 row of the transpose of the basis matrix of the left-kernel T. This argument goes ad verbatim for K′ when it is in the anti-diagonal format. The easiest way to deal with the above, compute the RREF for the hyperplanes that are in the range [ℓ] ∖ (b) and then stack the whole basis matrix of the transpose of T under it. Then, when a duplicate is found while dealing with kernels of d − 1 × d submatrices, put the indices in proper order using the above argument to find the zero-minor of K′ . We call this part post processing (see, Algorithm 2). This section also refers to the create-signature and signature-mat from K′ in Algorithm 1 leading to ′ the creation of the matrix A which is of size (ℓ′ + d) × d. Then the table A is the hashtable and which ℓ+d is derived from A and has a maximum length of d−1 .
5
An algorithm to find a zero minor
Now we describe the main algorithm of this paper, which finds a zero minor in the rectangular matrix K of size ℓ × 2ℓ. The first thing to do is apply the recursion once and reduce the size of the matrix by half. To do this, it is important that ℓ = 2ℓ′ is an even number, however since the number of distinct random
7
points on the elliptic curve selected to form the matrix M is our choice, this can be easily achieved. We call this reduced matrix, K′ which is of size ℓ′ × ℓ and is in the anti-diagonal format. The next step of the algorithm uses ideas from hyperplane arrangement, where the hyperplanes are the left-kernel of the columns of K′ . Recall the intersection poset of these hyperplane arrangements are ordered by reverse inclusion. We are trying to find a central element in this intersection poset. A central element corresponds to an array of size ℓ′ which represents columns of K′ where the hyperplanes have a non-zero intersection. We could do an exhaustive search of all possible combinations of all columns, but then there will be ℓℓ′ combinations; which is of exponential growth. To solve this problem with exponential growth, we choose d, a small positive integer, which we call the defect. For many of our experiments we took d = 4 or 5. Let b be a set of ℓ′ − d columns from the dense part of K′ . Let M be the submatrix constructed from these columns of b. We then compute the left-kernel of M and call it T. The dimension of T is d under general position. This is one spot, where we can parallelize the algorithm with different processes getting different b. This type of parallelization is called a ridiculous parallelization which requires no inter-process communication. Now we need to find d hyperplanes, from the columns of K′ that are not in M, whose intersection among themselves and then with T is non-zero. This provides the existence of a central element and then the columns in M together with the columns whose hyperplanes had non-zero intersection gives us a zero minor of K′ and then that can be extended to a zero minor in K by adjoining a to it.
DLP solver
E P, Q
K size ℓ × 2ℓ
a |a| = ℓ′
K′ = K[a]T size ℓ′ × ℓ
m parallelize over ′ b ∈ ℓ′ℓ−d
b∪B
signature-matrix dim(T) = d
A of size (ℓ′ + d) × d duplicate-detection
T
b
M = K′ [b] size ℓ′ × (ℓ′ − d)
Figure 1: Schematic diagram of the algorithm. The index set a of size ℓ′ = ℓ/2 selects a subset of columns from the dense part of K to form K′ . Then index set b of size ℓ′ − d selects a subset of columns from the dense part of K′ to form the tall matrix M. The subspace T is the left-kernel of M which gives rise to the signature-matrix and then a duplicate in the hashtable yields B. One can parallelize this algorithm by choosing chunks of b and sending it to different processors for multiprocessing. In an actual implementation of this algorithm we used the multiprocessing library in Python, but one can do this serially as well. We create all combinations of size ℓ′ − d from the set [ℓ′ ]. There are ℓ′ +d such subsets which is a polynomial in ℓ′ and thus polynomial in ℓ for a fixed d. In our experience d with computation and also from the probability table, Table 1, it is clear that the defect d will increase with the increase in the size of the group p. The actual relation between p and d remains unexplored and is vital for the understanding of the complexity of the algorithm. ′ For each b ∈ ℓ +d we extract M and compute its left-kernel T. We then compute the signature of d T with all the remaining hyperplanes of K′ that are not in M and create the signature-matrix. In this ′ step lies the big bottleneck. The binomial ℓ +d can be a large number and computing the kernel T for d each one of them is really time consuming. There are ways to speed things up, like using Gray codes for creating combinations, such that, the combinations are ordered, and consecutive ones differ in only one place from the previous one and then do a rank-one replacement in the matrix to compute the kernel. We have not done this part in our experiments.
8
5.1
Pseudocode for the attack algorithm
We now present the attack algorithm in a pseudocode. The algorithm has two parts. The first one reduces the size of the input matrix by half using an array a and we call it the recursive step. The next step finds a zero minor in the reduced matrix using central hyperplane arrangements. The question remains: what is the complexity of this algorithm? First note that the complexity depends on the defect d. And, d is bounded above by ℓ. So one would expect that the algorithm is polynomial time. However, one has to consider the probability of success for that. This is the expected number of a one must choose for the success in the algorithm below. We have computed probability for small fields and tabulated that in Table 1. For big fields the probability is not known. So, at the end, we are not sure of the complexity of the algorithm at this moment.
Algorithm 1 Pseudo-code of the algorithm to find a zero minor in K Input: a matrix K of size ℓ × 2ℓ and defect d much smaller than ℓ. ▷ Using finding a mate. ◁ 3: nr ← K.nrows(), nc ← K.ncols() ′ 4: a ← array of length nr/2 from the set [nr] and a is its complement from the same set. ′ ′ 5: K ← submatrix (K[a]) ▷ K is a submatrix of K of columns with index from a. ′ ′ 6: K ← K .transpose() ′ ′ 7: K ← reduce-anti-diagonal (K ) ▷ Reduces the matrix to anti-diagonal format. ′ 8: K ← K . 9: ▷ Using intersection poset of hyperplane arrangement. ◁ 10: nr ← K.nrows(), nc ← K.ncols() 11: comb ← all-combinations of [nr] of size nr − d ▷ This step can be run in parallel, with each processor getting different b 12: for b in comb do 13: mat ← K[b]; ▷ mat is the submatrix of K with columns from b 14: T ← left-kernel(mat); ▷ dim(T) = d. 15: signature-mat ← mat(0, d) ▷ Initialize an empty matrix of zero row and d cols 16: for i ∈ b′ do ▷ b′ = [nr] ∖ b 17: u ←create-signature(H[i], T) ▷ Signature of T with hyperplane of ith column of K 18: signature-mat = signature-mat stack u ▷ Adds u at the bottom. 19: A ← signature-mat stack (T.transpose()) ′ 20: A ← create-intersection-signature(A, d) ▷ A′ is an array of hash-values. ′ 21: search for repetition in A ′ 22: Return index of repetitions in A 23: procedure create-signature(H, T) 24: ▷ This creates the signature for the hyperplane H and the kernel T ◁ 25: ▷ Both H and T are basis-matrix of size (ℓ − 1) × ℓ and d × ℓ respectively. ◁ 26: Create a matrix U by stacking H.transpose() and T.transpose() horizontally. 27: U′ is the RREF of U. 28: Extract u, the last row of U′ . 29: The vector u′ is the last d elements in the row u. 30: return u′ . ▷ u′ is a 1 × d vector. 31: procedure create-intersection-signature(A, d) 32: ▷ Creates signature for penultimate intersections. ◁ 33: r ← H.nrows() and d ← H.ncols() ▷ Number of rows and columns respectively A. 34: Comb ← all possible combinations of {1, 2, . . . , r} of size d − 1. 35: L = dict() ▷ Initialize L as an empty dictionary. 36: for x ∈ Comb do 37: mat ← A[x] ▷ mat is the submatrix of A formed by the rows with index from x 38: ker ← right-kernel(mat) ▷ ker is 1 dimensional subspace 39: L[x] ← hash(v) ▷ Here v is the generator with first non-zero element 1 40: return L 1: 2:
The post processing, that is, once a repetition is found is fairly easy to describe. There can be two
9
kinds of search, one that stops at the first repetitions and other that finds all repetitions. We adopted the first kind in out experiments. It can happen that the first repetitions do not give us the result, in that case the cardinality of the union of the index sets will be greater than ℓ′ . In that case, two different zero minors have the same central element. We have not observed this event in our computations. There
Algorithm 2 Post Processing Input: List of two combinations of size d − 1 written as set, a and b. nr ← K′ .nrows(), nc ← K′ .ncols() ′ 3: b ← [nr] ∖ (b) ▷ b′ is the complement of b 4: Take the union of two sets from input. 5: if cardinality of the union = d then 6: Γ ← union; ▷ Γ is an array of size d 7: ▷ Now compute the indices in K′ corresponding to the union ◁ 8: B=∅ ▷ Create an empty list 9: for i ∈ Γ do 10: if i <= d then 11: B.append(b′ [i]) 12: else if i > d then 13: B.append(nc − (i − d) + 1) 14: b = b ∪ B; ▷ b are indices for a zero-minor in K′ 15: ▷ Now compute indices for zero-minor in the input-matrix K ◁ 16: O ← [nc, nc + 1, . . . , 2nc] ▷ Initialize O 17: for i ∈ b do 18: O.delete(2 ∗ nc − i + 1) for i ∈ b 19: a←a∪O 20: return a 21: ▷ a are indices of the columns of K that is a zero-minor. ◁ 22: else if cardinality ̸= d then 23: return No result 1: 2:
is bit of a nonsense when we invoked K′ in the Algorithm 2. But, we trust that the reader will be able to deal with it.
5.2
Why does this algorithm work
As we know from Theorem 2, one way to find a zero minor in K is to find ℓ columns in K whose hyperplanes form a central hyperplane arrangement. This is the same as saying, find an array Υ of length ℓ from the set [2ℓ], such that, ∩i∈Υ Ki ̸= 0. Then there is a non-zero v, such that, v ∈ ∩i∈Υ Ki . The algorithm that we develop is finding this v. Now clearly v ∈ ∩i∈Υ Ki is equivalent to the condition that v ∈ ∩i∈Υ′ Ki , for every Υ′ a subset of Υ of size ℓ − 1. Then an obvious thing to do, take all ℓ − 1 subsets of the set [2ℓ] and check the intersection of the corresponding hyperplanes for repetitions. The 2ℓ problem with that, ℓ−1 is exponential in ℓ. That number is very big. So we focus on the left-half and the right-half of the rectangular matrix K simultaneously. This way, we divide the problem into two. We choose a combination b of size ℓ − d, where d is small and dℓ is polynomial in ℓ. We call d the defect in b. We define T = ∩i∈b Ki , where Ki is the hyperplane corresponding to the i ∈ b. Assuming that the hyperplanes are in general position, dimension of T is d. Now we need to find d hyperplanes from ∆ = [2ℓ]∖(b), such that, the intersection of these hyperplanes with T is non-zero. This is the same as finding two different sets of size d − 1 from ∆, such that, the v in the intersection for each set of d − 1 hyperplanes along with T is identical. Size of ∆ is ℓ + d. If ℓ+d d is small enough the number of choices d−1 is still polynomial in ℓ. So the total number of choice is ℓ ℓ+d ℓ+d d d−1 which is still polynomial in ℓ. Now the idea is, for a fixed choice of b, take all d−1 choices from ∆. These are subsets of size d − 1 and compute the signature using Theorem 3. These signatures represent the penultimate intersection. And, same penultimate intersections give rise to a zero minor. The indexes of the zero minor is the union of the indices of the hyperplanes in these two identical penultimate intersections. The above argument works for K as well as K′ .
10
The above argument will be formalized below in the form of a theorem. Theorem 4. Let Υ, ∆, T and d be as defined earlier. Let x be a d − 1 subset of ∆. Then for every i ∈ x there is a signature si as computed in Theorem 3. Make a matrix X with these signatures as rows. Thus the size of X is (d − 1) × d. Assuming general position, the right-kernel of X is one dimensional. Assume that it is generated by v. Then ∩i∈Υ∪x Ki = ⟨v⟩. Furthermore, by making the first non-zero element of v one, v is assumed unique upto scalar multiple. Proof. Recall that |Υ| = ℓ. The principal argument is, assuming general position the intersection of t many hyperplanes is a subspace of dimension ℓ − t, where 0 < t < ℓ. For a non-zero minor, the dimension of the intersection of ℓ−1 hyperplanes is 1 and the intersection of ℓ hyperplanes is 0. For a zero-minor the dimension of the intersection of ℓ hyperplanes, its ultimate intersection, is also one-dimensional. When that happens, the penultimate intersections, which are always one dimensional becomes identical. With this understanding, look at X and its right-kernel. The right-kernel being penultimate intersection is one-dimensional ⟨v⟩. And, identical v for two different x gives the same penultimate intersection and will lead to a one-dimensional ultimate intersection whose indices give rise to a zero-minor. ‡ Now once we have a vector v for every subset of size d − 1 of ∆ we have an element v ∈ ∩Υ∪x Ki , where x a subset of ∆ of size d − 1. We then compute and store the hash of this vector v along with x; for all possible x and call it the hashtable. If there is a repetition in the hash-table for x and x′ , we can construct a set of size ℓ from these sets x, x′ and Υ and the corresponding minor of K′ will be zero. This proves the following theorem: Theorem 5. Let K be a matrix of size ℓ × 2ℓ. If any two penultimate intersections of hyperplanes from K, i.e., intersection of ℓ − 1 hyperplanes coming from columns of K are identical as subspace, then there is a zero minor in K. The indices of that zero minor can be determined from the union of the indices of the two concerned intersections. At this stage, we must warn the reader that there is a possibility that the above theorem could be wrong. The vector of the indices must be made unique by making the first non-zero element in it 1. Moreover, there is a remote possibility that two different ultimate intersections are generated by the same vector. But if that happens, it will be a rare event inside a rare event.
6
The probability of success
We recall from our earlier work [8, Theorems 4 & 5] that the probability of success is greater than 0.5 as the size of the group of prime order p tends to infinity. The estimate was elementary and depended on computing the number of unique partitions of m module p. In particular we computed, given a positive integer m, the number of partitions of m into k unique parts in the range (1, p) is given by the following expression: (p − 1)(p − 2) · · · (p − k + 2)(p − 2k + 1) (2) k! From which the probability of success can be easily computed as p − 2k + 1 p(p − k + 1)
(3)
which is really close to 1/p. Now recall that the points that are in the intersection of the elliptic curve and the complete curve C, which is a subset of those points that created the matrix M, are the ones which are not in the column indices of the zero minor [8, Corollary 1]. For our current algorithm we are looking at a conditional probability, what is the probability of success when we have chosen an array a of size ℓ′ to be part of a zero minor? Let a′ = [ℓ] ∖ (a). And let t be the sum of the ni where i ∈ a′ modulo the prime p. Once a is chosen from the dense part and we do the recursive reduction corresponding to that. The output is a matrix K′ of size ℓ′ × ℓ in the anti-diagonal format and we are looking for a zero minor in that using central hyperplane arrangements. Now from Equation 1, we are looking at ℓ′ distinct integers −nj , such that, m times the sum of those integers add up to t. The probability of success can be simulated for this experiment and we present
11
the simulation as a pseudo-code in Algorithm 3. The simulation algorithm uses no matrices and is much faster than solving the discrete logarithm problem. In the determine part of our attack, we are working with the transpose of the matrix K′ = K[a] which is of size ℓ′ × ℓ. We fix ℓ′ − d columns from the dense part of K′ and then try to find d columns ′ from the rest of the columns that extend the fixed part to a zero minor in K′ . There are ℓ +d many d such choices for this fixed part. The probability that none of these choices sum upto the required sum of t := t/m mod p is ℓ′ +d p − 2ℓ′ + 1 ( d ) (4) Λ= 1− p(p − ℓ′ + 1 and thus the probability that at least one of these choices will add upto t is 1 − Λ. The probability for small fiedls and defects was computed and is in Table 1. In that table we computed the probability for a fixed small prime p and then for various small defects d. The size of the prime p was computed logarithm base 2 and is presented in the leftmost column of the table. The corresponding probability for a particular d was computed and put in the row. The range for d was from 5 to 14. The reader will notice that as the defect increases, so does the probability. Needless to say, the defect make the set of choices of b larger and also the signature matrix larger and the choices in it bigger. Thus computation becomes expensive as defect increases. Remark 2. This is a pseudo code for the simulation algorithm. Using this simulation algorithm one can simulate solving the discrete logarithm problem. It follows our algorithm closely. In particular, it can be used to understand the probability of success. This algorithm uses only integer addition, one integer multiplication and a few remainder calculation. In it, the integer r is just a place holder for the exponent m. Since, this algorithm do not use any matrices, it runs much faster compared to the original Algorithm 1. There is one more reason to look at this simulation algorithm carefully, it exposes the inner working of the attack algorithm nicely.
Table 1: The probability table for the success probability of finding a zero minor. The prime p is the size of the group of the elliptic curve. The largest integer not exceeding its logarithm base 2 is tabulated in the first column. The row corresponding to the log of a prime p is the probability of success for various defects d. log2 p 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60
d=5 0.00001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
d=6 0.00009 0.00005 0.00003 0.00001 0.00001 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
d=7 0.00088 0.00044 0.0003 0.00015 0.0001 0.00005 0.00003 0.00002 0.00001 0.00001 0 0 0 0 0 0 0 0 0 0 0
d=8 0.00758 0.0038 0.00272 0.00136 0.00096 0.00048 0.00033 0.00017 0.00011 0.00006 0.00004 0.00002 0.00001 0.00001 0 0 0 0 0 0 0
d=9 0.05743 0.02914 0.02183 0.01098 0.00807 0.00404 0.00292 0.00146 0.00104 0.00052 0.00037 0.00018 0.00013 0.00006 0.00004 0.00002 0.00001 0.00001 0 0 0
12
d = 10 0.34292 0.18939 0.1507 0.07843 0.06045 0.0307 0.02313 0.01163 0.0086 0.00431 0.00314 0.00157 0.00113 0.00056 0.0004 0.0002 0.00014 0.00007 0.00005 0.00002 0.00002
d = 11 0.93599 0.747 0.67167 0.427 0.35736 0.19835 0.15827 0.08254 0.06386 0.03246 0.02457 0.01236 0.0092 0.00461 0.00338 0.00169 0.00122 0.00061 0.00044 0.00022 0.00015
d = 12 1 0.99977 0.99914 0.9706 0.94557 0.76671 0.69191 0.44494 0.37338 0.20841 0.16674 0.08717 0.06766 0.03442 0.02616 0.01317 0.00984 0.00493 0.00364 0.00182 0.00133
d = 13 1 1 1 1 1 0.99987 0.99946 0.97668 0.9546 0.78692 0.71315 0.46441 0.3909 0.21955 0.17611 0.09232 0.07186 0.0366 0.02792 0.01406 0.01055
d = 14 1 1 1 1 1 1 1 1 1 0.99993 0.99967 0.98194 0.96287 0.80731 0.73509 0.4853 0.40984 0.23178 0.1864 0.098 0.0765
7
Implementation
The algorithm was implemented for prime fields using SageMath [15] which used FLINT [14] using Python’s multiprocessing library. The main objective of this implementation was a proof of concept for the algorithm. The implementation went fine. However, at this stage, we do not have much data to share. The algorithm has two parts. The input is a matrix K of size ℓ × 2ℓ in the anti-diagonal format. We assume that ℓ is even and ℓ = 2ℓ′ . Then we choose a random vector a of size ℓ′ from the set [ℓ] = {1, 2, . . . , ℓ} and an positive integer d as defect. Then we compute K′ from K as the submatrix of columns whose indices are in a. Then we transpose this K′ and reduce it to anti-diagonal format using only row operations. Then K′ is a matrix of size ℓ′ × ℓ. This part was done serially. Now the parallel step begins. We make a list of all possible combinations of [ℓ′ ] of size ℓ − d. Let b denote such a combination and each processor got a chunk of b. After getting a b, each processor computes the submatrix M with column indices in b from K′ and then computes its left-kernel T. The dimension of T is d. Then corresponding to this fixed T, we compute the signature-matrix and look for duplicates. If any one of these processors find a duplicate, it returns both entries in the duplicate and the computation moves into the post-processing stage, where the discrete logarithm is computed. Because of our ability to use the structure of the sparse part of the matrix which is in anti-diagonal format, computing the signature-matrix was fast. We had compute RREF for only d rows in the signaturematrix and the rest were free. Thus computing the signature-matrix was efficient. One bottle neck of the computation was computing maximal-minors in this signature-matrix. Though these were of small d × d size and since d is a rather small integer the number of such minors was polynomial in ℓ + d. But, still there were a lot of them. On the other hand, we were not able to use parallel computing with these minors. This is because that will be a two level parallelization. We did not had the expertise or the resources for that.
8
Conclusion
This paper is a formidable step forward in the Las Vegas attack that we developed about a decade ago. The work in here is both theoretical and experimental. Though we have not been able to produce data, but there are codes running and we expect to update later. We have implemented the algorithm in SageMath [15] using FLINT [14]. The implementation done was mostly a proof of concept. The implementation went fine and the algorithm presented here was tested rigorously and passed all tests. At the end, this paper reduces solving the discrete logarithm problem to searching for duplicates in ′ an array which we call the hashtable. The length of this hashtable is ℓ +d . The hashtable is created d from hashes of vectors. These vectors are the generator of the kernel of d − 1 rows of the signaturematrix. The size of the signature-matrix is (ℓ′ + d) × d. The kernel is one-dimensional and the hash of its generator is the hash value in the hashtable. The signature matrix was created from one fixed b which is an array of size ℓ′ − d from the set [ℓ′ ]. The matrix M = K′ [b] is extracted and then T is the left-kernel of M. Thus fixing b, fixes M and its left-kernel T which is of dimension d. Corresponding to this T, signatures are computed from all hyperplanes coming from the columns of K′ whose indices are not in b and signature-matrix is formed with rows as signatures. Then the d − 1 rows whose dimension is 1 is the penultimate intersection of ℓ′ hyperplanes. And, if there is a repetition in the hashtable, the union of these two sets of indices most likely is a non-zero ultimate intersection. Thus b union the union of these two sets is the set of indices of columns of K′ that forms a zero minor. This set is in one-one correspondence with a set of indices from the sparse part of K and which when added to a is the indices of the columns of a zero minor in K and solves the discrete logarithm problem. Now to the question of the probability of success of the algorithm. At the end, the probability estimate is roughly ℓ′ +d 1 ( d ) 1− 1− p ′ matters. Since as p becomes large 1 − 1p becomes small, ℓ +d has to be large enough for a reasonable d chance of success. This is what determines the choice of the number of recursion and the defect d. As
13
we said earlier, there are two bottlenecks in the implementation of this algorithm. One is the choice of b and other is the choice of d − 1 rows in the signature matrix. ′ The binomial coefficient ℓ +d is special. On one hand, it is a bottleneck in the algorithm, because d it can become very big. On the other hand, while computing the probability, it provides us with the exponent which makes the probability large enough for the computations to be worthwhile. It is the needle that we needs to threaded carefully, so that, actual computations are feasible while keeping the probability large enough for those computations to terminate. We look at the signature matrix one last time, to solve the discrete logarithm problem we need to find a maximal minor in it. This is a theme that keeps recurring, to find a zero minor in a matrix we have to find a zero minor in another matrix, albeit smaller. Is this just pure coincidence, or is there some structure underneath that remains unexposed?
Acknowledgements This work was partially supported by a NBHM research grant and a SERB Matrics grant. AI agent chatGPT was used for coding purposes, in particular, it was used to parallelize and optimize SageMath code. Ansari Abdullah implemented a preliminary version of the attack algorithm.
References [1] Ansari Abdullah and Ayan Mahalanobis. A zero minor solves the elliptic curve discrete logarithm problem. Experimental Mathematics, 2025. to appear. [2] Ansari Abdullah, Ayan Mahalanobis, and Vivek M. Mallick. A new method for solving the elliptic curve discrete logarithm problem. journal of Groups, Complexity, Cryptology, Volume 12, Issue 2, 2021. [3] W.V.D. Hodge and D. Pedoe. Methods of Algebraic Geometry, volume I. Cambridge, 1953. [4] Jeffrey Hoffstein, Jill Pipher, and Joseph H. Silverman. An Introduction to Mathematical Cryptography. Springer, New York, NY, 2nd edition, 2014. [5] Neal Koblitz. Elliptic curve cryptosystems. Mathematics of Computation, 48(177):203–209, 1987. [6] Neal Koblitz. The uneasy relationship between mathematics and cryptography. Notices of the AMS, 54(8):972–979, 2007. [7] László Lovász. Singular spaces of matrices and their application in combinatorics. Boletim da Sociedade Brasileira de Matematica - Bulletin/Brazilian Mathematical Society, 20:87–99, 1989. [8] Ayan Mahalanobis, Vivek Mohan Mallick, and Ansari Abdullah. A Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. In Debrup Chakraborty and Tetsu Iwata, editors, Progress in Cryptology – INDOCRYPT 2018, pages 215–227. Springer International Publishing, 2018. [9] Victor S. Miller. Use of elliptic curves in cryptography. In Advances in Cryptology — CRYPTO ’85 Proceedings, volume 218 of Lecture Notes in Computer Science, pages 417–426. Springer, 1985. [10] Carla Savage. A survey of combinatorial Gray codes. SIAM Review, 39(4):605–629, Dec 1997. [11] Igor R Shafarevich and Alexey O Remizov. Linear algebra and geometry. Springer Science & Business Media, 2012. [12] Richard P. Stanley. An introduction to hyperplane arrangemnts. In Geometric Combinatorics, volume 13 of IAS/Park City Mathematics Series, pages 389–496. 2007. [13] Richard P. Stanley. Enumerative Combinatorics, Volume 1. Cambridge, second edition, 2011. [14] The FLINT team. FLINT: Fast Library for Number Theory, 2026. Version 3.5.0, https://flintl ib.org. [15] The Sage Developers. SageMath, the Sage Mathematics Software System, 2026.
14
Algorithm 3 Pseudo code for the Simulation Algorithm Input: Two positive integers n and d. ▷ We will work with a prime of size approximately 2n and defect d. ◁ n 3: Compute a prime p approximately the size of 2 . 4: ▷ This prime p is the size of the group of points of the elliptic curve. ◁ 5: ℓ ← log2 p 6: if ℓ mod 2 = 1 then 7: ℓ←ℓ+1 ▷ Make ℓ even. 8: ℓ ← 3ℓ ′ 9: ℓ = ℓ ÷ 2 10: r ← random(1, p) ▷ This random r is the place holder for the exponent m 11: pool ← random.sample(range(1, p), 2 ∗ ℓ) 12: ▷ This creates a random array of distinct integers from [p] of size 2ℓ. ◁ ▷ Left-half of the pool. 13: p pool ← pool[0 . . . ℓ] 14: q pool ← pool[ℓ . . . 2ℓ] ▷ Right-half of the pool. 15: a count ← 0 ′ 16: f irst half q pool ← q pool[0 . . . ℓ ] 17: max no tries ← 50 ▷ Number of a it is going to try 18: while i < max no tries do 19: a ← random.sample(p pool, ℓ′ ) 20: ▷ Picks an array of ℓ′ distinct elements from p pool. ◁ 21: a complement ← (p pool) ∖ (a) ▷ Difference of two sets. 22: m0 ← sum(a complement) mod p 23: ▷ Sum of all the elements in the list a complement modulo a prime p. ◁ 24: d′ ← ℓ′ − d 25: b count ← 0 26: f irst half q pool = q pool[0 . . . ℓ′ ] 27: ▷ Search Loop ◁ 28: b to test ← combinations(f irst half q pool, d′ ) 29: ▷ Create all combinations of elements of first half q pool of size d′ . ◁ 30: for t ∈ b to test do 31: b set ← t 32: b complement ← q pool set ∖ (b) 33: set to test ← combinations(b complement), d) ▷ Create all combinations 34: for x ∈ set to test do 35: b prime ← x + i ▷ Concatenation of two lists 36: b prime complement = q pool set ∖ (b prime) 37: b sum ← sum(b prime complement) mod p ▷ Sum of elements in the list modulo p. 38: b sum ← (r ∗ b sum) mod p 39: if (b sum + m0 ) mod p = 0 then 40: b count+ = 1 41: return (’match found’, a count, b count) 42: return ’No match found’ 1: 2:
15