What a lovely hat

In 2016,Petit et al. first studied the implementation of the index calculus method on elliptic curves in prime finite fields, and in 2018, Momonari and Kudo et al. improved algorithm of Petit et al. This paper analyzes the research results of Petit, Momonari and Kudo, and points out the existing problems of the algorithm. Therefore, with the help of sum polynomial function and index calculus, a pseudo-index calculus algorithm for elliptic curves discrete logarithm problem over prime finite...

This paper studies the limitations of the generic approaches to solving cryptographic problems in classical and quantum settings in various models. - In the classical generic group model (GGM), we find simple alternative proofs for the lower bounds of variants of the discrete logarithm (DL) problem: the multiple-instance DL and one-more DL problems (and their mixture). We also re-prove the unknown-order GGM lower bounds, such as the order finding, root extraction, and repeated squaring. -...

We present SCALLOP: SCALable isogeny action based on Oriented supersingular curves with Prime conductor, a new group action based on isogenies of supersingular curves. Similarly to CSIDH and OSIDH, we use the group action of an imaginary quadratic order’s class group on the set of oriented supersingular curves. Compared to CSIDH, the main benefit of our construction is that it is easy to compute the class-group structure; this data is required to uniquely represent — and efficiently act...

We demonstrate that a modification of the classical index calculus algorithm can be used to factor integers. More generally, we reduce the factoring problem to finding an overdetermined system of multiplicative relations in any factor base modulo $n$, where $n$ is the integer whose factorization is sought. The algorithm has subexponential runtime $\exp(O(\sqrt{\log n \log \log n}))$ (or $\exp(O( (\log n)^{1/3} (\log \log n)^{2/3} ))$ with the addition of a number field sieve), but requires...

For a hyperelliptic curve defined over a finite field $\bbbf_{q^n}$ with $n>1$, the discrete logarithm problem is subject to index calculus attacks. We exploit the endomorphism of the curve to reduce the size of the factorization basis and hence improve the complexity of the index calculus attack for certain families of ordinary elliptic curves and genus 2 hyperelliptic Jacobians defined over finite fields. This approach adds an extra cost when performing operation on the factor basis, but...

Let \(q~=~2^n\), and let \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) be a generalized Galbraith--Lin--Scott (GLS) binary curve, with $\ell \ge 2$ and \((\ell, n) = 1\). We show that the GLS endomorphism on \(\mathcal{E} / \mathbb{F}_{q^{\ell}}\) induces an efficient endomorphism on the Jacobian \(\mathrm{Jac}_\mathcal{H}(\mathbb{F}_q)\) of the genus-\(g\) hyperelliptic curve \(\mathcal{H}\) corresponding to the image of the GHS Weil-descent attack applied to \(\mathcal{E} /...

Prime integers are the backbone of most public key cryptosystems. Attacks often go after the primes themselves, as in the case of all factoring and index calculus algorithms. Primes are time sensitive cryptographic material and should be periodically changed. Unfortunately many systems use fixed primes for a variety of reasons, including the difficulty of generating trusted, random, cryptographically secure primes. This is particularly concerning in the case of discrete log based...

The security of multivariate cryptosystems and digital signature schemes relies on the hardness of solving a system of polynomial equations over a finite field. Polynomial system solving is also currently a bottleneck of index-calculus algorithms to solve the elliptic and hyperelliptic curve discrete logarithm problem. The complexity of solving a system of polynomial equations is closely related to the cost of computing Gröbner bases, since computing the solutions of a polynomial system can...

In this paper we further the study of index calculus methods for solving the elliptic curve discrete logarithm problem (ECDLP). We focus on the index calculus for subfield curves, also called Koblitz curves, defined over $\mathbb{F}_q$ with ECDLP in $\mathbb{F}_{q^n}$. Instead of accelerating the solution of polynomial systems during index calculus as was predominantly done in previous work, we define factor bases that are invariant under the $q$-power Frobenius automorphism of the field...

Logical cryptanalysis, first introduced by Massacci in 2000, is a viable alternative to common algebraic cryptanalysis techniques over boolean fields. With XOR operations being at the core of many cryptographic problems, recent research in this area has focused on handling XOR clauses efficiently. In this paper, we investigate solving the point decomposition step of the index calculus method for prime degree extension fields $\mathbb{F}_{2^n}$, using SAT solving methods. We experimented with...

In this paper, we describe a new Las Vegas algorithm to solve the elliptic curve discrete logarithm problem. The algorithm depends on a property of the group of rational points of an elliptic curve and is thus not a generic algorithm. The algorithm that we describe has some similarities with the most powerful index-calculus algorithm for the discrete logarithm problem over a finite field.

The introduction of summation polynomials for elliptic curves by Semaev has opened up new avenues of investigation in index calculus type algorithms for the elliptic curve discrete logarithm problem, and several recent papers have explored their use. We propose an index calculus algorithm to solve the Elliptic Curve Discrete Logarithm Problem that makes use of a technique for fast evaluation of the summation polynomials, and unlike all other algorithms using summation polynomials, does...

One of the key questions in contemporary applied cryptography is whether there exist an efficient algorithm for solving the discrete logarithm problem in elliptic curves. The primary approach for this problem is to try to solve a certain system of polynomial equations. Current attempts try to solve them directly with existing software tools which does not work well due to their very loosely connected topology and illusory reliance on degree falls. A deeper reflection on what makes systems of...

Recent research for efficient algorithms for solving the discrete logarithm (DL) problem on elliptic curves depends on the difficult question of the feasibility of index calculus which would consist of splitting EC points into sums of points lying in a certain subspace. A natural algebraic approach towards this goal is through solving systems of non linear multivariate equations derived from the so called summation polynomials which method have been proposed by Semaev in 2004 [12]. In this...

We survey recent work on the elliptic curve discrete logarithm problem. In particular we review index calculus algorithms using summation polynomials, and claims about their complexity.

The first fall degree assumption provides a complexity approximation of Gröbner basis algorithms when the degree of regularity of a polynomial system cannot be precisely evaluated. Most importantly, this assumption was recently used by Petit and Quisquater's to conjecture that the elliptic curve discrete logarithm problem can be solved in subexponential time for binary fields (binary ECDLP). The validity of the assumption may however depend on the systems in play. In this paper, we...

Nagao had proposed a decomposition method for divisors of hyperelliptic curves defined over a field $\rF_{q^n}$ with $n\geq 2$. Joux and Vitse had later proposed a variant which provided relations among the factor basis elements. Both Nagao's and the Joux-Vitse methods require solving a multi-variate system of non-linear equations. In this work, we revisit Nagao's approach with the idea of avoiding the requirement of solving a multi-variate system. While this cannot be done in general, we...

The function field sieve, a subexponential algorithm of complexity L(1/3) that computes discrete logarithms in finite fields, has recently been improved to an algorithm of complexity L(1/4) and subsequently to a quasi-polynomial time algorithm. We investigate whether the new ideas also apply to index calculus algorithms for computing discrete logarithms in Jacobians of algebraic curves. While we do not give a final answer to the question, we discuss a number of ideas, experiments, and...

Decomposing a divisor over a suitable factor basis in the Jacobian of a hyperelliptic curve is a crucial step in an index calculus algorithm for the discrete log problem in the Jacobian. For small genus curves, in the year 2000, Gaudry had proposed a suitable factor basis and a decomposition method. In this work, we provide a new method for decomposition over the same factor basis. The advantage of the new method is that it admits a sieving technique which removes smoothness checking of...

The paper is about the discrete logarithm problem for elliptic curves over characteristic 2 finite fields F_2^n of prime degree n. We consider practical issues about index calculus attacks using summation polynomials in this setting. The contributions of the paper include: a choice of variables for binary Edwards curves (invariant under the action of a relatively large group) to lower the degree of the summation polynomials; a choice of factor base that “breaks symmetry” and increases the...

In this paper, we present a variant of Diem's $\widetilde{O}(q)$ index calculus algorithm to attack the discrete logarithm problem (DLP) in Jacobians of genus $3$ non-hyperelliptic curves over a finite field $\mathbb{F}_q$. We implement this new variant in C++ and study the complexity in both theory and practice, making the logarithmic factors and constants hidden in the $\widetilde{O}$-notation precise. Our variant improves the computational complexity at the cost of a moderate increase in...

We discuss how to apply Gaudry’s index calculus algorithm for abelian varieties to solve the discrete logarithm problem in the trace zero variety of an elliptic curve. We treat in particular the practically relevant cases of field extensions of degree 3 or 5. Our theoretical analysis is compared to other algorithms present in the literature, and is complemented by results from a prototype implementation.

At ASIACRYPT 2012, Petit and Quisquater suggested that there may be a subexponential-time index-calculus type algorithm for the Elliptic Curve Discrete Logarithm Problem (ECDLP) in characteristic two fields. This algorithm uses Semaev polynomials and Weil Descent to create a system of polynomial equations that subsequently is to be solved with Gröbner basis methods. Its analysis is based on heuristic assumptions on the performance of Gröbner basis methods in this particular setting. While...

The GHS attack is known to map the discrete logarithm problem(DLP) in the Jacobian of a curve $C_{0}$ defined over the $d$ degree extension $k_{d}$ of a finite field $k$ to the DLP in the Jacobian of a new curve $C$ over $k$ which is a covering curve of $C_0$, then solve the DLP of curves $C/k$ by variations of index calculus algorithms. It is therefore important to know which curve $C_0/k_d$ is subjected to the GHS attack, especially those whose covering $C/k$ have the smallest genus...

This paper explores the potential for using genus~2 curves over quadratic extension fields in cryptography, motivated by the fact that they allow for an 8-dimensional scalar decomposition when using a combination of the GLV/GLS algorithms. Besides lowering the number of doublings required in a scalar multiplication, this approach has the advantage of performing arithmetic operations in a 64-bit ground field, making it an attractive candidate for embedded devices. We found cryptographically...

In this paper, we describe a new algorithm for discrete logarithms in small characteristic. This algorithm is based on index calculus and includes two new contributions. The first is a new method for generating multiplicative relations among elements of a small smoothness basis. The second is a new descent strategy that allows us to express the logarithm of an arbitrary finite field element in terms of the logarithm of elements from the smoothness basis. For a small characteristic finite...

Many index calculus algorithms generate multiplicative relations between smoothness basis elements by using a process called {\it Sieving}. This process allows to filter potential candidate relations very quickly, without spending too much time to consider bad candidates. However, from an asymptotic point of view, there is not much difference between sieving and straightforward testing of candidates. The reason is that even when sieving, some small amount time is spend for each bad...

In 2004, an algorithm is introduced to solve the DLP for elliptic curves defined over a non prime finite field $\F_{q^n}$. One of the main steps of this algorithm requires decomposing points of the curve $E(\F_{q^n})$ with respect to a factor base, this problem is denoted PDP. In this paper, we will apply this algorithm to the case of Edwards curves, the well-known family of elliptic curves that allow faster arithmetic as shown by Bernstein and Lange. More precisely, we show how to take...

We describe improved versions of index-calculus algorithms for solving discrete logarithm problems in Jacobians of high-genus hyperelliptic curves defined over even characteristic fields. Our first improvement is to incorporate several ideas for the low-genus case by Gaudry and Theriault, including the large prime variant and using a smaller factor base, into the large-genus algorithm of Enge and Gaudry. We extend the analysis in [24] to our new algorithm, allowing us to predict accurately...

We present a new variant of cover and decomposition attacks on the elliptic curve discrete logarithm problem, that combines Weil descent and decomposition-based index calculus into a single discrete logarithm algorithm. This variant applies, at least theoretically, to all composite degree extension fields, and is particularly well-suited for curves defined over $\F_{p^6}$. We give a real-size example of discrete logarithm computations on a seemingly secure curve defined over a 130$-bit...

We give an improved index calculus attack for a large class of elliptic curves. Our algorithm works by efficiently transferring the group structure of an elliptic curve to a weaker group. The running time of our attack poses a significant and realistic threat to the security of the elliptic curves in this class. As a consequence of our construction, we will also derive entirely new point counting algorithms. These algorithms set new run-time complexity records. We discuss...

In recent researches, it is discovered that index calculus is useful for solving the discrete logarithm problems (DLP) of the groups of the Jacobian of curves (including elliptic curve) over finite field, which are widely used to cryptosystems. In these cases, the probability that an element of the group is written by the summation of N elements of large primes and factor bases is O(1) where N is some pre-fixed constant. So the situation is little different to the normal index calculus and...

We show that for any elliptic curve $E(\F_{q^n})$, if an adversary has access to a Static Diffie-Hellman Problem (Static DHP) oracle, then by making $O(q^{1-\frac{1}{n+1}})$ Static DHP oracle queries during an initial learning phase, for fixed $n>1$ and $q \rightarrow \infty$ the adversary can solve {\em any} further instance of the Static DHP in {\em heuristic} time $\tilde{O}(q^{1-\frac{1}{n+1}})$. Our proposal also solves the {\em Delayed Target DHP} as defined by Freeman, and naturally...

In 2008 and 2009, Gaudry and Diem proposed an index calculus method for the resolution of the discrete logarithm on the group of points of an elliptic curve defined over a small degree extension field $\F_{q^n}$. In this paper, we study a variation of this index calculus method, improving the overall asymptotic complexity when $\log q \leq c n^3$. In particular, we are able to successfully obtain relations on $E(\F_{p^5})$, whereas the more expensive computational complexity of Gaudry and...

We describe the use of explicit isogenies to reduce Discrete Logarithm Problems (DLPs) on Jacobians of hyperelliptic genus~$3$ curves to Jacobians of non-hyperelliptic genus~$3$ curves, which are vulnerable to faster index calculus attacks. We provide algorithms which compute an isogeny with kernel isomorphic to $(\mathbb{Z}/2\mathbb{Z})^3$ for any hyperelliptic genus~$3$ curve. These algorithms provide a rational isogeny for a positive fraction of all hyperelliptic genus~$3$ curves defined...

In this paper, we show a general classification of cryptographically used elliptic and hyperelliptic curves which can be attacked by the Weil descent attack and index calculus algorithms. In particular, we classfy all the Weil restriction of these curves obtained by $(2,...,2)$ covering. Density analysis of these curves are shown. Explicit defintion equations of such weak curves are also provided.

We present a novel index calculus algorithm for the discrete logarithm problem (DLP) in degree 0 class groups of curves over finite fields. A heuristic analysis of our algorithm indicates that asymptotically for varying q, ``essentially all'' instances of the DLP in degree 0 class groups of curves represented by plane models of a fixed degree d over $\mathbb{F}_q$ can be solved in an expected time of $\tilde{O}(q^{2 -2/(d-2)})$. A particular application is that heuristically, ``essentially...

Gaudry present a variation of index calculus attack for solving the DLP in the Jacobian of hyperelliptic curves. Harley and Thériault improve these kind of algorithm. Here, we will present a variation of these kind of algorithm, which is faster than previous ones. Its complexity is $O(2-\frac{2}{g}+\epsilon)$. Recently, P. Gaudry and E. Thomé http://eprint.iacr.org/2004/153/ present the algorithm, whose complexity is same as our results. So I submit my manuscript to this eprint archive.

In this article, we examine how the index calculus approach for computing discrete logarithms in small genus hyperelliptic curves can be improved by introducing a double large prime variation. Two algorithms are presented. The first algorithm is a rather natural adaptation of the double large prime variation to the intended context. On heuristic and experimental grounds, it seems to perform quite well but lacks a complete and precise analysis. Our second algorithm is a...

We propose an index calculus algorithm for the discrete logarithm problem on general abelian varieties. The main difference with the previous approaches is that we do not make use of any embedding into the Jacobian of a well-suited curve. We apply this algorithm to the Weil restriction of elliptic curves and hyperelliptic curves over small degree extension fields. In particular, our attack can solve all elliptic curve discrete logarithm problems defined over $GF(q^3)$ in time $O(q^{10/7})$,...

The aim of the paper is the construction of the index calculus algorithm for the discrete logarithm problem on elliptic curves. The construction presented here is based on the problem of finding bounded solutions to some explicit modular multivariate polynomial equations. These equations arise from the elliptic curve summation polynomials introduced here and may be computed easily. Roughly speaking, we show that given the algorithm for solving such equations, which works in polynomial or...