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 and is published only as ; 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 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 is
cyclic if
Let
Fix a family of cyclic groups, where
The challenger runs the sampler, draws
The adversary outputs
The game outputs iff
The DLP assumption for the family states that for every PPT ,
The order is required to be prime because a composite order splits the problem across its factors (§2.5).
In a cyclic group
Let 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
and and share , 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
runs as follows: the challenger
draws
An adversary may be unable to compute 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 ,
with
A triple with
Rerandomisation applies to DDH as to DLP, by the following map. Given
a target triple
Writing
This subsection orders the three problems by reduction. Write
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 solves DLP. Given a CDH instance
, run on to recover
, 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 . Equivalently, the DDH assumption implies the CDH assumption.
Suppose solves CDH with probability .
Build a distinguisher : on input
, call to obtain
a candidate , and output iff
non-negligible whenever is, since is negligible.
For the amplified form let be noticeable. The
distinguisher rerandomises its input times
independently by the map of
Remark 2.6, runs with
fresh coins on each copy, and outputs iff some copy
answered . A DH input becomes independent uniform DH
triples, each accepted with probability , so
accepts with probability at least
Some elliptic-curve groups carry an efficiently computable,
non-degenerate bilinear pairing
which holds iff
The reverse reductions are not known in general. Whether an oracle computing yields 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 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 , any discrete logarithm can be computed in group operations and stored group elements, deterministically and unconditionally.
Let
and the target relation
The memory of BSGS, not its time, is the binding
constraint in practice: at the -bit security level no attacker
can store
In a cyclic group of prime order there is a randomised algorithm computing discrete logarithms in expected group operations and storage.
Sketch. Walk pseudo-randomly on , keeping with each
visited element its known representation .
Partition into three roughly equal sets
each step updating
and if
Pollard rho parallelises with near-linear speedup via the van
Oorschot–Wiener method of distinguished points: each of
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 wall-clock time with modest communication.
The security-relevant
measure is therefore the cost of the attack—the total
operation count , 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 be prime. Any generic algorithm that makes at most queries to the group oracle outputs the discrete logarithm of a uniformly random challenge with probability at most
In particular, constant success probability requires
Sketch—the linear-polynomial technique. In the idealisation,
the challenge logarithm is an indeterminate drawn uniformly from
. 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 group operations— bits of security against generic attacks—the prime group order must satisfy
For
The square-root barrier governs generic groups only; a concrete representation can expose structure that beats it. The multiplicative group is the standard example: index calculus exploits the factorisation of integers into small primes—smooth numbers—to solve DLP in sub-exponential time
far below . No analogue is known for the points of a
well-chosen elliptic curve over : there is no useful notion of
a “small” point over which to factor. This non-generic gap is why
elliptic-curve groups suffice at bits where
requires about 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 for prime ; 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
group operations. The term dominates, where is the largest prime dividing .
We compute
Reduction to prime-power order. Fix
Reduction to prime order, digit by digit. Write the unknown in base :
Let
because every higher digit contributes a multiple of to the
exponent and annihilates . Thus is a single
discrete logarithm in a group of prime order , solvable in
operations by BSGS or rho
(Propositions 2.11
and 2.13). Having , set
Suppose, contrary to good practice, a group has order
a product of small primes—it is smooth. Despite having
bits, the largest prime factor is only about ,
far below , 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 with
The “prime order” of Definition 2.2 makes Pohlig–Hellman vacuous (the only factor is 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 .
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 ”) that an elliptic
curve over , for
and that its set of -points,
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 and
For over (Math Guide, §“The group structure of ”),
where is the trace of Frobenius. The group order is thus
For -bit security the prime is chosen with about
bits, so that
A curve of prime order
(Size / generic.) The order satisfies
(Prime order.) The order is prime, so Pohlig–Hellman is vacuous and the cofactor is (Corollary 2.21).
(Anti-MOV / large embedding degree.) The multiplicative
order of modulo —the embedding
degree—is large. The MOV/Frey–Rück attack uses a pairing to
embed into and runs the
sub-exponential index calculus of
Remark 2.18 there; the attack is
effective only for small , as on supersingular curves—over
a prime field
(Anti-Smart / not anomalous.) The order avoids
(Twist security.) The quadratic twist —the
curve
The Pasta curves are a pair, Pallas and Vesta, in short Weierstrass form
(so
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 -bit prime slightly above , so
(2) Both orders are prime by construction: cofactor , 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
with a -bit prime and a -bit
prime. The best attack on the Pallas twist therefore costs about
The standard generic analysis therefore governs, and the security level is about 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 : the function
a line of slope . The algorithm prepares a uniform superposition
over , evaluates into a second register, and
applies the quantum Fourier transform—the reversible change of
basis into the characters of , 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 in about
quantum queries—a quadratic, not exponential, speedup—so a
cipher with a -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 -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 : no classical PPT adversary finds from with non-negligible probability—concretely, every known attack costs at least 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.