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 Z / q Z and is published only as g x ; 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
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
Let
Fix a family { G λ } of cyclic groups, where
The challenger runs the sampler, draws
The adversary outputs
The game outputs 1 iff
The DLP assumption for the family states that for every PPT A ,
| Pr [DLOG A (λ) = 1] ∈ negl (λ) . |
The order is required to be prime because a composite order splits the problem across its factors (§2.5).
In a cyclic group
Let A succeed on a uniform target with probability
ε . Given a fixed challenge
Random self-reducibility does not make every instance hard: the logarithm of the identity is immediate.
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
g a and g b and share g a b , which each computes from
the other’s public value and its own exponent; an eavesdropper observes
With notation as in Definition 2.2, the game
CDH A (λ) runs as follows: the challenger
draws
| Pr a, b [CDH A (λ) = 1] ∈ negl (λ) . |
An adversary may be unable to compute g a 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.
The decisional Diffie–Hellman problem is to distinguish two distributions over G 3 ,
| D dh = (g a, g b, g a b), D rand = (g a, g b, g c), |
with
| Adv ddh (D) = | Pr a, b [D (g a, g b, g a b) = 1] − Pr a, b, c [D (g a, g b, g c) = 1] | ∈ negl (λ) . |
A triple (g a, g b, g c) with
Rerandomisation applies to DDH as to DLP, by the following map. Given
a target triple
| (u ′, v ′, w ′) = (u α g β, v γ g δ, w α γ u α δ v β γ g β δ) . |
Writing
This subsection orders the three problems by reduction. Write
| DDH ≤ CDH ≤ DLP, |
so assuming DDH hard is the strongest commitment and assuming DLP hard the weakest.
If DLP is solvable in PPT, then CDH is solvable in PPT. Equivalently, the CDH assumption implies the DLP assumption.
Suppose A solves DLP. Given a CDH instance
(g, g a, g b) , run A on (g, g a) to recover
a , then compute
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.
Suppose A solves CDH with probability ε .
Build a distinguisher D : on input
(g a, g b, z) , call A (g, g a, g b) to obtain
a candidate w , and output 1 iff
| Adv ddh (D) ≥ ε − 1 q, |
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
Some elliptic-curve groups carry an efficiently computable,
non-degenerate bilinear pairing
| e (g a, g b) = ? e (g, z), |
which holds iff
The reverse reductions are not known in general. Whether an oracle computing g a 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.
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
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.
Let
| x = i ⋅ m + j, 0 ≤ i < m, 0 ≤ j < m, |
and the target relation
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
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.
Sketch. Walk pseudo-randomly on G , keeping with each
visited element its known representation g α h β .
Partition G into three roughly equal sets
| f (P) = { h ⋅ P = g α h β + 1, P ∈ S 1, P 2 = g 2 α h 2 β, P ∈ S 2, g ⋅ P = g α + 1 h β, P ∈ S 3, |
each step updating
| α i − α j ≡ x (β j − β i) (mod q), |
and if
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
Shoup’s lower bound, the square-root barrier, shows that up to constant factors the two attacks are the best possible generic algorithms.
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 + 2 2) + 1 q = O (n 2 q) . |
In particular, constant success probability requires
Sketch—the linear-polynomial technique. In the idealisation,
the challenge logarithm is an indeterminate X drawn uniformly from
Z / q Z . By induction on the queries, every element the algorithm
forms is σ of a known linear polynomial
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 λ ⟺ log 2 q ≥ 2 λ . |
For
The square-root barrier governs generic groups only; a concrete representation can expose structure that beats it. The multiplicative group F 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 F 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 F p ×
requires about 3072 bits for the same security. It also means
the rule
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.
Let
| O (∑ i = 1 r e i (log N + p i)) |
group operations. The term p max dominates, where p max is the largest prime dividing N .
We compute
Reduction to prime-power order. Fix
Reduction to prime order, digit by digit. Write the unknown in base p :
| x ≡ x 0 + x 1 p + ⋯ + x e − 1 p e − 1 (mod p e), 0 ≤ x k < p . |
Let
| h i p e − 1 = g i x p e − 1 = γ x 0, |
because every higher digit contributes a multiple of p e to the
exponent and annihilates γ . Thus x 0 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 x 0 , set
Suppose, contrary to good practice, a group has order
| 2 256 − 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 2 72.3 ,
far below 2 128 , so Pohlig–Hellman with rho in the largest
subgroup solves DLP in roughly
For DLP-based security at level λ , the group order must be
divisible by a prime q with
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 .
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 (F p) ”) that an elliptic
curve over F p , for
| E : y 2 = x 3 + a x + b, a, b ∈ F p, 4 a 3 + 27 b 2 ≠ 0, |
and that its set of F p -points,
| E (F p) = { (x, y) ∈ F p 2 : y 2 = x 3 + a x + b } ∪ { O }, |
equipped with chord-and-tangent addition and the point at infinity
O as identity, forms a finite abelian group. The discrete
logarithm problem in this group—given P and
For E over F p (Math Guide, §“The group structure of E (F p) ”),
| | # E (F p) − (p + 1) | ≤ 2 p, i.e. # E (F p) = p + 1 − t, | t | ≤ 2 p, |
where t is the trace of Frobenius. The group order is thus
For λ -bit security the prime p is chosen with about
2 λ bits, so that
A curve E / F p of prime order
(Size / generic.) The order satisfies
(Prime order.) The order q is prime, so Pohlig–Hellman is vacuous and the cofactor is 1 (Corollary 2.21).
(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 (F p) into F p k × 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
(Anti-Smart / not anomalous.) The order avoids
(Twist security.) The quadratic twist E ′ —the
curve
The Pasta curves are a pair, Pallas and Vesta, in short Weierstrass form
| y 2 = x 3 + 5 |
(so
| # Pallas = q (Pallas defined over F p), # Vesta = p (Vesta defined over F q) . |
The order of each curve equals the field of definition of the other.
Both primes are congruent to
The cycle property
The curves Pallas and Vesta satisfy criteria (1)–(4) of
Definition 2.24 at
Sketch, criterion by criterion.
(1) Each order is a 255 -bit prime slightly above 2 254 , so
(2) Both orders are prime by construction: cofactor 1 , Pohlig–Hellman vacuous.
(3) Both curves are ordinary: the trace
(4) Neither curve is anomalous:
(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
| # Pallas ′ | = 3 2 ⋅ 7 ⋅ 8191 ⋅ 85021 ⋅ 11540602760389 ⋅ P 176, | ||
| # Vesta ′ | = 3 3 ⋅ 7 ⋅ 13 ⋅ 2851 ⋅ 30097 ⋅ P 217, |
with P 176 a 176 -bit prime and P 217 a 217 -bit
prime. The best attack on the Pallas twist therefore costs about
The standard generic analysis therefore governs, and the security level is about 126 bits. □
The shape
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.
There is a quantum algorithm that, given a cyclic group
Discrete logarithm is an instance of the hidden subgroup problem
over (Z / q Z) 2 : the function
| H = { (α, β) : α ≡ x β (mod q) } = ⟨ (x, 1) ⟩ ⊆ (Z / q Z) 2, |
a line of slope x . The algorithm prepares a uniform superposition
over (Z / q Z) 2 , evaluates f into a second register, and
applies the quantum Fourier transform—the reversible change of
basis into the characters of (Z / q Z) 2 , the homomorphisms
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.
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 2 n in about 2 n / 2
quantum queries—a quadratic, not exponential, speedup—so a
cipher with a 2 λ -bit key, or an
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.
We collect the premises the rest of the volume relies on. For each
Pasta curve
ECDLP is hard in ⟨ g C ⟩ : no classical PPT adversary finds x from [x] g C with non-negligible probability—concretely, every known attack costs at least 2 126 operations (Proposition 2.27).
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.