Edwards curve point counting method and supersingular Edwards curves
0
Citation
0
Reference
20
Related Paper
Abstract:
We consider algebraic affine and projective curves of Edwards \cite{E, SkOdProj} over a finite field $\text{F}_{p^n}$. Most cryptosystems of the modern cryptography \cite{SkBlock} can be naturally transform into elliptic curves \cite{Kob}. We research Edwards algebraic curves over a finite field, which at the present time is one of the most promising supports of sets of points that are used for fast group operations \cite{Bir}. New method of counting Edwards curve order over finite field was constructed. It can be applied to order of elliptic curve due to birational equivalence between elliptic curve and Edwards curve. We find not only a specific set of coefficients with corresponding field characteristics, for which these curves are supersingular but also a general formula by which one can determine whether a curve $E_d[\mathbb{F}_{p^n}]$ is supersingular over this field or not. The embedding degree of the supersingular curve of Edwards over $\mathbb{F}_{p^n}$ in a finite field is investigated, the field characteristic, where this degree is minimal, was found. The criterion of supersungularity of the Edwards curves is found over $\mathbb{F}_{p^n}$. Also the generator of crypto stable sequence on an elliptic curve with a deterministic lower estimate of its period is proposed.Keywords:
Supersingular elliptic curve
Edwards curve
Jacobian curve
Twists of curves
Tripling-oriented Doche–Icart–Kohel curve
Degree (music)
Cite
CSIDH is an isogeny-based key exchange protocol proposed by Castryck et al. in 2018. It is based on the ideal class group action on Fp-isomorphism classes of Montgomery curves. The original CSIDH algorithm requires a calculation over Fp by representing points as x-coordinate over Montgomery curves. There is a special coordinate on Edwards curves (the w-coordinate) to calculate group operations and isogenies. If we try to calculate the class group action on Edwards curves by using the w-coordinate in a similar way on Montgomery curves, we have to consider points defined over Fp4. Therefore, calculating the class group action on Edwards curves with w-coordinates over only Fp is not a trivial task. In this paper, we prove some theorems about the properties of Edwards curves. We construct the new CSIDH algorithm using these theorems on Edwards curves with w-coordinates over Fp. This algorithm is as fast as (or a little bit faster than) the algorithm proposed by Meyer and Reith. This paper is an extended version of [29]. We added the construction of a technique similar to Elligator on Edwards curves. This technique contributes to the efficiency of the constant-time CSIDH algorithm. We also added the construction of new formulas to compute isogenies in O˜(ℓ) time on Edwards curves. It is based on formulas on Montgomery curves proposed by Bernstein et al. (élu's formulas). In our analysis, these formulas on Edwards curves are a little bit faster than those on Montgomery curves. We finally implemented CSIDH, élu's formulas, and CTIDH [3] (faster constant-time CSIDH) on Edwards curves. Each result shows the efficiency of algorithms on Edwards curves.
Edwards curve
Isogeny
Ideal class group
Family of curves
Isomorphism (crystallography)
Cite
Citations (6)
Let C be a supersingular genus-2 curve over an algebraically closed field of characteristic 3. We show that if C is not isomorphic to the curve y^2 = x^5 + 1 then up to isomorphism there are exactly 20 degree-3 maps phi from C to the elliptic curve E with j-invariant 0. We study the coarse moduli space of triples (C,E,phi), paying particular attention to questions of rationality. The results we obtain allow us to determine, for every finite field k of characteristic 3, the polynomials that occur as Weil polynomials of supersingular genus-2 curves over k.
Supersingular elliptic curve
Cite
Citations (4)
Edwards curve
Twists of curves
Supersingular elliptic curve
Jacobian curve
Canonical form
Cite
Citations (3)
We present new algorithms related to both theoretical and practical questions in the area of elliptic curves and class field theory. The dissertation has two main parts, as described below.
Let O be an imaginary quadratic order of discriminant D < 0, and let K = QD . The class polynomial HD of O is the polynomial whose roots are precisely the j-invariants of elliptic curves with complex multiplication by O . Computing this polynomial is useful in constructing elliptic curves suitable for cryptography, as well as in the context of explicit class field theory. In the first part of the dissertation, we present an algorithm to compute HD p-adically where p is a prime inert in K and not dividing D. This involves computing the canonical lift E˜ of a pair (E, f) where E is a supersingular elliptic curve and f is an embedding of O into the endomorphism ring of E. We also present an algorithm to compute HD modulo p for p inert which is used in the Chinese remainder theorem algorithm to compute HD.
For an elliptic curve E over any field K, the Weil pairing en is a bilinear map on the points of order n of E. The Weil pairing is a useful tool in both the theory of elliptic curves and the application of elliptic curves to cryptography. However, for K of characteristic p, the classical Weil pairing on the points of order p is trivial. In the second part of the dissertation, we consider E over the dual numbers K[e] and define a non-degenerate “Weil pairing on p-torsion.” We show that this pairing satisfies many of the same properties of the classical pairing. Moreover, we show that it directly relates to recent attacks on the discrete logarithm problem on the p-torsion subgroup of an elliptic curve over the finite field Fq . We also present a new attack on the discrete logarithm problem on anomalous curves using a lift of E over Fp [e].
Supersingular elliptic curve
Edwards curve
Twists of curves
Cite
Citations (4)
While first used to solve the Discrete Logarithm Problem (DLP) in the group of points of elliptic curves, bilinear pairings are now useful to construct many public key protocols. The efficiency of pairings computation depends on the arithmetic of the model chosen for the elliptic curve and of the base field where the curve is defined. In this thesis, we compute and implement pairings on elliptic curves of Jacobi forms and we study the arithmetic of a new Edwards model for elliptic curves defined over any finite field. More precisely, We use the geometric interpretation of the group law of Jacobi intersection curves to obtain the first explicit formulas for the Miller function in Tate pairing computation in this case. For pairing computation with even embedding degree, we define and use the quadratic twist of this curve to obtain efficient formulas in the doubling and addition stages in Miller's algorithm. Moreover, for pairing computation with embedding degree divisible by 4 on the special Jacobi quartic elliptic curve Ed :Y²=dX⁴+Z⁴, we define and use its quartic twist to obtain a best result with respect to Weierstrass curves. Our result is at the same time an improvement of a result recently obtained on this curve, and is therefore, to our knowledge, the best result to date on Tate pairing computation among all curves with quartic twists. In 2006, Hess et al. introduced the concept of Ate pairing which is an improving version of the Tate pairing. We extend the computation of this pairing and its variations to the curve E_d. Again our theoretical results show that this curve offers the best performances comparatively to other curves with quartic twists, especially Weiertrass curves. As a third contribution, we introduce a new Edwards model for elliptic curves with equation 1+x²+y²+x²y²=\lambda xy. This model is ordinary over binary fields and we show that it is birationally equivalent to the well known Edwards model x²+y²=c²(1+x²y²) over non-binary fields. For this, we use the theory of theta functions to obtain an intermediate model that we call the level 4 theta model. We study the arithmetic of these curves, using Riemann relations of theta functions. The group laws are complete, unified, efficient and are particularly competitive in characteristic 2. Our formulas for differential addition on the level four theta model over binary fields are the best to date among well known models of elliptic curves.
Twists of curves
Supersingular elliptic curve
Tripling-oriented Doche–Icart–Kohel curve
Discrete logarithm
Edwards curve
Cite
Citations (0)
Rational number
Supersingular elliptic curve
Cite
Citations (15)
We count the number of isogeny classes of Edwards curves over finite fields, answering a question recently posed by Rezaeian and Shparlinski. We also show that each isogeny class contains a {\em complete} Edwards curve, and that an Edwards curve is isogenous to an {\em original} Edwards curve over $\F_q$ if and only if its group order is divisible by 8 if $q \equiv -1 \pmod{4}$, and 16 if $q \equiv 1 \pmod{4}$. Furthermore, we give formulae for the proportion of $d \in \F_q \setminus \{0,1\}$ for which the Edwards curve $E_d$ is complete or original, relative to the total number of $d$ in each isogeny class.
Isogeny
Cite
Citations (3)
Edwards curve
Tripling-oriented Doche–Icart–Kohel curve
Jacobian curve
Cite
Citations (2)
Degree (music)
Cite
Citations (5)
Edwards curve
Jacobian curve
Tripling-oriented Doche–Icart–Kohel curve
Cite
Citations (120)