The Zcash ArboretumI–IX The Complete Arboretum
Contents
PDF
Theme

2 Hardness assumptions

This section states the hardness assumptions on which the group-based constructions of the volume rest: those of the discrete logarithm problem (DLP) and of the computational and decisional Diffie–Hellman problems (CDH, DDH), ordered by reduction. Each secret of these constructions—a spending key, the trapdoor of a commitment, the nonce of a signature—lies in ℤ/qℤ and is published only as gx; an adversary that computes discrete logarithms recovers signing keys from verification keys, opens commitments to values of its choice, and removes the blinding from every rerandomised key of later sections. The section proves the generic square-root bounds and the Pohlig–Hellman reduction, which together show that λ bits of security against generic attacks, λ the security parameter, require a group of prime order q with log2q≥2λ; instantiates the assumptions on the Pasta curves; and records that Shor’s quantum algorithm breaks all of them. Throughout, G=⟨g⟩ denotes a cyclic group of prime order q, written multiplicatively until §2.6 switches to the additive notation of elliptic curves.

2.1 The discrete logarithm problem

This subsection defines the discrete logarithm problem and proves that in prime order its average-case and worst-case hardness coincide. Recall from the Math Guide (§“The discrete logarithm problem”) that a group G is cyclic if G=⟨g⟩={gk:k∈ℤ} for some generator g. If |G|=q then ℤ/qℤ≅G via k↦gk, an isomorphism efficient to evaluate—repeated squaring costs O(logk) group operations—whose inversion, the discrete logarithm problem, is conjecturally infeasible.

Definition 2.1 (Discrete logarithm).

Let G=⟨g⟩ be a cyclic group of order q, written multiplicatively. For h∈G, the discrete logarithm of h to the base g, denoted loggh, is the unique residue x∈ℤ/qℤ with gx=h. Existence follows from G=⟨g⟩ and ord(g)=q; uniqueness because gx=gx′ forces gx−x′=1, whence q∣x−x′.

Definition 2.2 (Discrete logarithm problem, DLP).

Fix a family {Gλ} of cyclic groups, where Gλ=⟨gλ⟩ has prime order qλ with log2qλ=Θ(λ), together with a sampler that on input 1λ outputs a description of (Gλ,gλ,qλ). The game 𝖣𝖫𝖮𝖦𝒜(λ) runs as follows.

  1. 1.

    The challenger runs the sampler, draws x←$ℤ/qλℤ uniformly, and sends (Gλ,gλ,qλ,h=gλx) to the adversary 𝒜.

  2. 2.

    The adversary outputs x′∈ℤ/qλℤ.

  3. 3.

    The game outputs 1 iff gλx′=h.

The DLP assumption for the family states that for every PPT 𝒜,

Pr⁡[𝖣𝖫𝖮𝖦𝒜⁢(λ)=1]∈negl⁡(λ).

The order is required to be prime because a composite order splits the problem across its factors (§2.5).

Proposition 2.3 (Random self-reducibility of DLP).

In a cyclic group G=⟨g⟩ of prime order q, the discrete logarithm problem is random self-reducible: an algorithm solving a fraction ε of instances, over uniformly random h, converts into one solving any fixed instance with probability ε per trial. Consequently worst-case and average-case hardness coincide.

Proof.

Let 𝒜 succeed on a uniform target with probability ε. Given a fixed challenge h=gx, draw r←$ℤ/qℤ and form h′=h⋅gr=gx+r. Addition modulo q is a bijection and r is uniform, so h′ is uniform in G and independent of h; hence 𝒜(h′) returns x+rmodq with probability ε, and subtracting r recovers x. Each candidate is checked by testing gx=?h, so failures are recognised. Fresh randomness r per trial makes trials independent: t of them succeed with probability 1−(1−ε)t, overwhelming once t=ω(ε−1logλ). □

Random self-reducibility does not make every instance hard: the logarithm of the identity is immediate.

2.2 Diffie–Hellman: computational and decisional

This subsection defines the computational and decisional Diffie–Hellman problems, which concern the product of two exponents. In Diffie–Hellman key exchange the parties publish ga and gb and share ga⁢b, which each computes from the other’s public value and its own exponent; an eavesdropper observes g,ga,gb and must be unable to obtain ga⁢b.

Definition 2.4 (Computational Diffie–Hellman, CDH).

With notation as in Definition 2.2, the game 𝖢𝖣𝖧𝒜(λ) runs as follows: the challenger draws a,b←$ℤ/qℤ independently and sends (g,ga,gb); the adversary outputs z∈G; the game outputs 1 iff z=ga⁢b. The CDH assumption states that for every PPT 𝒜,

Pra,b⁡[𝖢𝖣𝖧𝒜⁢(λ)=1]∈negl⁡(λ).

An adversary may be unable to compute ga⁢b yet able to distinguish it from a random group element, and such a distinguisher already breaks, for example, the indistinguishability of an ElGamal ciphertext. The decisional variant excludes such distinguishers.

Definition 2.5 (Decisional Diffie–Hellman, DDH).

The decisional Diffie–Hellman problem is to distinguish two distributions over G3,

𝒟dh=(ga,gb,ga⁢b),𝒟rand=(ga,gb,gc),

with a,b,c independent and uniform in ℤ/qℤ; this is the distinguishing game of Definition 1.15, the challenger handing over a sample of one or the other according to its hidden bit. The DDH assumption states that every PPT distinguisher D has negligible advantage

Advddh⁢(D)=|Pra,b⁡[D⁢(ga,gb,ga⁢b)=1]−Pra,b,c⁡[D⁢(ga,gb,gc)=1]|∈negl⁡(λ).

A triple (ga,gb,gc) with c≡ab(modq) is a Diffie–Hellman triple; the assumption says no efficient distinguisher recognises such triples.

Remark 2.6 (DDH admits a random self-reduction).

Rerandomisation applies to DDH as to DLP, by the following map. Given a target triple (u,v,w)=(ga,gb,gc), choose α,γ←$(ℤ/q⁢ℤ)× and β,δ←$ℤ/qℤ, and form

(u′,v′,w′)=(uα⁢gβ,vγ⁢gδ,wα⁢γ⁢uα⁢δ⁢vβ⁢γ⁢gβ⁢δ).

Writing A=αa+β, B=γb+δ, and E=c−ab, the new exponents are A, B, and AB+αγE, with A and B uniform and independent. A DH triple (E=0) therefore becomes a fresh uniform DH triple; a non-DH triple becomes uniform conditional on being non-DH, because αγE is uniform in (ℤ/q⁢ℤ)×. The latter distribution lies at statistical distance (Definition 1.6) 1/q from 𝒟rand, whose third component completes a DH triple by accident with probability 1/q. A noticeable distinguishing advantage on random instances thus transfers to every fixed triple, up to this negligible term.

2.3 The assumption hierarchy

This subsection orders the three problems by reduction. Write A≤B for “A reduces to B”: an oracle solving B yields an efficient solver for A, so B is at least as hard as A, and the assumption “A is hard” is the stronger commitment, since it implies “B is hard”. The reductions of this subsection give

DDH≤CDH≤DLP,

so assuming DDH hard is the strongest commitment and assuming DLP hard the weakest.

Theorem 2.7 (DLP is at least as hard as CDH).

If DLP is solvable in PPT, then CDH is solvable in PPT. Equivalently, the CDH assumption implies the DLP assumption.

Proof.

Suppose 𝒜 solves DLP. Given a CDH instance (g,ga,gb), run 𝒜 on (g,ga) to recover a, then compute (gb)a=ga⁢b by fast exponentiation. The cost is one DLP call plus O(logq) group operations; only one of the two exponents is inverted. □

Theorem 2.8 (CDH is at least as hard as DDH).

If CDH is solvable in PPT with non-negligible success probability, then DDH is solvable in PPT with non-negligible advantage; if the success probability is noticeable, rerandomisation drives the advantage overwhelmingly close to 1. Equivalently, the DDH assumption implies the CDH assumption.

Proof.

Suppose 𝒜 solves CDH with probability ε. Build a distinguisher D: on input (ga,gb,z), call 𝒜(g,ga,gb) to obtain a candidate w, and output 1 iff w=z. On a Diffie–Hellman triple, z=ga⁢b, so D outputs 1 whenever 𝒜 succeeds, that is, with probability ε. On a random triple, z=gc with c uniform and independent of a,b, while w depends only on (ga,gb); the event w=z therefore has probability exactly 1/q. Hence

Advddh⁢(D)≥ε−1q,

non-negligible whenever ε is, since 1/q is negligible.

For the amplified form let ε be noticeable. The distinguisher D′ rerandomises its input t times independently by the map of Remark 2.6, runs D with fresh coins on each copy, and outputs 1 iff some copy answered 1. A DH input becomes t independent uniform DH triples, each accepted with probability ε, so D′ accepts with probability at least 1−(1−ε)t. A sample of 𝒟rand fails to be a DH triple except with probability 1/q, and then each copy’s third component is uniform over the q−1 non-completing values given the first two, so each copy is accepted with probability at most 1/(q−1) and D′ accepts with probability at most 1/q+t/(q−1). With t=ω(ε−1logλ), polynomial because ε is noticeable, the advantage of D′ is 1−negl(λ). □

Example 2.9 (DDH can be easy while CDH and DLP are hard).

Some elliptic-curve groups carry an efficiently computable, non-degenerate bilinear pairing e:G×G→GT with e(ga,gb)=e(g,g)a⁢b. On such a group DDH is easy: to test whether (ga,gb,z) is a DH triple, check

e⁢(ga,gb)=?e⁢(g,z),

which holds iff loggz≡ab(modq). Yet CDH—and a fortiori DLP—may remain hard, because the pairing reveals ga⁢b only inside the target group GT, never as an element of G. Such groups, called gap groups, separate DDH from CDH and are the setting of pairing-based cryptography. The DDH assumption is therefore strictly stronger than the CDH assumption: a “DDH group” must admit no efficiently computable pairing of this kind on G itself.

Figure 3 draws the ordering, with the separation of Example 2.9.

Refer to caption
Figure 3: The three problems of §2.2 ordered by reduction. Each downward arrow (blue) converts a solver for the upper problem into one for the lower (Theorems 2.7 and 2.8), so that DDH≤CDH≤DLP. Each upward arrow (green) reads the same reduction as an implication between assumptions, the DDH assumption being the strongest and the DLP assumption the weakest. In a gap group (amber; Example 2.9) the pairing e decides DDH but yields ga⁢b only in the target group GT, so it gives no CDH solver (struck edge): there DDH detaches from CDH.
Remark 2.10 (The converses are open).

The reverse reductions are not known in general. Whether an oracle computing ga⁢b yields a is the longstanding Diffie–Hellman versus discrete log question; partial results of den Boer and Maurer establish equivalence when a suitable auxiliary group of smooth order—an order that is a product of small primes—is available, but no unconditional equivalence is known. In the other direction DDH may be strictly easier than CDH, as Example 2.9 shows. Each protocol therefore assumes exactly the strength it requires: signatures and key exchange often need only CDH, while ElGamal-style encryption needs DDH for its ciphertexts to hide the plaintext.

2.4 Generic algorithms and the square-root barrier

This subsection proves that two generic discrete-logarithm algorithms achieve O(q) group operations and that no generic algorithm does asymptotically better. In a group with no exploitable structure beyond the group law, the best known algorithms are generic: they manipulate group elements only through multiplication, inversion, and equality testing, never inspecting the bit-representation of an element. Shoup’s idealisation makes the class precise: a random injective labelling σ:ℤ/qℤ→S encodes the element gk as the opaque string σ(k), and the algorithm may only ask an oracle for σ(i+j) given σ(i) and σ(j), and compare labels for equality.

Baby-step giant-step

Proposition 2.11 (Baby-step giant-step, BSGS).

In a cyclic group of order q, any discrete logarithm can be computed in O(q) group operations and O(q) stored group elements, deterministically and unconditionally.

Proof.

Let m=⌈q⌉. Since m2≥q, every x∈{0,…,q−1} decomposes as

x=i⋅m+j,0≤i<m,0≤j<m,

and the target relation gx=h becomes gj=h⋅(g−m)i. Baby steps: compute and store the table {(j,gj):0≤j<m}, indexed by group element in a hash map—m−1 multiplications. Giant steps: set u=g−m (one inversion plus one exponentiation, O(logq) operations) and for i=0,1,2,… compute h⋅ui incrementally, looking each value up in the table. The decomposition guarantees some pair (i,j) matches, yielding x=im+j after at most m giant steps. Total: O(q) operations and O(q) memory. □

Remark 2.12 (Memory is the bottleneck).

The O(q) memory of BSGS, not its time, is the binding constraint in practice: at the 128-bit security level no attacker can store q≈2128 table entries. Pollard’s rho method matches the time bound with negligible memory, which is why rho, rather than BSGS, is the realistic generic attack.

Pollard’s rho

Proposition 2.13 (Pollard’s rho, sketch).

In a cyclic group of prime order q there is a randomised algorithm computing discrete logarithms in expected O(q) group operations and O(1) storage.

Proof.

Sketch. Walk pseudo-randomly on G, keeping with each visited element its known representation gαhβ. Partition G into three roughly equal sets S1,S2,S3 by an easily computed function of the element’s label, and from P=gαhβ step to

f⁢(P)={h⋅P=gα⁢hβ+1,P∈S1,P2=g2⁢α⁢h2⁢β,P∈S2,g⋅P=gα+1⁢hβ,P∈S3,

each step updating (α,β)∈(ℤ/q⁢ℤ)2 explicitly at O(1) cost. The sequence eventually cycles: a tail leading into a loop, in the shape of the letter ρ. Modelling f as a random function on q elements, the birthday bound (Math Guide, §“The union bound and a birthday calculation”) produces a collision Pi=Pj, i≠j, within O(q) steps in expectation. A collision gives gαihβi=gαjhβj, hence gαi−αj=hβj−βi; writing h=gx,

αi−αj≡x⁢(βj−βi)(modq),

and if βj≢βi the difference is invertible modulo the prime q, so x≡(αi−αj)(βj−βi)−1(modq). Floyd’s tortoise-and-hare cycle detection, or Brent’s improvement, finds the collision with O(1) memory, never storing the trajectory. The exceptional case βj≡βi occurs with probability O(1/q); re-randomising the start point handles it. □

Remark 2.14 (Cost, not time, and constant factors).

Pollard rho parallelises with near-linear speedup via the van Oorschot–Wiener method of distinguished points: each of P processors walks independently and reports to a shared table only the points whose label satisfies a cheap predicate, say a run of leading zero bits; two walks that ever meet coincide from then on and are detected at the next distinguished point, so the processors achieve q/P wall-clock time with modest communication. The security-relevant measure is therefore the cost of the attack—the total operation count q, read as the attacker’s budget—not the time on any single machine. A further constant-factor saving applies in groups admitting the ± automorphism P↦−P, as elliptic curves do: identifying P with −P halves the effective search space and lowers the expected count from π⁢q/2 to π⁢q/4, a factor 2 that leaves the Θ(q) scaling untouched. The constant is the birthday integral: a random walk on N points is still collision-free after k steps with probability ∏i<k(1−i/N)≈e−k2/2⁢N (the product in the birthday calculation cited above), and summing over k gives an expected first-collision index of ∫0∞e−k2/2⁢N𝑑k=π⁢N/2.

The generic lower bound

Shoup’s lower bound, the square-root barrier, shows that up to constant factors the two attacks are the best possible generic algorithms.

Theorem 2.15 (Shoup’s generic lower bound).

Let q be prime. Any generic algorithm that makes at most n queries to the group oracle outputs the discrete logarithm of a uniformly random challenge with probability at most

(n+22)+1q=O⁢(n2q).

In particular, constant success probability requires n=Ω(q) queries.

Proof.

Sketch—the linear-polynomial technique. In the idealisation, the challenge logarithm is an indeterminate X drawn uniformly from ℤ/qℤ. By induction on the queries, every element the algorithm forms is σ of a known linear polynomial ai+biXmodq whose coefficients the algorithm chose. Treat X formally: as long as the polynomials produced are pairwise distinct as functions of X, the labels seen are consistent with X taking any value, so the algorithm has learnt nothing about it and can do no better than guess, succeeding with probability 1/q. Information leaks only through an accidental collision: two distinct polynomials agreeing at the secret x, that is, (ai−aj)+(bi−bj)x≡0(modq). For a fixed pair this nonzero linear equation has at most one root modulo the prime q—the degree-one case of the Schwartz–Zippel lemma (Math Guide, §“The Schwartz–Zippel lemma”)—so it holds with probability at most 1/q over uniform x. With n queries plus the two inputs g and h there are at most (n+22) pairs, and the union bound (Math Guide, §“The union bound and a birthday calculation”) caps the collision probability at (n+22)/q. Adding the 1/q guess yields the bound; solving n2/q=Ω(1) gives n=Ω(q). □

Corollary 2.16 (Why log2q≥2λ).

To force every generic attacker to spend at least 2λ group operations—λ bits of security against generic attacks—the prime group order must satisfy

q≳ 2λ⟺log2⁡q≥ 2⁢λ.
Proof.

Propositions 2.11 and 2.13 show that Θ(q) operations suffice for a generic attacker, and Theorem 2.15 shows no generic attacker does asymptotically better. Equating the attacker’s cost q with the target work factor 2λ gives q≈22⁢λ; demanding at least this much is log2q≥2λ. □

Example 2.17 (The 128-bit target).

For λ=128 the corollary demands a prime group order with log2q≥256. This is the reason for the standardised 256-bit elliptic curves: NIST P-256 (secp256r1) has a 256-bit field and a 256-bit group order, so q≈2128.0. The Pasta curves of §2.6, with 255-bit orders slightly above 2254 and about 126 bits of security, fall slightly below this class. In the multiplicative group 𝔽p×, by contrast, the sub-exponential index calculus of Remark 2.18 forces log2p into the thousands of bits for the same λ. Elliptic curves are used precisely because no sub-exponential algorithm that beats the generic attacks is known for them.

Remark 2.18 (Why the barrier is special to elliptic curves).

The square-root barrier governs generic groups only; a concrete representation can expose structure that beats it. The multiplicative group 𝔽p× is the standard example: index calculus exploits the factorisation of integers into small primes—smooth numbers—to solve DLP in sub-exponential time

exp⁡(O⁢((log⁡p)1/3⁢(log⁡log⁡p)2/3)),

far below p. No analogue is known for the points of a well-chosen elliptic curve over 𝔽p: there is no useful notion of a “small” point over which to factor. This non-generic gap is why elliptic-curve groups suffice at 256 bits where 𝔽p× requires about 3072 bits for the same security. It also means the rule log2q≥2λ protects against generic attacks only; a curve must additionally be screened against the special-purpose attacks of Definition 2.24.

2.5 Pohlig–Hellman and the necessity of large prime order

This subsection proves the Pohlig–Hellman reduction and derives from it the rule for choosing the group order. The square-root barrier puts the cost of an attack at q for prime q; if the group order factors, the discrete logarithm splits into independent subproblems the size of the factors, and the cost falls to that of the largest prime dividing the order.

Theorem 2.19 (Pohlig–Hellman).

Let G=⟨g⟩ have order N=∏i=1rpiei with the pi distinct primes. Then a discrete logarithm in G can be computed in

O⁢(∑i=1rei⁢(log⁡N+pi))

group operations. The term pmax dominates, where pmax is the largest prime dividing N.

Proof.

We compute x=loggh modulo each prime power piei and recombine by the Chinese Remainder Theorem, the moduli being pairwise coprime with product N.

Reduction to prime-power order. Fix p=pi, e=ei, and put gi=gN/pe, hi=hN/pe. Then gi has order exactly pe, and loggihi≡x(modpe): raising to N/pe eliminates the part of x coprime to p’s power and leaves xmodpe. It therefore suffices to solve DLP in ⟨gi⟩ of order pe.

Reduction to prime order, digit by digit. Write the unknown in base p:

x≡x0+x1⁢p+⋯+xe−1⁢pe−1(modpe),0≤xk<p.

Let γ=gipe−1, an element of order exactly p. Raising hi to the power pe−1 gives

hipe−1=gix⁢pe−1=γx0,

because every higher digit contributes a multiple of pe to the exponent and annihilates γ. Thus x0 is a single discrete logarithm in a group of prime order p, solvable in O(p) operations by BSGS or rho (Propositions 2.11 and 2.13). Having x0, set hi(1)=hi⋅gi−x0; its logarithm is divisible by p, and the same step at exponent pe−2 yields x1. Iterating recovers all e digits with e prime-order DLPs of cost O(p) each, plus O(elogN) operations of exponentiation. Summing over i and applying the CRT gives the stated bound. □

Example 2.20 (A composite-order trap).

Suppose, contrary to good practice, a group has order N=2256−1. The order factors completely into

2256−1= 3⋅5⋅17⋅257⋅641⋅65537⋅274177⋅6700417⋅67280421310721
⋅59649589127497217⋅5704689200685129054721,

a product of small primes—it is smooth. Despite N having 256 bits, the largest prime factor is only about 272.3, far below 2128, so Pohlig–Hellman with rho in the largest subgroup solves DLP in roughly pmax≈236.1 operations, about 236, far below the nominal 128-bit level. A 256-bit order is necessary but not sufficient: it must be (almost) prime.

Corollary 2.21 (Design rule for the group order).

For DLP-based security at level λ, the group order must be divisible by a prime q with log2q≥2λ, and the cryptographic group must be, or be restricted to, the subgroup of order q. When the ambient group has order N=h⋅q with small cofactor h and large prime q, one works in the order-q subgroup; clearing the cofactor—multiplying incoming elements by h, or checking subgroup membership—prevents small-subgroup attacks that would otherwise leak xmodh via Pohlig–Hellman on the order-h part.

Remark 2.22 (Prime order and Pohlig–Hellman).

The “prime order” of Definition 2.2 makes Pohlig–Hellman vacuous (the only factor is q itself), makes every non-identity element a generator (no element lies in a weak proper subgroup), and eliminates cofactor handling. The Pasta curves below are constructed to have prime order, hence cofactor 1.

2.6 Instantiation on elliptic curves; the Pasta curves

This subsection fixes the concrete groups used in the remainder of the volume. Recall from the Math Guide (§“Elliptic curves”, with the group law in §“The group structure of E(𝔽p)”) that an elliptic curve over 𝔽p, for p>3 prime, in short Weierstrass form is

E:y2=x3+a⁢x+b,a,b∈𝔽p,4⁢a3+27⁢b2≠0,

and that its set of 𝔽p-points,

E⁢(𝔽p)={(x,y)∈𝔽p2:y2=x3+a⁢x+b}∪{𝒪},

equipped with chord-and-tangent addition and the point at infinity 𝒪 as identity, forms a finite abelian group. The discrete logarithm problem in this group—given P and Q=[x]P, find x—is the elliptic-curve discrete logarithm problem (ECDLP), stated for elliptic curves in the Math Guide (§“The elliptic-curve discrete logarithm problem”); CDH and DDH transcribe verbatim with multiplicative notation replaced by the additive scalar multiplication x↦[x]P, giving ECCDH and ECDDH.

Theorem 2.23 (Hasse bound, recalled).

For E over 𝔽p (Math Guide, §“The group structure of E(𝔽p)”),

|#⁢E⁢(𝔽p)−(p+1)|≤ 2⁢p,i.e.#⁢E⁢(𝔽p)=p+1−t,|t|≤2⁢p,

where t is the trace of Frobenius. The group order is thus p+1 up to a deviation of order p.

For λ-bit security the prime p is chosen with about 2λ bits, so that #E(𝔽p)≈p≈22⁢λ, and, following Corollary 2.21, #E(𝔽p) is required to be prime—cofactor 1. ECDLP, ECCDH, and ECDDH are then assumed at the level Corollary 2.16 predicts, provided the curve avoids the known structural attacks that beat the generic bound; the following criteria screen for them.

Definition 2.24 (Secure-curve criteria).

A curve E/𝔽p of prime order q=#E(𝔽p) is admissible for λ-bit DLP security if:

  1. 1.

    (Size / generic.) The order satisfies log2q≥2λ, so Pollard rho costs at least 2λ operations (Corollary 2.16).

  2. 2.

    (Prime order.) The order q is prime, so Pohlig–Hellman is vacuous and the cofactor is 1 (Corollary 2.21).

  3. 3.

    (Anti-MOV / large embedding degree.) The multiplicative order k of p modulo q—the embedding degree—is large. The MOV/Frey–Rück attack uses a pairing to embed E(𝔽p) into 𝔽pk× and runs the sub-exponential index calculus of Remark 2.18 there; the attack is effective only for small k, as on supersingular curves—over a prime field p>3, those with trace t=0, so that #E(𝔽p)=p+1 divides p2−1 and k≤2. A curve with t≠0 is ordinary.

  4. 4.

    (Anti-Smart / not anomalous.) The order avoids q=p: on an anomalous curve, #E(𝔽p)=p with trace t=1, the Smart–Satoh–Araki–Semaev attack solves ECDLP in polynomial time.

  5. 5.

    (Twist security.) The quadratic twist E′—the curve dy2=x3+ax+b for a fixed nonsquare d∈𝔽p; every x∈𝔽p is the x-coordinate of a point of E or of E′—should also have large prime order, so that a fault or an invalid-point injection cannot move the computation onto a weak twist.

Definition 2.25 (The Pasta curves).

The Pasta curves are a pair, Pallas and Vesta, in short Weierstrass form

y2=x3+5

(so a=0, b=5, a j-invariant-0 shape), defined over two 255-bit primes p and q arranged in a cycle:

#⁢Pallas=q(Pallas defined over ⁢𝔽p),#⁢Vesta=p(Vesta defined over ⁢𝔽q).

The order of each curve equals the field of definition of the other. Both primes are congruent to 1mod232, giving their multiplicative groups large 2-adic valuation for fast FFTs, and each curve has cofactor 1: the whole group is of prime order. The primes themselves are assembled digit by digit in the Math Guide (§“Pallas and Vesta assembled”), and the field/scalar bookkeeping of the cycle in §“Base fields, scalar fields, and the Pasta cycle” there.

Remark 2.26 (The role of the curve cycle).

The cycle property #Pallas=q, #Vesta=p makes (Pallas, Vesta) an amicable, or cyclic, pair: one curve’s scalar field is the other’s coordinate field. A proof system can therefore use Pallas-arithmetic to verify statements about Vesta-arithmetic and vice versa without non-native field emulation; this is the mechanism behind recursive proof composition in Halo 2, whose recursion alternates between the two curves. The cycle is an efficiency property, not a security one: it does not enter the hardness assumptions, and each curve is screened independently against Definition 2.24.

Proposition 2.27 (The Pasta curves against the criteria).

The curves Pallas and Vesta satisfy criteria (1)–(4) of Definition 2.24 at λ≈126. Criterion (5) fails for both curves—neither twist has prime order, and the Pallas twist falls below the SafeCurves 2100 twist-attack cost threshold—but mandatory point validation makes the failure inconsequential.

Proof.

Sketch, criterion by criterion.

(1) Each order is a 255-bit prime slightly above 2254, so log2q≈254.0 and the bare generic cost is q≈2127.0. Plain Pollard rho expects about π⁢q/2≈2127.3 operations; the ± automorphism speedup of Remark 2.14 lowers this to π⁢q/4≈2126.8; and the order-6 automorphism group of these j-invariant-0 curves—the factor m for an order-m automorphism group of Remark 2.28, here an extra 3—lowers it to π⁢q/12≈2126.0. Hence “about 126 bits” of security, the same range as the 128-bit curves of Example 2.17.

(2) Both orders are prime by construction: cofactor 1, Pohlig–Hellman vacuous.

(3) Both curves are ordinary: the trace t=p+1−q is odd, so t≠0. The embedding degree k of each is large. For Pallas, q−1=232⋅32⋅1709⋅24859⋅C with C a 194-bit composite, and p(q−1)/32≢1 and p(q−1)/ℓ≢1(modq) for ℓ∈{3,1709,24859}, so the order k of p modulo q is a multiple of 228⋅32⋅1709⋅24859>256; for Vesta, p−1=232⋅3⋅463⋅C′, and q(p−1)/4≢1, q(p−1)/ℓ≢1(modp) for ℓ∈{3,463} make k a multiple of 231⋅3⋅463>241. Either extension field lies far beyond the reach of any feasible index-calculus computation; MOV/Frey–Rück does not apply.

(4) Neither curve is anomalous: #Pallas=q≠p and #Vesta=p≠q, so the trace t=p+1−q≠1 and the Smart attack does not apply.

(5) Twist security is the criterion the pair does not meet. The Pasta search deliberately ignored it—the curves were generated with the search flag --ignoretwist of the amicable.sage search recorded in the README of the zcash/pasta repository—and neither twist has prime order. Each x∈𝔽p supplies two affine points in total, on E or on E′ (one on each when x3+b=0), so #E+#E′=2(p+1) and #E′=2(p+1)−#E=p+1+t; hence #Pallas′=2(p+1)−q and #Vesta′=2(q+1)−p, which factor as

#⁢Pallas′ =32⋅7⋅8191⋅85021⋅11540602760389⋅P176,
#⁢Vesta′ =33⋅7⋅13⋅2851⋅30097⋅P217,

with P176 a 176-bit prime and P217 a 217-bit prime. The best attack on the Pallas twist therefore costs about P176≈287.6, below the SafeCurves 2100 twist-security threshold; the Vesta twist clears the threshold at about 2108.2. The failure has no consequence in this setting: twist attacks require an implementation that accepts an attacker-supplied x-coordinate without validation (an x-only ladder) or that skips its on-curve checks, and the deployed protocol admits neither. Protocol specification § 5.4.9.6 decodes a point by recovering y as a square root of x3+b; its decoding map returns ⊥ (failure) when no root exists, exactly when x lies on the twist, and an implementation must not assume that the root exists or that the encoding lies on the curve. Orchard decodes its points through this map, and cofactor 1 leaves no small subgroup on the curve itself. Invalid-curve and twist-point injection are therefore excluded by validation, not by twist structure.

The standard generic analysis therefore governs, and the security level is about 126 bits. □

Remark 2.28 (j-invariant 0 and endomorphisms).

The shape y2=x3+b gives j-invariant 0, and with it an extra automorphism of order 3 (Math Guide, §“The j-invariant and the GLV endomorphism”): for ω a primitive cube root of unity in 𝔽p, the cheap endomorphism ϕ(x,y)=(ωx,y) acts on the group as multiplication by a fixed scalar ζ with ζ2+ζ+1≡0(modq) (the λ of the Math Guide’s proposition), enabling the GLV speedup for honest scalar multiplication. The same endomorphism gives the attacker a slightly larger automorphism group, and with it the constant-factor Pollard-rho speedup used in Proposition 2.27—a factor m for an order-m automorphism group—but that is a small constant and does not change the Θ(q) scaling. Beyond that constant, the extra automorphism is not known to weaken ECDLP; the structural weaknesses at issue are small embedding degree and anomalousness, both excluded above.

2.7 Quantum adversaries: Shor’s algorithm

Every assumption above restricts the adversary to classical PPT computation. This subsection states which of them fail against a large fault-tolerant quantum computer and which primitives remain secure.

Theorem 2.29 (Shor, informal; stated without proof).

There is a quantum algorithm that, given a cyclic group G=⟨g⟩ of order q with efficient group operations and a target h=gx, outputs x in time polynomial in logq, succeeding with overwhelming probability. Consequently DLP—and with it CDH and DDH—falls in quantum polynomial time in any group, elliptic-curve groups included.

Discrete logarithm is an instance of the hidden subgroup problem over (ℤ/q⁢ℤ)2: the function f(α,β)=gαh−β=gα−x⁢β is constant exactly on the cosets of

H={(α,β):α≡x⁢β(modq)}=⟨(x,1)⟩⊆(ℤ/q⁢ℤ)2,

a line of slope x. The algorithm prepares a uniform superposition over (ℤ/q⁢ℤ)2, evaluates f into a second register, and applies the quantum Fourier transform—the reversible change of basis into the characters of (ℤ/q⁢ℤ)2, the homomorphisms χu,v(α,β)=e2⁢π⁢i⁢(u⁢α+v⁢β)/q into the unit circle; measurement then samples characters trivial on H, i.e. pairs (u,v) with ux+v≡0(modq), and a small number of samples determine the slope x by classical linear algebra modulo q. The whole procedure uses O(poly(logq)) qubits and gates, and it accesses the group only through the black-box map (α,β)↦gαh−β, so it is independent of the representation: elliptic-curve DLP falls exactly as 𝔽p× DLP does, and integer factoring falls to the order-finding variant.

Remark 2.30 (No contradiction with the square-root barrier).

Shoup’s lower bound (Theorem 2.15) assumes the generic model for classical algorithms making sequential, individual oracle queries. Shor’s algorithm is non-generic in exactly the relevant sense: it queries the group function in superposition and exploits the periodicity the Fourier transform exposes, abilities the classical generic model does not grant.

Remark 2.31 (Primitives broken and unbroken by Shor’s algorithm).

Shor’s algorithm breaks the entire discrete-log family and integer factoring in polynomial time: RSA, finite-field Diffie–Hellman, and elliptic-curve cryptography are all quantum-broken. It does not break the following.

  • •

    Symmetric primitives and hash functions. Grover’s algorithm searches a space of size 2n in about 2n/2 quantum queries—a quadratic, not exponential, speedup—so a cipher with a 2λ-bit key, or an n=2λ-bit hash against preimages, retains λ bits of quantum security. Generic quantum collision finding instead costs Θ(2n/3) queries, so in the query metric an output of about 3λ bits is needed for λ-bit quantum collision security—though the algorithm needs comparably much quantum memory, and whether it beats classical parallel collision search in realistic cost models is debated. Doubling therefore suffices for key search and preimages, but for collisions only under that contested cost reading.

  • •

    Post-quantum assumptions. Hardness assumptions based on neither discrete logarithms nor factoring are not known to fall to Shor and underlie post-quantum cryptography.

The discrete-log assumptions of this volume are therefore adopted under the standing premise that no cryptographically relevant quantum computer exists. Within that premise, and against all classical attacks, the Pasta curves provide the approximately 126-bit security of Proposition 2.27, on which the later Halo 2 constructions rely.

2.8 Standing assumptions

Remark 2.32 (Standing assumptions for the sequel).

We collect the premises the rest of the volume relies on. For each Pasta curve C∈{Pallas,Vesta} with prime order qC and generator gC:

  1. 1.

    ECDLP is hard in ⟨gC⟩: no classical PPT adversary finds x from [x]gC with non-negligible probability—concretely, every known attack costs at least 2126 operations (Proposition 2.27).

  2. 2.

    ECCDH and, where needed, ECDDH hold in ⟨gC⟩ (Definitions 2.4 and 2.5, transcribed additively).

  3. 3.

    The adversary is classical and probabilistic polynomial-time (Remark 2.31).

By the hierarchy of §2.3, assuming ECDDH is the strongest commitment and implies the rest; each later construction invokes, by name, the weakest assumption it requires.