This section constructs elliptic-curve groups, the standard source of groups of roughly 2 255 elements for which no discrete-logarithm attack faster than the generic O (N) attacks of 7.22 is known. The multiplicative groups F p × lack this property: the index-calculus algorithms exploit the factorisation of the integers behind the residues and run in subexponential time, so p must have thousands of bits to push the cheapest known attack beyond 2 128 operations. An elliptic curve is the solution set of a cubic equation in two variables together with one additional point, the “point at infinity”. The section proves that these points form an abelian group under a geometric rule (10.16, associativity in sketch), derives explicit addition formulas, including complete ones valid for every input pair, bounds the group order by Hasse’s theorem (10.22), and states the elliptic-curve discrete logarithm problem.
Throughout, K is a field whose characteristic (4.30) is neither 2 nor 3 ; in the applications K is a prime field F p with p large. The running example is the pair of Pasta curves
| E p : y 2 = x 3 + 5 over F p, E q : y 2 = x 3 + 5 over F q, |
where p and q are the two 255 -bit primes of 6.24 and 7.18,
| p | = 2 254 + 0 x 224698 f c 094 c f 91 b 992 d 30 e d 00000001, | ||
| q | = 2 254 + 0 x 224698 f c 0994 a 8 d d 8 c 46 e b 2100000001 . |
The primes and the curve equations are the deployed constants, specified in §5.4.9.6 (“Pallas and Vesta”) of the Zcash protocol specification. The curve E p is called Pallas and E q Vesta. By design they form a cycle: the number of F p -points of Pallas equals q , and the number of F q -points of Vesta equals p . A toy curve over F 11 is treated in parallel for hand computation.
Let K be a field of characteristic
| y 2 = x 3 + a x + b . | (9) |
The elements a and b are the Weierstrass coefficients.
Over a field of characteristic
Cubics whose graph has a self-intersection or a cusp are excluded, because the group law defined below fails at such a singular point.
The discriminant of the short Weierstrass equation (9) is
| Δ = − 16 (4 a 3 + 27 b 2) ∈ K . | (10) |
The equation, and the cubic
The following lemma expresses
Let
| ∏ i < j (r i − r j) 2 = − (4 a 3 + 27 b 2) . |
Expanding
| r 1 + r 2 + r 3 = 0, r 1 r 2 + r 1 r 3 + r 2 r 3 = a, r 1 r 2 r 3 = − b . |
Differentiating
| ∏ i f ′ (r i) = ∏ i < j (r i − r j) (r j − r i) = (− 1) 3 ∏ i < j (r i − r j) 2 . |
It remains to compute
| ∏ i (3 r i 2 + a) = 27 ∏ i r i 2 + 9 a ∑ i < j r i 2 r j 2 + 3 a 2 ∑ i r i 2 + a 3 . |
Vieta’s relations evaluate each symmetric function: with
| ∑ i r i 2 = e 1 2 − 2 e 2 = − 2 a, ∑ i < j r i 2 r j 2 = e 2 2 − 2 e 1 e 3 = a 2, ∏ i r i 2 = e 3 2 = b 2 . |
Substituting,
Let
The quantity
The cubic f has no repeated root in the algebraic closure K ̄ —the smallest extension field of K in which every nonconstant polynomial over K factors into linear factors.
The polynomials f and f ′ are coprime in K ̄ [x] .
There is no point
Equivalence
Equivalence
Equivalence
An elliptic curve over K is a short Weierstrass
equation (9) with nonzero
discriminant,
| E aff (L) = { (x, y) ∈ L × L : y 2 = x 3 + a x + b }, |
and the set of L -rational points is
| E (L) = E aff (L) ∪ { O }, |
where O is a single formal symbol called the point
at infinity. When
For the Pasta curves
The point O is the identity element of the group law
defined below. To exhibit it as a point of the curve, embed the affine
plane in the projective plane. A
point of the projective plane P 2 (K) is an
equivalence class
| Y 2 Z = X 3 + a X Z 2 + b Z 3 . | (11) |
Setting
The geometric definition of addition rests on one fact: a line meets a cubic curve in exactly three points, counted with multiplicity, once the point at infinity is included.
Let
If
Otherwise
5 draws the chord and the tangent
on the real points of
The reflection turns the rule that the three intersection points of any line with the curve add up to O into a group law with identity O : reflection across the x -axis sends an affine point (x, y) to (x, − y) , its additive inverse by the next subsection, and fixes O . The rule is stated here as a heuristic; every use of it below is discharged by explicit computation with the formulas of §10.4, which obtain the third intersection point from Vieta’s relations, as in 10.3.
Fix an elliptic curve
Define
| − O = O, − (x 1, y 1) = (x 1, − y 1) . |
The reflected point (x 1, − y 1) is again on the curve, since the
curve equation depends on y only through y 2 . Geometrically,
the line through P and − P is the vertical line
Suppose
| λ = y 2 − y 1 x 2 − x 1, μ = y 1 − λ x 1 . |
Substituting the line into the curve equation,
| g (x) := x 3 − λ 2 x 2 + (a − 2 λ μ) x + (b − μ 2) = 0 . |
Both x 1 and x 2 are roots of the monic cubic g : each
point lies on the line and on the curve, so
| x 3 = λ 2 − x 1 − x 2, y 3 = λ (x 1 − x 3) − y 1, | (12) |
and
Suppose
| λ = 3 x 1 2 + a 2 y 1 . |
With
| g ′ (x 1) = 3 x 1 2 + a − 2 λ (λ x 1 + μ) = 3 x 1 2 + a − 2 λ y 1 = 0 |
by the choice of λ , so x 1 is a repeated root of g
(5.40(1)). Factoring
(x − x 1) 2 out of g leaves a monic linear factor
| x 3 = λ 2 − 2 x 1, y 3 = λ (x 1 − x 3) − y 1, [2] P = (x 3, y 3) . | (13) |
The remaining cases are exactly those in which the line is vertical.
If
If
Every case is covered: either an input is O ; or both
inputs are affine with
For all
If either input is O , the result is the other input,
which lies in E (K) by hypothesis; if the result is O ,
it lies in E (K) by definition. Otherwise (x 3, y 3) is produced
by (12) or (13),
and in both constructions x 3 was exhibited as a root of the cubic
The chord formula (12) is incomplete:
it fails whenever
A circuit cannot branch. A proof system checks the group law by a fixed list of polynomial identities in the input, output, and auxiliary cells of a row, evaluated on every row alike, so each branch of the case analysis appears as a factor that vanishes exactly when the branch is not taken. The deployed gate uses five auxiliary cells, four of them “inverse-or-zero” hints that let a polynomial test a field element for zero.
Let
| α = inv 0 (x q − x p), β = inv 0 (x p), γ = inv 0 (x q), δ = { inv 0 (y q + y p) if x q = x p, 0 otherwise, | ||
| λ = { (y q − y p) α if x q ≠ x p, 3 x p 2 (2 y p) − 1 if x q = x p and y p ≠ 0, 0 otherwise, |
and an output pair (x r, y r) : it is Q if
| (x q − x p) ((x q − x p) λ − (y q − y p)) | = 0, | (C1) | ||
| (1 − (x q − x p) α) (2 y p λ − 3 x p 2) | = 0, | (C2) | ||
| x p x q (x q − x p) (λ 2 − x p − x q − x r) | = 0, | (C3a) | ||
| x p x q (x q − x p) (λ (x p − x r) − y p − y r) | = 0, | (C3b) | ||
| x p x q (y q + y p) (λ 2 − x p − x q − x r) | = 0, | (C3c) | ||
| x p x q (y q + y p) (λ (x p − x r) − y p − y r) | = 0, | (C3d) | ||
| (1 − x p β) (x r − x q) | = 0, | (C4a) | ||
| (1 − x p β) (y r − y q) | = 0, | (C4b) | ||
| (1 − x q γ) (x r − x p) | = 0, | (C5a) | ||
| (1 − x q γ) (y r − y p) | = 0, | (C5b) | ||
| (1 − (x q − x p) α − (y q + y p) δ) x r | = 0, | (C6a) | ||
| (1 − (x q − x p) α − (y q + y p) δ) y r | = 0 | (C6b) |
hold in F p . These are, in this order, the twelve constraints of the complete-addition gate of the halo2_gadgets crate, each carrying there one further factor, a per-row cell equal to 1 on the rows where the gate applies and 0 elsewhere, which switches the list on or off; the crate assigns the cells as above, and the circuit field is the Pallas base field F p .
Suppose no affine point of E (F p) has
(completeness) the prover’s cells satisfy
(C1)–(C6b), and the output pair encodes
(soundness) every
This is what complete means for a gate: the twelve identities are
satisfiable for every input pair—doublings, inverse pairs, and the
identity included—and the output they admit is unique, so they are
the graph of the total function
Under the hypothesis an encoded pair has
Case
Case
Case
Case
Case
Pallas satisfies both hypotheses of 10.14:
5 is a non-square in F p (7.16)
and − 5 is not a cube (10.26). The toy
curve
Let E be an elliptic curve over a field K . The set E (K) with the chord-and-tangent operation + of 10.7 is an abelian group with identity O .
Closure is 10.11. The next proposition establishes every remaining axiom except associativity.
The operation + on E (K) has the following properties.
The point O is a two-sided identity:
Every P has the two-sided inverse − P of
10.8:
The operation is commutative:
Item (1) is the first clause of 10.7.
For item (2), let
The remaining axiom is associativity,
The proof uses the classical Cayley–Bacharach theorem for plane
cubics: if two cubics with no common component meet in nine points counted
with intersection multiplicity, then any third cubic passing through eight
of them with the required multiplicities also passes through the ninth. To
prove
A complete, case-free treatment identifies E (K) with the
degree-zero part Pic 0 (E) of the divisor class group of
the curve via the map
For
The affine formulas (12)
and (13) each require a field
inversion, by
Two redundant systems serve this purpose. In (homogeneous)
projective coordinates, a triple
Scalar multiplication computes, for a point P and an integer
| [n] P = P + P + ⋯ + P ⏟ n times . |
Computing this by
If
For
The case
| [2] R j + 1 + [n j] P = [2 ⌊ n / 2 j + 1 ⌋ + n j] P = [⌊ n / 2 j ⌋] P, |
where the last step is the digit identity
Scalar multiplication by an n -bit scalar therefore costs O (n) group operations— O (n) field operations up to constant factors, or O (n log 2 p) bit operations with schoolbook field arithmetic. Elliptic-curve cryptography rests on the contrast between this forward map and the apparent hardness of inverting it (§10.11).
Let
Let E be an elliptic curve over F p . Write
| # E (F p) = p + 1 − t, |
which defines the integer t , called the trace of Frobenius. Then
| | t | ≤ 2 p ; |
equivalently, # E (F p) lies in the Hasse interval
The count has an exact character-sum expression. For fixed x , the
number of
| # E aff (F p) = ∑ x ∈ F p (1 + (x 3 + a x + b p)) = p + ∑ x ∈ F p (x 3 + a x + b p), |
so
The conceptual proof realises t as the trace of the p -power
Frobenius endomorphism
By Hasse’s theorem the relative deviation of the order from p is of order p − 1 / 2 , so the bound guarantees without a brute-force count that the group has about p elements, about 255 bits for the Pasta curves. The bound also underlies the point-counting algorithms (Schoof–Elkies–Atkin) that compute the exact order in polynomial time, by which curve designers certify their group orders.
Cryptographic use requires E (F p) to contain a large subgroup of prime order. The general structure theory of E (F p) is not needed in this series: the Pasta curves are designed so that # E (F p) is itself prime, and a group of prime order is cyclic with no proper nontrivial subgroups (3.34).
The order of a point
| E [m] = { P ∈ E (F p ̄) : [m] P = O }, |
the points over the algebraic closure killed by m ; its rational
part is
Suppose
A nontrivial cofactor
The affine points of order 2 in E (F p) are exactly the points
(x 0, 0) with
A point
Next, the number N of roots of f in F p can only be 0 ,
1 , or 3 : two roots force a third. Suppose f has distinct
roots
For the parity claim, consider negation
| # E (F p) ≡ 1 + N (mod 2), |
where
For
An elliptic-curve computation involves two prime fields. Every operation
of the group law on E (F p) —the slope
For an elliptic curve used in cryptography, with a prime-order subgroup of order r :
the base field F p is the field over which the curve is defined and in which point coordinates lie;
the scalar field
Both are prime fields, but in general
Scalar arithmetic runs in F r and coordinate arithmetic in F p . Halo 2’s Pallas and Vesta curves (the “Pasta” pair) form a cycle of curves: the base field of one is the scalar field of the other and vice versa,
| # E p (F p) = q, # E q (F q) = p, |
so the scalar field of Pallas is F q , the base field of Vesta, and
symmetrically (§5.4.9.6
of the Zcash protocol
specification). This lets a proof system express the verifier of one
curve’s arithmetic natively in the field of the other, which
enables the recursive proof composition of Halo 2. Both
primes are chosen
The discrete logarithm problem of 7.21, stated there for an abstract cyclic group, reads as follows for elliptic curves in additive notation.
Let
The map
Baby-step giant-step solves the ECDLP in a group of prime order r in O (r) group operations and O (r) space. Pollard’s rho method matches the O (r) bound in expectation with only O (1) space, under a modelling assumption on its pseudo-random walk that is stated explicitly in the proof and is unproved for every concrete walk.
For baby-step giant-step, set
Pollard’s rho eliminates the table, at the price of an explicitly
heuristic analysis. The algorithm takes a pseudo-random walk on G
whose every position is maintained in the form
| E [T] = ∑ k ≥ 1 Pr [T ≥ k] ≤ m ∑ j ≥ 0 Pr [T > j m] ≤ m (1 + ∑ j ≥ 1 e − j / 4) = O (r), |
where the middle step groups the indices k into blocks of length
m , bounding each block by its first term, and the last uses
| n ≡ (a − a ′) (b ′ − b) − 1 (mod r), |
the inverse existing because r is prime. If instead
For well-chosen curves, no unrestricted classical attack faster than
O (r) is known; this is not an unconditional lower bound for
all classical algorithms. In the classical generic-group model, however,
Shoup’s matching lower bound is proved
(7.22). For the 255 -bit Pasta orders
r , slightly above 2 254 , the square root is
In F p × the index-calculus method solves the discrete logarithm
in subexponential time L p [1 / 3] —shorthand for
2 Θ (λ 1 / 3 (log λ) 2 / 3) operations in the
bit length
The j -invariant classifies curves up to isomorphism; when it vanishes, as it does for the Pasta curves by design, the curve has an additional endomorphism.
The j -invariant of the curve
| j = 1728 4 a 3 4 a 3 + 27 b 2 ∈ K, |
where
Two elliptic curves over K ̄ are isomorphic over
K ̄ if and only if they have the same j -invariant.
The admissible coordinate changes preserving short Weierstrass form are
A direct computation shows that the only isomorphisms between short
Weierstrass curves fixing O are the scalings
For
Suppose F p contains a primitive cube root of unity ω ,
i.e.
| φ (x, y) = (ω x, y), φ (O) = O, |
is a group endomorphism of E (F p) . Let
| φ (Q) = [λ] Q for all Q ∈ G . |
For the Pasta curves the hypothesis
The map lands on the curve. If
The map is a homomorphism. We check
| λ ′ = y 2 − y 1 ω x 2 − ω x 1 = ω − 1 λ = ω 2 λ, |
using
| x 3 ′ = λ ′ 2 − ω x 1 − ω x 2 = ω 4 λ 2 − ω x 1 − ω x 2 = ω (λ 2 − x 1 − x 2) = ω x 3, |
| y 3 ′ = λ ′ (ω x 1 − x 3 ′) − y 1 = ω 2 λ ⋅ ω (x 1 − x 3) − y 1 = λ (x 1 − x 3) − y 1 = y 3, |
so
The relation
First let
| x 3 = 0 − x − ω x = − (1 + ω) x = ω 2 x, y 3 = 0 ⋅ (x − x 3) − y = − y, |
using
If instead
| λ = 3 ⋅ 0 2 + 0 2 y = 0, x 3 = 0 − 2 ⋅ 0 = 0, y 3 = 0 ⋅ (0 − 0) − y = − y, |
so
With
Action on G as a scalar. The subgroup
| [λ 2 + λ + 1] P = O ⟹ λ 2 + λ + 1 ≡ 0 (mod r), |
since P has order r . Consistently, this congruence is solvable
exactly when F r contains a primitive cube root of unity, i.e. when
Computing φ costs a single field multiplication
| [n] P = [n 1] P + [n 2] φ (P), n ≡ n 1 + n 2 λ (mod r), |
where
Take
| x x 3 mod 11 f (x) = x 3 + 5 y with y 2 = f (x) 0 0 5 ± 4 (4 2 = 16 ≡ 5) 1 1 6 none (6 ∉ QR) 2 8 2 none 3 5 10 none 4 9 3 ± 5 (5 2 = 25 ≡ 3) 5 4 9 ± 3 6 7 1 ± 1 7 2 7 none 8 6 0 0 9 3 8 none 10 10 4 ± 2 |
Counting: the five values
| # E (F 11) = 10 + 1 + 1 = 12 . |
Hasse’s bound holds:
An addition. Let
| λ = 3 − 4 5 − 0 = (− 1) ⋅ 5 − 1 = (− 1) ⋅ 9 = − 9 ≡ 2 (mod 11), |
using
| x 3 = λ 2 − x 1 − x 2 = 4 − 0 − 5 = − 1 ≡ 10, y 3 = λ (x 1 − x 3) − y 1 = 2 (0 − 10) − 4 = − 24 ≡ 9, |
so
A doubling. Take
| λ = 3 x 1 2 + a 2 y 1 = 0 8 = 0, x 3 = λ 2 − 2 x 1 = 0, y 3 = λ (x 1 − x 3) − y 1 = − 4 ≡ 7, |
so
The GLV endomorphism. Since
For the running example
Vesta, over F q : the order is
The cycle property
The discrete logarithm problem in E p (F p) and E q (F q) is
believed to require about 2 126 group operations: Pollard’s rho,
run on the classes of the automorphisms ± φ i , expects about
2 126.0 steps, against
We bound the expected step count of Pollard’s rho under the modelling
assumption of 10.30, applied to a walk on
a set of N elements (a forward reference: the probability results used
here belong to the closing section). The first k positions are pairwise
distinct with probability
| E [T] = ∑ k ≥ 0 ∏ i < k (1 − i N) ≤ 1 + ∑ j ≥ 0 e − j 2 / (2 N) ≤ 2 + ∫ 0 ∞ e − x 2 / (2 N) d x = 2 + π N / 2, |
the last sum bounded by the integral of its decreasing summand, which the
substitution
| E [T] = π N / 2 + 2 3 + O (N − 1 / 2) . |
Three walks apply to a Pasta group
The walk of 10.30 runs on the
A walk on the classes { R, − R } replaces each position by a
representative of its class fixed by a rule, and runs on
A walk on the classes
In a class walk a repeat presents positions
| π r / 2 ≈ 2 127.3, π r / 4 ≈ 2 126.8, π r / 12 ≈ 2 126.0 |
expected steps to the first repeat for the three walks, against