=Paper=
{{Paper
|id=Vol-2746/paper1
|storemode=property
|title=Analysis of 2-Isogeny Properties of Generalized Form Edwards Curves
|pdfUrl=https://ceur-ws.org/Vol-2746/paper1.pdf
|volume=Vol-2746
|authors=Anatoly Bessalov,Lyudmila Kovalchuk,Volodymyr Sokolov,Pavlo Skladannyi,Tamara Radivilova
|dblpUrl=https://dblp.org/rec/conf/cpits/BessalovKSSR20
}}
==Analysis of 2-Isogeny Properties of Generalized Form Edwards Curves==
https://ceur-ws.org/Vol-2746/paper1.pdf
Analysis of 2-Isogeny Properties
of Generalized Form Edwards Curves
Anatoly Bessalov1[0000-0002-6967-5001], Lyudmila Kovalchuk2[0000-0003-2874-7950],
Volodymyr Sokolov1[0000-0002-9349-7946], Pavlo Skladannyi1[0000-0002-7775-6039],
and Tamara Radivilova3[0000-0001-5975-0269]
1 Borys Grinchenko Kyiv University, Ukraine
2 National Technical University of Ukraine “Igor Sikorsky Kyiv Polytechnic Institute,” Ukraine
3 Kharkiv National University of Radio Electronics, Ukraine
v.sokolov@kubg.edu.ua
Abstract. The analysis of the 2-isogeny existence conditions of generalized
Edwards form curves over a prime field, including complete, quadratic, and
twisted Edwards curves, is presented. An overview of the properties of these three
classes of curves is given. Generalization of the results known for the classes of
complete and quadratic curves to the class of twisted Edwards curves is obtained.
A modified law of point’s addition is used to correctly determine the isogeny
degree.
Keywords: Generalized Edwards Form Curve, Complete Edwards Curve,
Twisted Edwards Curve, Quadratic Edwards Curve, Curve Order, Points Order,
Addition of Points, Isomorphism, Isogeny.
1 Introduction
One of the well-known prospects of post-quantum cryptography (PQC) is the isogeny
of supersingular elliptic curves with as many subgroups of their points as possible. The
discrete logarithm problem (DLP) of classical elliptic cryptography is replaced by the
problem of finding one of the isogenies of a large number of subgroups of such a
noncyclic curve, which is sufficiently resistant to the attacks of a virtual quantum
computer. To date, the growing interest in isogenies is associated with the shortest key
length in the proposed algorithms in comparison with other known candidates for PQC
at a given level of security [1].
Sect. 2 provides a brief review of the literature on this topic. Sect. 3 of the article
gives the basic definitions of isomorphic curves in Montgomery and Edwards forms,
the laws of the point’s addition, and doubling with a modification adapted to the
horizontal symmetry of inverse points. A brief overview of the properties of three
classes of generalized Edwards form curves following the classification is given. Sect. 4
summarizes the results of one of the methods for obtaining 2-isogeny for two classes
of complete and quadratic Edwards curves [3] to the class of twisted Edwards curves,
analyzes the existence conditions for the 2-isogeny in three classes of Edwards curves
over a prime field, and includes examples.
Copyright © 2020 for this paper by its authors.
Use permitted under Creative Commons License Attribution 4.0 International (CC BY 4.0)
2
2 Review of the Literature
The properties of isogenies for Weierstrass curves are well studied. Effective methods
for constructing and isogenies properties of promising classes of curves in the Edwards
form are much less known. The Edwards curves with one parameter, defined in [2],
have very attractive advantages for cryptography: fastest exponentiation of a point [2],
completeness and universality of the law of point’s addition, affine coordinates of a
neutral element of a points group, enhanced security against side-channel attacks [2–
4]. 3- and 5-isogenies are considered in previous works [5] and [6].
The programming of group operations is accelerated due to the absence of a singular
point at infinity as a neutral element of an Abelian group of points. The introduction of
the second curve parameter in [7] extended the class of curves in the Edwards form and
gave rise to classes of quadratic and twisted curves with new properties of interest to
cryptographic applications. In this paper, the known results for the 2-isogeny of
complete and quadratic Edwards curves [3, 8] are generalized to the class of twisted
Edwards curves [9, 10]. In particular, an analysis of the existing conditions of such
curves over a prime field is given.
3 Isomorphism and Properties of Classes of Generalized
Edwards Form Curves
The analysis of isogenies of Edwards curves is often based on Weierstrass and their
special cases of isomorphic curves in Montgomery or Legendre form. Let’s describe
the curve of the Montgomery form over the field 𝐹𝑞 , 𝑞 = 𝑝𝑚 by the equation [7]
𝑎+𝑑 4 𝐶+2 𝐶−2
𝑀𝐶,𝐷 : 𝐷𝜈 2 = 𝑢 3 + 𝐶𝑢2 + 𝑢, 𝐶 = 2 ,𝐷 = ,𝑎 = ,𝑑 = , 𝐶 2 ≠ 4. (1)
𝑎−𝑑 𝑎−𝑑 𝐷 𝐷
This curve is by a rational transformation of coordinates
𝑢 𝑢−1 1+𝑥 𝑢
𝑦 = ,𝑥 = ⟹𝑢= ,𝜈 = (2)
𝜈 𝑢+1 1−𝑥 𝜈
is mapped into a birationally equivalent in the generalized Edwards form curve of
[7, 10] with the equation
𝐸𝑎,𝑑 : 𝑥 2 + 𝑎𝑦 2 = 1 + 𝑑𝑥 2 𝑦 2 , 𝑎, 𝑑 ∈ 𝐹𝑝∗ , 𝑑 ≠ 1, 𝑎 ≠ 𝑑, 𝑝 ≠ 2. (3)
Unlike the original equation of this curve in [7] here we multiply the parameter 𝑎 by
𝑦 2 instead of 𝑥 2 . If the quadratic character 𝜒(𝑎𝑑) = −1, the curve (3) is isomorphic to
the complete Edwards curve [2] 𝐸1,𝑑 = 𝐸𝑑 with one parameter d
𝐸𝑑 : 𝑥 2 + 𝑦 2 = 1 + 𝑑𝑥 2 𝑦 2 , 𝜒(𝑑) = −1, 𝑑 ≠ 0,1. (4)
In the case of 𝜒(𝑎𝑑) = 1 and 𝜒(𝑎) = 𝜒(𝑑) = 1 the curve (1) is isomorphic with the
quadratic Edwards curve [10]
3
𝐸𝑑 : 𝑥 2 + 𝑦 2 = 1 + 𝑑𝑥 2 𝑦 2 , 𝜒(𝑑) = 1, 𝑑 ≠ 0,1 (5)
having, in contrast to (4), the parameter d defined as a square. This difference leads to
radically different properties of curves (4) and (5) [10], which are summarized below.
Despite this, in the pioneering work [7], these classes of curves are united by the general
term “Edwards curves.”
In [10], we proposed to swap the coordinates X and Y in the form of an Edwards
curve. Then the modified universal law of addition of points has the form
𝑥 𝑥 −𝑎𝑦1 𝑦2 𝑥1 𝑦2 +𝑥2 𝑦1
(𝑥1 , 𝑦1 ) + (𝑥2 , 𝑦2 ) = ( 1 2 , ). (6)
1−𝑑𝑥1 𝑥2 𝑦1 𝑦2 1+𝑑𝑥1 𝑥2 𝑦1 𝑦2
If two points coincide, we obtain from (6) the law of points doubling
𝑥 2 −𝑎𝑦12 2𝑥1 𝑦1
2(𝑥1 , 𝑦1 ) = ( 1 , ). (7)
1−𝑑𝑥12 𝑦12 1+𝑑𝑥12 𝑦12
The use of modified laws (6), (7) allows us to preserve the generally accepted horizontal
symmetry (relative to the axis X) of the inverse points.
Let’s define now the inverse point as −𝑃1 = (𝑥1 , −𝑦1 ) we will acquire according to
(6) the coordinates of the neutral element of the group of points 𝑂 = (𝑥1 , 𝑦1 ) +
(𝑥1 , −𝑦1 ) = (1,0). Except for the neutral element О on the axis x, there is also the point
of the second order, for which by (7) 2𝐷0 = (1,0) = 𝑂. Depending on the properties
of the parameters a and d we can get also two singular points of the 2nd order and two
singular points of the 4th order.
As follows from (3), the axis Y can also contain non-singular points
±𝐹0 = (0, ± 1⁄ ) of the 4th order, for which ±2𝐹0 = 𝐷0 = (−1,0). These points
√𝑎
exist over the primary field 𝐹𝑝 if the parameter 𝑎 is a square (quadratic residue). The
law of points addition (6) of the curve (3), in contrast to the original, retains the
definition of the degree of isogeny adapted to curves in the Weierstrass form. In
addition to the above, points of the 4th order can exist as non-singular for nonzero
coordinates x and y [10]. The order of the Edwards curve is 𝑁𝐸 = 2𝑚 ∙ 𝑛, 𝑚 ≥ 2, 𝑛 is
odd.
Justification of the new classification of generalized Edwards form curves is given
in papers [10, 11]. Below are definitions of three classes of these curves and a list of
fundamental properties of curves of different classes.
Depending on the properties of the parameters a and d, generalized Edwards form
curves (3) are divided into 3 non-intersecting classes:
• Complete Edwards curves with the condition C1: 𝜒(𝑎𝑑) = −1.
• Twisted Edwards curves with the condition C2.1: 𝜒(𝑎) = 𝜒(𝑑) = −1.
• Quadratic Edwards curves with the condition C2.2: 𝜒(𝑎) = 𝜒(𝑑) = 1.
The main properties of these classes of curves [8–10]:
1. For points of the second order, the first class of complete Edwards curves over a
prime field is the class of cyclic curves, while twisted and quadratic Edwards curves
form classes of non-cyclic curves. The maximum order of points of curves of the last 2
𝑁
classes does not exceed 𝐸⁄2.
4
2. The class of complete Edwards curves does not contain singular points. The order
of these curves is 𝑁𝐸 ≡ 4mod8 or 𝑁𝐸 ≡ 0mod8.
3. The twisted Edwards curves contain only two singular points of the 2 nd order
𝑎
𝐷1,2 = (±√ ; ∞). The order of these curves is 𝑁𝐸 ≡ 4mod8 or 𝑁𝐸 ≡ 0mod8.
𝑑
4. Quadratic Edwards curves contain two singular points of the 2 nd order 𝐷1,2 =
𝑎 1
(±√ ; ∞) and two singular points of the 4th order ±𝐹1 = (∞; ± ). The order of these
𝑑 √𝑑
curves is 𝑁𝐸 ≡ 0mod8.
5. Twisted and quadratic Edwards curves form pairs of quadratic torsion based on
the transformation of parameters: 𝑎̃ = 𝑐𝑎, 𝑑̃ = 𝑐𝑑, 𝜒(𝑐) = −1.
6. In the classes of twisted and quadratic Edwards curves, the replacement 𝑎 ↔ 𝑑
gives the isomorphism 𝐸𝑎,𝑑 ~𝐸𝑑,𝑎 .
7. Complete and quadratic Edwards curves are isomorphic to curves with parameter
𝑎 = 1: 𝐸𝑎,𝑑 ~𝐸1,𝑑/𝑎 . The introduction of the parameter into the equation of curve (3) is
justified only for the class of twisted Edwards curves.
8. Twisted Edwards curves under 𝑝 ≡ 1mod4 do not have the points of the 4th order
and have the order 𝑁𝐸 = 4𝑛, 𝑛 is odd.
9. For points of odd order, the law of addition of points (6) is always complete (i. e.,
the sum of any pair of points does not give a singular point).
4 2-Isogeny for the Classes of Complete, Quadratic,
and Twisted Edwards Curves
The isogeny of the elliptic curve 𝐸(𝐾) over a field 𝐾 into a curve 𝐸′(𝐾) is a
homomorphism 𝜙: 𝐸(𝐾 ̅) → 𝐸′(𝐾 ̅ ) over an algebraic closure 𝐾
̅ given by rational
functions. This means that for all points 𝑃, 𝑄 ∈ 𝐸(𝐾), 𝜙(𝑃 + 𝑄) = 𝜙(𝑃) + 𝜙(𝑄) and
there exist rational functions [12]
𝑝(𝑥) 𝑓(𝑥)
𝜙(𝑥, 𝑦) = ( ,𝑦 ) = (𝑥′, 𝑦′),
𝑞(𝑥) 𝑔(𝑥)
mapping points of the curve 𝐸 at the points of the curve 𝐸′. The degree of isogeny is
the maximum of the degrees 𝛼 = deg 𝜙(𝑥, 𝑦) = max{deg 𝑝(𝑥) , deg 𝑞(𝑥)}, and its
kernel is subgroup 𝐺 ⊆ 𝐸 of the order 𝛼 (separable isogeny), the points of which are
mapped by the function 𝜙(𝑥, 𝑦) into a neutral element of the group O.
Isogeny compresses the points of the curve 𝐸 at 𝛼 times and is a surjection (𝛼 points
of the curve 𝐸 are mapped to one point of the curve 𝐸′). When 𝐺 = 𝑂, isogeny becomes
isomorphism (𝛼 = 1).
The calculation of isogenies is usually carried out using the Velu formulas [12] for
curves in the Weierstrass form. In paper [3] isogeny formulas of the second (2-isogeny)
and odd degrees are obtained, adapted, in particular, to curves in the form of Edwards
(4) and (5) with one parameter 𝑑 (complete and quadratic Edwards curves).
Let us analyze and extend some of their results to curves (3) with the emphasis on
the analysis of the existing conditions for 2-isogeny over a prime field.
5
The construction of 2-isogeny in [3] is carried out in three stages:
1. Isomorphic transformation 𝜓1 (𝑥, 𝑦) = (𝑢, 𝜈) of the Edwards curve into the
Montgomery form.
2. The construction of 2-isogeny 𝜓2 (𝑢, 𝜈) = (𝑈, 𝑉).
3. Reverse transformation 𝜓3 (𝑈, 𝑉) = (𝑥, 𝑦) of the isogenous curve in the
Montgomery shape to the Edwards shape.
As a result, the composition 𝜙(𝑥, 𝑦) = 𝜓1 ∘ 𝜓2 ∘ 𝜓3 of three mappings between the
curve 𝐸 and the isogenic curve 𝐸′ is found.
At the first stage, the Edwards curve (3) 𝑥 2 + 𝑎𝑦 2 = 1 + 𝑑𝑥 2 𝑦 2 by a rational
transformation (2)
1+𝑢 2𝑢
𝜓1 (𝑥, 𝑦) = ((𝑎 − 𝑑) , (𝑎 − 𝑑) )
1−𝑢 𝜈
is transformed into the birationally equivalent Montgomery form
𝜈 2 = 𝑢3 + 2(𝑎 + 𝑑)𝑢2 + (𝑎 − 𝑑)2 𝑢. (8)
The point (0,0) is the second-order point of this curve, which, together with the point
at infinity as a neutral element of the group, forms the kernel of the 2-isogeny. It is
required to find parameters 𝑎̅ and 𝑑̅ of the isogenous curve with equation (8) and the
rational function 𝜓2 (𝑢, 𝜈) = (𝑈, 𝑉).
For the Montgomery curve of the general view
𝑀𝑐,𝑏 : 𝜈 2 = 𝑢3 + 𝑐𝑢2 + 𝑏𝑢, (9)
finding 2-isogeny is well known [12]. Based on the Velu formulas, using the laws of
the addition of the points of the curve in the general Weierstrass form, for the curve (9)
one can obtain the 2-isogeny ([12], the example 12.4)
𝑢2 +𝑐𝑢+𝑏 𝑢2 −𝑏
𝜓2 (𝑢, 𝜈) = ( , 𝜈) = (𝑈, 𝑉) (10)
𝑢 𝑢2
and the equation of the isogenous curve
𝑉 2 = 𝑈 3 − 2𝑐𝑈 2 + (𝑐 2 − 4𝑏)𝑈. (11)
The discriminant of the quadratic equation on the right-hand side of (11) is Δ = 16𝑏,
and depending on the meaning of 𝜒(𝑏), the curve (11) has one or three points of the 2nd
order. In the first case, one can construct one 2-isogeny, in the two-three points (for
three kernels as subgroups of the second-order).
The main question in this work is the question of the existence of 2-isogeny in three
classes of Edwards curves. As follows from (8) and (9), only those curves (9) of general
form can be reduced to the Montgomery form (1) or (8) (and, accordingly, to the
Edwards form), the parameter 𝑏 of which is the square (𝜒(𝑏) = 1). This is connected
with the existence on the curve (9) the points of the 4 th order 𝐹 = (𝑢1 , 𝜈1 ), such that
2𝐹 = (0,0). Then, taking 𝑏 = 𝑢12 , equation (9) after replacement 𝑐 → 𝐶𝑢1 is reduced
to the form
𝜈 2 = 𝑢3 + 𝐶𝑢1 𝑢2 + 𝑢12 𝑢, (12)
6
or to isomorphic (1) (or its quadratic torsion) curve
𝑎+𝑑
𝜈 2 = 𝑢3 + 𝐶𝑢2 + 𝑢, 𝐶 = 2 . (13)
𝑎−𝑑
This curve is birationally equivalent to the generalized Edwards form curve (3) when
𝜈 2 → 𝐷𝜈 2 . The equation (12) is equivalent to (8) when 𝑢12 = (𝑎 − 𝑑)2 and 𝐶𝑢1 =
2(𝑎 + 𝑑).
Thus, the 2-isogenic curve (11) with the discriminant Δ = 16𝑢12 in this case, has
three points of the 2nd order, and corresponding isogenies can be found only in the
classes of quadratic and twisted Edwards curves forming pairs of quadratic torsion. At
the time the curve 𝐸, for which isogeny is built, can have one point of the 2nd order and
two points of the 4th order (the class of complete Edwards curves), or belong to other
classes of Edwards curves with three points of the second order. For example, with 𝑝 ≡
3mod4 supersingular curve 𝜈 2 = 𝑢3 + 𝑢 (for which 𝜒(𝑐 2 − 4𝑏) = −1) has one point
of the second-order and two points of the 4th order and is isomorphic to the complete
Edwards curve. Its 2-isogenous curve (11) 𝑉 2 = 𝑈 3 − 4𝑈 has three points of the
second-order and falls into the classes of quadratic and twisted Edwards curves with
the same order 𝑝 + 1 of these curves. However, the element (–4) is a quadratic
nonresidue, and the Edwards curve, isomorphic to a curve of the form 𝑉 2 = 𝑈 3 − 4𝑈,
does not exist over a prime field (see equation (12)). However, taking 𝑈 → 𝑈 − 2, we
obtain an isomorphic curve 𝑉 2 = 𝑈 3 + 6𝑈 2 + 8𝑈, for which isomorphism with the
Edwards curve over a prime field with 𝑝 ≡ 7mod8 exists. Thus, the original curve 𝐸
of the form (8) with the adaptation to Edwards curves can have one or three points of
the second-order and, therefore, over a prime field belongs to one of the classes of
complete, twisted, or quadratic Edwards curves. All these curves in the extension 𝐹𝑝2 ,
in which all the elements of the subfield 𝐹𝑝 become squares, become quadratic Edwards
curves. Of course, in the extension 𝐹𝑝𝑛 , we can also build complete as well as twisted
Edwards curves.
The equations (8) and (9) are identical for 𝑐 = 2(𝑎 + 𝑑), 𝑏 = (𝑎 − 𝑑)2 , then
2
𝑐 − 4𝑏 = 16𝑎𝑑 and the isogenic curve equation (11) in the Montgomery form has the
form
𝑀1 : 𝑉 2 = 𝑈 3 − 4(𝑎 + 𝑑)𝑈 2 + 4𝑎𝑑𝑈. (14)
Its discriminant is Δ = 16(1 − 𝑑)2 , and the corresponding roots are defined as
2(𝑎 + 𝑑) ± 2(𝑎 − 𝑑) = {4𝑎, 4𝑑}. Therefore, it can be written as follows:
𝑀1 : 𝑉 2 = 𝑈(𝑈 − 4𝑎)(𝑈 − 4𝑑). (15)
Linear coordinate offset 𝑈 → {𝑈 − 4𝑎, 𝑈 − 4𝑑} to other values of the cubic roots in
(15) leads to two alternative equations (14) of isogenous curves in the Montgomery
form:
𝑀2 : 𝑉 2 = 𝑈 3 − 4(𝑑 − 2𝑎)𝑈 2 + 16𝑎(𝑎 − 𝑑)𝑈, (16)
𝑀3 : 𝑉 2 = 𝑈 3 + 4(2𝑑 − 𝑎)𝑈 2 − 16𝑑(𝑎 − 𝑑)𝑈. (17)
7
The curve (16), up to isomorphism, coincides with the isogenic curve in the form (8),
but with the parameters 𝑎̅ and 𝑑̅
2
𝑉 2 = 𝑈 3 + 2(𝑎̅ + 𝑑̅ )𝑈 2 + (𝑎̅ − 𝑑̅ ) 𝑈. (18)
From this equation and (12)–(14) one can obtain the equalities
𝑎̅+𝑑̅
2 ̅−𝑑̅ 𝑈1 = −4(𝑎 + 𝑑), 𝑈12 = 16𝑎𝑑.
𝑎
Hence, after the substitution 𝑈1 = ±4√𝑎𝑑 we obtain
2
𝑎̅+𝑑̅ ∓(𝑎+𝑑) √𝑎+√𝑑
= ⟹ 𝑑1̅ ±1 = 𝑎̅1 ( ) . (19)
𝑎̅−𝑑̅ 2√𝑎𝑑 √𝑎−√𝑑
So, for curve (8), two isogenous curves (14) in the form (18) have two mutually inverse
parameters 𝑑1̅ ±1 of isomorphic quadratic or twisted Edwards curves.
According to property 5 of Sect. 2, the twisted Edwards curve is the quadratic torsion
of the quadratic Edwards curve 𝐸1,𝑑 = 𝐸𝑑 with the offset 𝑐 = 𝑎 of the parameters 𝑎̃ =
𝑎, 𝑎̃ = 𝑎𝑑, 𝜒(𝑎) = −1, where 𝑑 is the parameter of the quadratic Edwards curve
(𝜒(𝑑) = 1). In this case, the parameter 𝑎 can be considered as a fixed factor of the
variable parameter 𝑑, moreover 𝑎̃ ± 𝑑̃ = 𝑎(1 ± 𝑑). For example, with 𝑝 ≡ 3mod4 for
a twisted curve, we can take 𝑎 = −1 аnd with 𝑝 ≡ 1mod4 as the smallest value of the
quadratic nonresidue.
Further, instead of the curve 𝐸𝑎,𝑑 we will use the curve 𝐸𝑎,𝑎𝑑 that leads to the
substitution 𝑑 → 𝑎𝑑. This simplifies the formulas for the isogenic curve parameters.
The formula (19) is valid only for one of the three points of the 2nd order (0,0) of the
curve (15). Based on (12), (13), (16)–(18) one can obtain two more formulas for the
parameter 𝑑̅2,3 of isogenic curves, which are given below in Theorem 1.
The inverse transformation of isogenous curves in the Montgomery form (𝑀1 , 𝑀2 ,
and 𝑀3 ) into the Edwards form 𝐸𝑎,𝑎𝑑 is performed based on rational functions (2) taking
into account different values of coordinates of points of the 4 th order
±𝑈1 ∈ {4𝑎√𝑑, 4𝑎√1 − 𝑑, 4𝑎√𝑑(𝑑 − 1)} or ±𝑈1 = 𝑎̅ − 𝑑̅ with the help of rational
function
𝑈−𝑈1 2𝑈 𝑈 1
𝜓3 (𝑈, 𝑉) = ( , √ ̅−𝑑 ̅
) = (𝑥, 𝑦).
𝑈+𝑈1 𝑉 𝑎
Substitution of these rational functions of the form (2) into the equations of the curve
in the Montgomery form gives the isogenic Edwards curve 𝑥 2 + 𝑎̅𝑦 2 = 1 + 𝑑̅ 𝑥 2 𝑦 2 .
The composition 𝜙(𝑥, 𝑦) = 𝜓1 ∘ 𝜓2 ∘ 𝜓3 of three transformations leads to the 2-
isogeny formulas for curves in the Edwards form, which are given below in Theorem 1.
In [3], the theorem was proved that is valid for complete and quadratic Edwards
curves (𝑎 = 1). We generalize this theorem to all generalized Edwards form curves (3).
Besides, we give its formulation taking into account the modification of the law of
points addition (6) of Edwards curves and the replacement (𝑥 ↔ 𝑦) [10].
8
Theorem 1. Let’s take the generalized Edwards form curve 𝐸𝑎,𝑎𝑑 and the elements
(possibly in extension) of the field 𝐾: 𝛿 2 = 𝑑, 𝛾 2 = 1 − 𝑑, 𝑖 2 = −1. Then there exist
three pairs of 2-isogeny 𝐸𝑎,𝑎𝑑 → 𝐸′𝑎,𝑎𝑑̅ , set by the functions 𝜙1 , 𝜙2 , and 𝜙3
𝑎𝑑 ∓ 𝛿 𝑎𝛿𝑥 2 ± 1 𝑦 1 − 𝑎2 𝑑𝑥 2
𝜙1 (𝑥, 𝑦) = ( , 𝑖(𝑎𝛿 ∓ 1) ),
𝑎𝑑 ± 𝛿 𝑎𝛿𝑥 2 ∓ 1 𝑥 1 − 𝑎2 𝑑
1−𝛿 2
mapping 𝐸𝑎,𝑎𝑑 → 𝐸′𝑎̅,𝑎̅𝑑̅ with the parameters 𝑑1̅ ±1 = 𝑎̅ ( ) ;
1+𝛿
(𝑎𝛾 ∓ 1)𝑥 2 ± 1
𝜙2 (𝑥, 𝑦) = ( , (𝑎𝛾 ∓ 1)𝑥𝑦),
(𝑎𝛾 ± 1)𝑥 2 ∓ 1
1−𝛾 2
mapping 𝐸𝑎,𝑎𝑑 → 𝐸′𝑎̅,𝑎̅𝑑̅ with the parameters 𝑑̅2±1 = 𝑎̅ ( ) ;
1+𝛾
𝛿𝑥 2 ∓ 𝑖𝛾 − 𝛿 𝑦
𝜙3 (𝑥, 𝑦) = (− , (𝑖𝛾 ± 𝛿) ),
𝛿𝑥 2 ± 𝑖𝛾 − 𝛿 𝑥
𝑖𝛾−𝛿 2
mapping 𝐸𝑎,𝑎𝑑 → 𝐸′𝑎̅,𝑎̅𝑑̅ with the parameters 𝑑̅3±1 = 𝑎̅ ( ) .
𝑖𝛾+𝛿
The proof of the theorem for the case 𝑎 = 1 is given in [3]. Let us adapt its formulas
for the curve (3).
Taking into account the accepted designations, equations (16), (18), (19) of isogenic
curves can be written
𝑀1 : 𝑉 2 = 𝑈 3 − 4𝑎(1 + 𝛿 2 )𝑈 2 + (4𝑎𝛿)2 𝑈;
𝑀2 : 𝑉 2 = 𝑈 3 + 4𝑎(1 + 𝛾 2 )𝑈 2 + (4𝑎𝛾)2 𝑈;
𝑀3 : 𝑉 2 = 𝑈 3 + 4𝑎(𝛿 2 + (𝑖𝛾)2 )𝑈 2 + (4𝑎𝑖𝛿𝛾)2 𝑈.
The first coordinates of the points (𝑈1 , 𝑉1 ) of the 4th order of these curves (for them
(1) (2)
2(𝑈1 , 𝑉1 ) = (0,0)) are respectively equal to 𝑈1 = ±4𝑎𝛿, 𝑈1 = ±4𝑎𝛾, and
(3)
𝑈1 = ±4𝑎𝑖𝛿𝛾. Equating the coefficients at 𝑈 2 in (15), (20), and the equations of
isogenic curves, we obtain
𝑎̅ + 𝑑̅ (1)
2 𝑈 = −4𝑎(1 + 𝛿 2 ),
𝑎̅ − 𝑑̅ 1
𝑎̅ + 𝑑̅ (2)
2 𝑈 = 4𝑎(1 + 𝛾 2 ),
𝑎̅ − 𝑑̅ 1
𝑎̅ + 𝑑̅ (3)
2 𝑈 = 4𝑎(𝛿 2 + (𝑖𝛾)2 ).
𝑎̅ − 𝑑̅ 1
Hence, for each pair of isogenic curves, we find the values of the parameters:
1−𝛿 2
𝑑1̅ ±1 = 𝑎̅ ( ) ,
1+𝛿
1−𝛾 2
𝑑̅2±1 = 𝑎̅ ( ) ,
1+𝛾
𝛿 − 𝑖𝛾 2
𝑑̅3±1 = 𝑎̅ ( ) .
𝛿 + 𝑖𝛾
We emphasize that for the curve 𝐸𝑎,𝑎𝑑 they do not depend on the parameter 𝑎, but they
depend on the parameter 𝑎̅.
The proof of formulas for mapping rational functions 𝜙1 , 𝜙2 , and 𝜙3 is based on the
composition 𝜙(𝑥, 𝑦) = 𝜓1 ∘ 𝜓2 ∘ 𝜓3 of three transformations: from an Edwards curve
9
to a Montgomery shape, an isogenous transformation of a Montgomery curve, and
finally the inverse transformation of the latter to an Edwards curve. It repeats the
corresponding proof in [3] with the replacement 𝛿 → 𝑎𝛿, 𝛾 → 𝑎𝛾.
It should be noted that the generally accepted definition of the degree of isogeny is
𝑝(𝑥)
the highest of the degrees of the polynomials of the first rational function of the
𝑞(𝑥)
transformation 𝜙(𝑥, 𝑦) [11]. It is valid for Weierstrass curves. If we turn to the original
Theorem 1 [3], then we come to a paradoxical result: the degree of 2-isogeny is equal
to 1. The modified law of Edwards curve points addition (6) with horizontal symmetry
of inverse points ±(𝑥1 , 𝑦1 ) = (𝑥1 , ±𝑦1 ) adopted by us removes this paradox: the degree
of isogeny is 𝛼 = deg(𝜙) = 2.
Let’s consider some properties of 2-isogeny of Edwards curve 𝐸𝑎,𝑎𝑑 over a prime
field.
Proposition 2. The complete Edwards curve with the order 𝑁𝐸 ≡ 0mod8 has a
unique mapping 𝜙2 (𝑥, 𝑦) over the primary field 𝐹𝑝 at 𝜒(𝛾) = 1 to the quadratic
Edwards curve.
Proof. By doing 𝜒(𝛾) = 1 the complete curve has points of the 8th order and its order
is 𝑁𝐸 ≡ 0mod8 [10]. At 𝜒(𝛾) = 1 there exist elements ±𝛾 of the field 𝐹𝑝 and the
1−𝛾 2
parameter 𝑑̅2±1 = 𝑎̅ ( ) of the quadratic (𝑎̅ = 1) or twisted (𝜒(𝑎̅) = −1) Edwards
1+𝛾
curve. At 𝑎̅ = 1 there exists a 2-isogeny 𝜙2 (𝑥, 𝑦) and the corresponding quadratic
curves are isomorphic to each other with parameters 𝑑̅2±1 . The transformation from a
quadratic curve to a twisted curve as a quadratic torsion change all points of the curve
(except 𝑂 = (1,0) and 𝐷0 = (−1,0)), therefore, an isogeny 𝜙2 (𝑥, 𝑦) from a complete
curve exists only in a pair of quadratic curves (𝑎̅ = 1). On the other hand, for the
complete Edwards curve over the field 𝐹𝑝 there are no elements of the field 𝛿 = ±√𝑑,
because 𝜒(𝑑) = −1 and 2-isogeny 𝜙1 (𝑥, 𝑦) and 𝜙3 (𝑥, 𝑦) over the field 𝐹𝑝 do not exist.
This proves the uniqueness of the mapping 𝜙3 (𝑥, 𝑦) as one of three functions defined
in Theorem 1.
Consequence. The complete Edwards curve with the order 𝑁𝐸 ≡ 0mod4 does not
have 2-isogeny over the field 𝐹𝑝 in all classes of generalized Edwards form curves.
Proof. From Proposition 2 it follows that the complete Edwards curves are mapped
exclusively to the quadratic Edwards curves. But the order of quadratic Edwards curves
is 𝑁𝐸 ≡ 0mod8 [10], that’s why complete Edwards curves with the order
𝑁𝐸 ≡ 0mod4, according to the Tate theorem [12], do not have 2-isogeny over the field
𝐹𝑝 .
Proposition 3. The quadratic Edwards curve has the only mapping 𝜙2 (𝑥, 𝑦) over the
prime field 𝐹𝑝 to the quadratic Edwards curve at any values 𝑝 and 𝜒(𝛾) = 1, and
mappings 𝜙1 (𝑥, 𝑦) and 𝜙3 (𝑥, 𝑦) at 𝑝 ≡ 1mod4 and 𝜒(𝛾) = 1.
Proof. Similarly to Proposition 2, there is a unique mapping of the Edwards quadratic
curve over the prime field to the Edwards quadratic curve; at 𝜒(𝛾) = 1 the only
mapping 𝜙2 (𝑥, 𝑦) of the Edwards quadratic curve over the prime field 𝐹𝑝 to the
Edwards quadratic curve takes place. By doing 𝑝 ≡ 1mod4 and 𝜒(𝛾) = 1 for quadratic
curves there exist the elements of the field 𝛿 = ±√𝑑, 𝛾 = ±√1 − 𝑑, and 𝑖 = ±√−1,
and, respectively, mappings 𝜙1 (𝑥, 𝑦) and 𝜙3 (𝑥, 𝑦).
10
Proposition 4. The twisted Edwards curve has the only mapping 𝜙2 (𝑥, 𝑦) over the
primary field 𝐹𝑝 to the Edwards twisted curve at 𝑝 ≡ 3mod4 and 𝜒(𝛾) = 1.
Proof. According to property 8 of the Sect. 1 [10], at 𝑝 ≡ 1mod4 the twisted
Edwards curve over the primary field 𝐹𝑝 does not have points of the 4th order, therefore,
the corresponding 2-isogeny does not exist in this class of curves. At 𝑝 ≡ 3mod4 over
the field 𝐹𝑝 there do not exist elements 𝑖 = ±√−1 and, respectively, mappings 𝜙1 (𝑥, 𝑦)
and 𝜙3 (𝑥, 𝑦). The only 2-isogeny in this class at 𝑝 ≡ 3mod4 and 𝜒(𝛾) = 1 is the
function 𝜙2 (𝑥, 𝑦).
Let’s consider examples of the 2-isogeny of complete and quadratic Edwards curves
over the field 𝐹𝑝 .
Example 1. Let 𝑝 = 11 and the complete Edwards curve 𝐸 = 𝐸7 : 𝑥 2 + 𝑦 2 = 1 +
7𝑥 2 𝑦 2 where 𝜒(𝑑 = 7) = −1, 𝜒(1 − 𝑑 = 4) = 1 with the order 𝑁𝐸 = 16 is given.
According to Theorem 1, there exists only a pair of 2-isogeny Edwards quadratic curves
𝐸′ = 𝐸4 and 𝐸′ = 𝐸3 with the parameters 𝑑1,2 = 𝑑̅ ±1 = {4,3} and the mapping
𝜙2 (𝑥, 𝑦). They have the same order 𝑁𝐸 = 16 (which corresponds to the well-known
Tate theorem [11]), are isomorphic to each other, but instead of one they already have
3 points of the 2nd order (the curves are noncyclic) and 12 points of the 4th order. There
are two singular points of the 2nd and 4th order. The points of the original complete
curve E are denoted as 𝑃𝑖 , and the points of two isogenic curves 𝐸′ is as 𝑄𝑖 . As with
the doubling of points, the mapping 𝜙2 (𝑥, 𝑦) compresses the preimage (curve 𝐸) in
half, i.e. maps a pair of points of curve 𝐸 to one point of curve 𝐸′. Unlike doubling, 2-
isogeny does not necessarily halve the order of a point of even order.
On the curve E , we have points (±1,0), (0, ±1), (±2, ±4), (±3, ±3), (±4, ±2).
Let 𝑃1 = (2,4) is the point of the 16th order of the curve. 𝑃2 = (3,3) = 6𝑃1 is the point
of the 8th order, 𝑃3 = (4,2) = 11𝑃1 . On the isogenous curve 𝐸′ = 𝐸4 , except points
𝑂 = (1,0), 𝐷0 = (−1,0), ±𝐹0 = (0, ±1), we have singular points 𝐷1,2 = (±5, ∞),
±𝐹1 = (∞, ±5), and points of the 4th order (±2, ±3) and (±3, ±2). Let’s denote 𝑄1 =
(2,3), 𝑄2 = (3,2), 𝑃 ∗ = 𝑃 + 𝐷0 = (−𝑥1 , −𝑦1 ). Using the first function value 𝜙2 (𝑥, 𝑦)
we calculate
±𝜙2 (𝑃1 , 𝑃1∗ )(1) = (3, ±2) = ±𝑄2 ,
±𝜙2 (𝑃2 , 𝑃2∗ )(1) = (∞, ±5) = ±𝐹1 ,
±𝜙2 (𝑃3 , 𝑃3∗ )(1) = (−3, ±2) = ∓𝑄2∗ ,
𝜙2 (±𝐹0 )(1) = (−1,0) = 𝐷0 ,
𝜙2 (𝐷0 , 𝑂)(1) = (1,0) = 𝑂.
The second isogenic curve 𝐸′ = 𝐸3 with the parameter 𝑑 = 3, except points O, 𝐷0 , ±𝐹0,
has singular points 𝐷1,2 = (±2, ∞), ±𝐹1 = (∞, ±2), and the points of the 4th order
(±4, ±4) and (±5, ±5). Let 𝑅1 = (4,4) and 𝑅2 = (5,5). According to the second value
of the function 𝜙2 (𝑥, 𝑦)(2) we obtain
±𝜙2 (𝑃1 , 𝑃1∗ )(2) = (4, ∓4) = ∓𝑅1 ,
±𝜙2 (𝑃2 , 𝑃2∗ )(2) = (0, ±1) = ±𝐹0 ,
±𝜙2 (𝑃3 , 𝑃3∗ )(2) = (−4, ∓4) = ±𝑅1∗ ,
𝜙2 (±𝐹0 )(2) = (−1,0) = 𝐷0 ,
𝜙2 (𝐷0 , 𝑂)(2) = (1,0) = 𝑂.
11
So, the function 𝜙2 (𝑥, 𝑦) maps a pair of points of the same order of the curve to one
point of the curve 𝐸′ (i.e. the function 𝜙2 (𝑥, 𝑦) is a surjection), and one complete
Edwards curve is mapped to two isomorphic quadratic curves.
Example 2. Let’s construct the isogeny for the quadratic curve 𝐸 = 𝐸3 from example
1 with the parameters 𝑑 = 3, 1 − 𝑑 = 9, 𝛾 = 3. One of the isogenic curves when
mapping 𝜙2 (𝑥, 𝑦) has the same parameter 𝑑 = 3 and the same points 𝑅1 = (4,4), 𝑅2 =
(5,5), 𝐷1,2 = (±2, ∞), ±𝐹1 = (∞, ±2), ±𝐹0 = (∞, ±1), 𝐷0 , 𝑂. The mapping
𝜙2 (𝑥, 𝑦)(2) of this curve gives us the points of the curve 𝐸′
±𝜙2 (𝑅1 , 𝑅1∗ )(2) = (∞, ∓2) = ±𝐹1 ,
±𝜙2 (𝑅2 , 𝑅2∗ )(2) = (0, ∓1) = ∓𝐹0 ,
𝜙2 (±𝐹0 )(2) = (−1,0) = 𝐷0 ,
𝜙2 (±𝐹1 )(2) = (2, ∞) = 𝐷1 ,
𝜙2 (𝐷1 , 𝐷2 )(2) = (−2, ∞) = 𝐷2 ,
𝜙2 (𝐷0 , 𝑂)(2) = (1,0) = 𝑂.
If you reapply the function 𝜙2 (𝑥, 𝑦)(2) to the points of the isogenous curve 𝐸′, we obtain
the points of the curve 𝐸′′
𝜙2 (±𝐹0 )(2) = (−1,0) = 𝐷0 ,
𝜙2 (±𝐹1 )(2) = (2, ∞) = 𝐷1 ,
𝜙2 (𝐷1 , 𝐷2 )(2) = (−2, ∞) = 𝐷2 ,
𝜙2 (𝐷0 , 𝑂)(2) = (1,0) = 𝑂.
Thus, the second isogeny returns us to the points of the original curve (𝐸 ′′ = 𝐸), and
for two steps the mapped points of the curve 𝐸 are doubled (multiplied by 𝛼: points of
the 4th order are mapped into points of the 2nd order, and points of the 2nd order are to
the point 𝑂). This is an example of dual 2-isogeny 𝜙̂2 = 𝜙2 (𝑥, 𝑦)(2) for a quadratic
curve over a prime field.
Consider the isogenies of twisted Edwards curves over the field 𝐹𝑝 . According to
Proposition 3, they exist only at 𝑝 ≡ 3mod4 and 𝜒(𝛾) = 1, at the same time it is
possible to accept 𝑎 = 𝑎̅ = −1.
Example 3. Let 𝑝 = 19 and the twisted curve 𝐸−1,−9 with the parameters 𝑎 = −1,
𝑎𝑑 = −9, 𝛾 = √11 = ±7 is given. Its order is 𝑁𝐸 = 16. It has the points 𝑂, 𝐷0 ,
𝐷1,2 = (±6, ∞), and the points of the first quadrant 𝑃1 = (2,1), 𝑃2 = (3,6),
𝑃3 = (5,5) (total of 12 points of the 4th order with the coordinates (±𝑥, ±𝑦)). One of
the isogenous curves 𝐸′−1,−16 , when mapped 𝜙2 (𝑥, 𝑦), has the parameter
1−7 2
𝑑̅2 = ( ) = 16, the points 𝑂, 𝐷0 , 𝐷′1,2 = (±5, ∞), and the points of the 4th order of
1+7
the first quadrant 𝑄1 = (2,3), 𝑄2 = (7,8), 𝑄3 = (9,9) (total of 12 points of the 4th order
with the coordinates ( x, y ) ). The mapping 𝜙2 (𝑥, 𝑦)(1) of the curve 𝐸−1,−9 gives
the points of the first isogenous curve 𝐸′−1,−16
(−7 − 1)22 + 1
±𝜙2 (𝑃1 , 𝑃1∗ )(1) = ± ( = 2, (−7 − 1)2 = 3) = ±𝑄1 ,
(−7 + 1)22 − 1
±𝜙2 (𝑃2 , 𝑃2∗ )(1) = ±(−7,8) = ∓𝑄2∗ ,
±𝜙2 (𝑃3 , 𝑃3∗ )(1) = ±(−9,9) = ∓𝑄3∗ ,
𝜙2 (𝐷1 , 𝐷2 )(1) = (5, ∞) = 𝐷′1 ,
𝜙2 (𝐷0 , 𝑂)(1) = (1,0) = 𝑂.
12
The second isogenous curve 𝐸′−1,13 with the reverse meaning of the parameter
𝑑̅2−1 = 3−1 = 13 is isomorphic to the first one and contains the points 𝑂, 𝐷0 ,
𝐷′′1,2 = (±4, ∞), 𝑅1 = (2,2), 𝑅2 = (8,6), 𝑅3 = (9,7). The mapping 𝜙2 (𝑥, 𝑦)(2) of the
curve 𝐸−1,−9 gives the points of the 2nd isogenous curve 𝐸′−1,−6
(−7 + 1)22 − 1
±𝜙2 (𝑃1 , 𝑃1∗ )(2) = ± ( = −9, (−7 + 1)2 = 7) = ∓𝑅3∗ ,
(−7 − 1)22 + 1
±𝜙2 (𝑃2 , 𝑃2∗ )(2) = ±(8,6) = ±𝑅2 ,
±𝜙2 (𝑃3 , 𝑃3∗ )(2) = ±(2,2) = ±𝑅1 ,
𝜙2 (𝐷1 , 𝐷2 )(2) = (4, ∞) = 𝐷′1 ,
𝜙2 (𝐷0 , 𝑂)(2) = (1,0) = 𝑂.
In contrast to the isogenies of quadratic curves over a prime field, for twisted Edwards
curves that do not have singular 4th order points, pairs of 4th order points of the curve 𝐸
are mapped to one point of the same order of the curve 𝐸′. Halving the number of
singular points is an advantage of the class of twisted Edwards curves over quadratic
ones (when programming isogenies).
For isogeny 𝜙: 𝐸 → 𝐸′ there exists dual isogeny 𝜙̂: 𝐸′ → 𝐸, in such way that
𝜙°𝜙̂ = [deg(𝜙) = 𝛼] [11]. The formulas of Theorem 2 prove that over the field 𝐹𝑝 for
the complete Edwards curves, dual isogeny does not exist, but it exists in the extension
𝐹𝑝2 . To find dual isogeny 𝜙̂: 𝐸′ → 𝐸, for example to the function 𝜙1 (𝑥, 𝑦) with the
values of the isogenic curve
1−𝛿 2
𝑑1̅ ±1 = 𝑎̅ ( ) .
1+𝛿
It is necessary to solve the inverse problem: from the known value 𝑑1̅ of the curve 𝐸′ it
is necessary to calculate one of the suitable values of the parameter 𝛿 of the curve 𝐸,
which is determined by a similar formula
1 − √𝑎̅−1 𝑑1̅
𝛿 ±1 = .
1 + √𝑎̅−1 𝑑1̅
Hence we see that the dual mapping of the curve 𝐸′ to the complete and twisted
Edwards curves 𝐸 exists only in the extension 𝐹𝑝2 , in which all curves defined over the
field 𝐹𝑝 , have the properties of quadratic curves.
5 Conclusions
Thus, over the field 𝐹𝑝 there exists 2-isogenies 𝜙: 𝐸 → 𝐸′ from the complete curves to
the quadratic Edwards curves, from the quadratic curves to the quadratic Edwards
curves, and also from the twisted curves to the twisted Edwards curves. In the extension
𝐹𝑝2 all the curves defined over the field 𝐹𝑝 become quadratic Edwards curve (their
parameters 𝑎 and 𝑑 are the squares in the field 𝐹𝑝2 ), and for any such curve, there is a
pair of isogenic quadratic curves defined by Theorem 1. In practice, in this regard, the
isogenies of curves given over 𝐹𝑝 are calculated over the extension 𝐹𝑝2 . The
implementation of one of the promising algorithms for PQC Supersingular Isogenies
Diffie-Hellman (SIDH) [13] is based, as is known, on 2- and 3-isogeny of supersingular
13
elliptic curves. The use of fast twisted Edwards curve arithmetic will undoubtedly allow
the construction of more efficient cryptosystems.
References
1. Komarova, A.: The analysis of existing post-quantum approaches and electronic signature
schemes. Cybersecur. Issues 2(30): 58–68 (2019). https://doi.org/10.21681/2311-3456-
2019-2-58-68. [Publication in Russian]
2. Bernstein, D. J., Lange, T.: Faster addition and doubling on elliptic curves. Lect. Notes
Comput. Sci. 4833: 29–50 (2007). https://doi.org/10.1007/978-3-540-76900-2_3
3. Moody, D., Shumow, D.: Analogues of Velu’s formulas for isogenies on alternate models
of elliptic curves. Math. Computation 85(300), 1929–1951 (2015). https://doi.org/10.1090/
mcom/3036
4. Koblitz, N., Menezes, A.: A riddle wrapped in an Enigma. IEEE Secur. Priv. 14(6): 34–42
(2016). https://doi.org/10.1109/msp.2016.120
5. Bessalov, A. V.: Calculation of parameters of cryptic curves Edwards over the fields of 5 th
and 7th characteristic. Cybersecur. Educ. Sci. Tech. 1(1): 94–104 (2018).
https://doi.org/10.28925/2663-4023.2018.1.94104. [Publication in Ukrainian]
6. Bessalov, A., Grubiyan, E., Sokolov, V., Skladannyi, P.: 3- and 5-isogenies of supersingular
Edwards curves. Cybersecur. Educ. Sci. Tech. 4(8): 6–21 (2020).
https://doi.org/10.28925/2663-4023.2020.8.621
7. Bernstein, D. J., Birkner, P., Joye, M., Lange, T., Peters, C.: Twisted Edwards curves. Lect.
Notes Comput. Sci. 5023: 389–405 (2008). https://doi.org/10.1007/978-3-540-68164-9_26
8. Ahmadi, O., Granger, R.: On isogeny classes of Edwards curves over finite fields. J. Number
Theory 132(6), 1337–1358 (2012). https://doi.org/10.1016/j.jnt.2011.12.013
9. Bessalov, A. V.: Unique cryptographic properties of non-cyclic twisted Edwards curves.
Appl. Radioelectr. 17(1,2): 49–54 (2018). [Publication in Russian]
10. Bessalov, A. V.: Edwards Elliptic Curves and Cryptography (2017). [Publication in
Russian]
11. Bessalov, A. V., Tsygankova, O. V.: Number of curves in the generalized Edwards form
with minimal even cofactor of the curve order. Probl. Inf. Transm. 53(1): 92–101 (2017).
https://doi.org/10.1134/s0032946017010082
12. Washington, L.: Elliptic Curves. Discrete Mathematics and Its Applications (2008).
https://doi.org/10.1201/9781420071474
13. Jao, D., de Feo, L.: Towards quantum-resistant cryptosystems from supersingular elliptic
curve isogenies. Lect. Notes Comput. Sci. 7071: 19–34 (2011). https://doi.org/10.1007/978-
3-642-25405-5_2