II Crypto Guide: Cryptographic primitives from scratch 1 The provable-security model 3 Hash functions and the random oracle model

2 Hardness assumptions

Every secret in this volume is an exponent. A spending key, the trapdoor of a commitment, the nonce of a signature—each lives in $\mathbb{Z}/q\mathbb{Z}$ and faces the world only through a group element $g^{x}$ . The adversary of this section is the patient cryptanalyst who collects those elements from the public record and asks for nothing more than the exponent behind one of them: an adversary who computes discrete logarithms recovers signing keys from verification keys, opens and re-opens commitments at will, and strips the blinding from every rerandomised key the later sections construct. What she can forge is everything; what she must be denied is a single inversion. This section assembles the family of assumptions that deny it: the discrete logarithm problem itself, the ladder of Diffie–Hellman variants above it, the generic-attack bounds that calibrate how hard the problem can possibly be, the composite-order failure mode that squanders that hardness, the elliptic curves on which the remainder of the volume instantiates the family, and the quantum caveat under which the whole edifice stands. Throughout, the lodestar is a single number: the security parameter $\lambda$ , read as the bit-length of security demanded. The recurring conclusion is that to obtain $\lambda$ bits of security against the best generic attacks the group must have prime order $q$ with $\log_{2}q\geq 2\lambda$ . Notation is fixed once: $G=\langle g\rangle$ 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

The stage is a finite cyclic group. Recall from the Math Guide (§“The discrete logarithm problem”) that a group $G$ is cyclic if $G=\langle g\rangle=\{\,g^{k}:k\in\mathbb{Z}\,\}$ for some generator $g$ ; written additively, as we shall write elliptic curves, this reads $G=\{\,kg:k\in\mathbb{Z}\,\}$ . If $\lvert G\rvert=q$ then $\mathbb{Z}/q\mathbb{Z}\cong G$ via $k\mapsto g^{k}$ , an isomorphism trivial to evaluate forwards—repeated squaring costs $O(\log k)$ group operations—but conjecturally infeasible to invert. That asymmetry is the discrete logarithm problem.

Definition 2.1 (Discrete logarithm).

Let $G=\langle g\rangle$ be a cyclic group of order $q$ , written multiplicatively. For $h\in G$ , the discrete logarithm of $h$ to the base $g$ , denoted $\log_{g}h$ , is the unique residue $x\in\mathbb{Z}/q\mathbb{Z}$ with $g^{x}=h$ . Existence follows from $G=\langle g\rangle$ and $\operatorname{ord}(g)=q$ ; uniqueness because $g^{x}=g^{x^{\prime}}$ forces $g^{x-x^{\prime}}=1$ , whence $q\mid x-x^{\prime}$ .

Definition 2.2 (Discrete logarithm problem, DLP).

Fix a family $\{G_{\lambda}\}$ of cyclic groups, where $G_{\lambda}=\langle g_{\lambda}\rangle$ has prime order $q_{\lambda}$ with $\log_{2}q_{\lambda}=\Theta(\lambda)$ , together with a sampler that on input $1^{\lambda}$ outputs a description of $(G_{\lambda},g_{\lambda},q_{\lambda})$ . The game $\mathsf{DLOG}^{\mathcal{A}}(\lambda)$ runs as follows.

1.

The challenger runs the sampler, draws $x\xleftarrow{\$}\mathbb{Z}/q_{\lambda}\mathbb{Z}$ uniformly, and sends $(G_{\lambda},g_{\lambda},q_{\lambda},\,h=g_{\lambda}^{\,x})$ to the adversary $\mathcal{A}$ .
2.

The adversary outputs $x^{\prime}\in\mathbb{Z}/q_{\lambda}\mathbb{Z}$ .
3.

The game outputs $1$ iff $g_{\lambda}^{\,x^{\prime}}=h$ .

The DLP assumption for the family states that for every PPT $\mathcal{A}$ ,

\Pr\bigl{[}\mathsf{DLOG}^{\mathcal{A}}(\lambda)=1\bigr{]}\;\in\;\operatorname{% negl}(\lambda).

The order is restricted to be prime for reasons that §2.5 makes emphatic: in prime order every non-identity element is a generator, there are no proper nontrivial subgroups through which information can leak, and the problem cannot be split across factors of the order. For now we record the convenience that prime order affords immediately.

Proposition 2.3 (Random self-reducibility of DLP).

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

Proof.

Let $\mathcal{A}$ succeed on a uniform target with probability $\varepsilon$ . Given a fixed challenge $h=g^{x}$ , draw $r\xleftarrow{\$}\mathbb{Z}/q\mathbb{Z}$ and form $h^{\prime}=h\cdot g^{r}=g^{x+r}$ . Addition modulo $q$ is a bijection and $r$ is uniform, so $h^{\prime}$ is uniform in $G$ and independent of $h$ ; hence $\mathcal{A}(h^{\prime})$ returns $x+r\bmod q$ with probability $\varepsilon$ , and subtracting $r$ recovers $x$ . Each candidate is checked by testing $g^{x}\stackrel{{\scriptstyle?}}{{=}}h$ , so failures are recognised. Fresh randomness $r$ per trial makes trials independent: $t$ of them succeed with probability $1-(1-\varepsilon)^{t}$ , overwhelming once $t=\omega(\varepsilon^{-1}\log\lambda)$ . □

Random self-reducibility is the formal licence to speak of “the” hardness of DLP in a group: an average-case solver also solves every fixed instance after rerandomisation. This does not literally make every instance difficult—the logarithm of the identity, for one, is immediate.

2.2 Diffie–Hellman: computational and decisional

The discrete logarithm problem asks to invert exponentiation. Many protocols—the Diffie–Hellman key exchange and ElGamal encryption are the historical motivations—need only a weaker-looking guarantee about the product of two exponents. Suppose Alice publishes $g^{a}$ and Bob publishes $g^{b}$ ; their shared secret is $g^{ab}$ , which each computes from the other’s public value and their own exponent. The eavesdropper sees $g,g^{a},g^{b}$ and wants $g^{ab}$ .

Definition 2.4 (Computational Diffie–Hellman, CDH).

With notation as in Definition 2.2, the game $\mathsf{CDH}^{\mathcal{A}}(\lambda)$ runs as follows: the challenger draws $a,b\xleftarrow{\$}\mathbb{Z}/q\mathbb{Z}$ independently and sends $(g,g^{a},g^{b})$ ; the adversary outputs $z\in G$ ; the game outputs $1$ iff $z=g^{ab}$ . The CDH assumption states that for every PPT $\mathcal{A}$ ,

\Pr_{a,b}\bigl{[}\mathsf{CDH}^{\mathcal{A}}(\lambda)=1\bigr{]}\;\in\;% \operatorname{negl}(\lambda).

The computational guarantee delivers the shared key but not its secrecy: an adversary may be unable to produce $g^{ab}$ yet perfectly able to distinguish it from a random group element, and that alone already breaks, say, the indistinguishability of an ElGamal ciphertext. The decisional variant excludes it.

Definition 2.5 (Decisional Diffie–Hellman, DDH).

The decisional Diffie–Hellman problem is to distinguish two distributions over $G^{3}$ ,

\mathcal{D}_{\mathrm{dh}}=\bigl{(}g^{a},g^{b},g^{ab}\bigr{)},\qquad\mathcal{D}% _{\mathrm{rand}}=\bigl{(}g^{a},g^{b},g^{c}\bigr{)},

with $a, b, c$ independent and uniform in $\mathbb{Z}/q\mathbb{Z}$ ; 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

\mathrm{Adv}_{\mathrm{ddh}}(D)=\Bigl{|}\Pr_{a,b}\bigl{[}D(g^{a},g^{b},g^{ab})=% 1\bigr{]}-\Pr_{a,b,c}\bigl{[}D(g^{a},g^{b},g^{c})=1\bigr{]}\Bigr{|}\;\in\;% \operatorname{negl}(\lambda).

A triple $(g^{a},g^{b},g^{c})$ with $c\equiv ab\pmod{q}$ is a Diffie–Hellman triple; the assumption says no efficient distinguisher recognises such triples.

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

Rerandomisation works for DDH as it did for DLP, though the correct map takes some care. Given a target triple $(u,v,w)=(g^{a},g^{b},g^{c})$ , choose $\alpha,\gamma\xleftarrow{\$}(\mathbb{Z}/q\mathbb{Z})^{\times}$ and $\beta,\delta\xleftarrow{\$}\mathbb{Z}/q\mathbb{Z}$ , and form

(u^{\prime},v^{\prime},w^{\prime})=\bigl{(}u^{\alpha}g^{\beta},\;v^{\gamma}g^{% \delta},\;w^{\alpha\gamma}\,u^{\alpha\delta}\,v^{\beta\gamma}\,g^{\beta\delta}% \bigr{)}.

Writing $A=\alpha a+\beta$ , $B=\gamma b+\delta$ , and $E=c-ab$ , the new exponents are $A$ , $B$ , and $AB+\alpha\gamma 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 $\alpha\gamma E$ is uniform in $(\mathbb{Z}/q\mathbb{Z})^{\times}$ . The latter distribution lies at statistical distance (Definition 1.6) $1/q$ from $\mathcal{D}_{\mathrm{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

The three problems form a chain. Write $A\leq B$ for “ $A$ reduces to $B$ ”: an oracle solving $B$ yields an efficient solver for $A$ ; equivalently, $B$ is at least as hard as $A$ , so that if $B$ is easy then $A$ is easy; equivalently again, the assumption “ $A$ is hard” is the stronger commitment, since it implies “ $B$ is hard”. The reductions of this subsection give

\mathrm{DDH}\;\leq\;\mathrm{CDH}\;\leq\;\mathrm{DLP},

ordering the problems by increasing hardness and the assumptions by decreasing strength: assuming DDH hard is the strongest commitment, 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 $\mathcal{A}$ solves DLP. Given a CDH instance $(g,g^{a},g^{b})$ , run $\mathcal{A}$ on $(g,g^{a})$ to recover $a$ , then compute $(g^{b})^{a}=g^{ab}$ by fast exponentiation. The cost is one DLP call plus $O(\log q)$ group operations, and only one of the two exponents ever needed inverting. □

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 $\mathcal{A}$ solves CDH with probability $\varepsilon$ . Build a distinguisher $D$ : on input $(g^{a},g^{b},z)$ , call $\mathcal{A}(g,g^{a},g^{b})$ to obtain a candidate $w$ , and output $1$ iff $w=z$ . On a Diffie–Hellman triple, $z=g^{ab}$ , so $D$ outputs $1$ whenever $\mathcal{A}$ succeeds—probability $\varepsilon$ . On a random triple, $z=g^{c}$ with $c$ uniform and independent of $a, b$ , while $w$ depends only on $(g^{a},g^{b})$ ; the event $w=z$ therefore has probability exactly $1/q$ . Hence

\mathrm{Adv}_{\mathrm{ddh}}(D)\;\geq\;\varepsilon-\frac{1}{q},

non-negligible whenever $\varepsilon$ is, since $1/q$ is negligible.

For the amplified form let $\varepsilon$ be noticeable. The distinguisher $D^{\prime}$ 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 $\varepsilon$ , so $D^{\prime}$ accepts with probability at least $1-(1-\varepsilon)^{t}$ . A sample of $\mathcal{D}_{\mathrm{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^{\prime}$ accepts with probability at most $1/q+t/(q-1)$ . With $t=\omega(\varepsilon^{-1}\log\lambda)$ , polynomial because $\varepsilon$ is noticeable, the advantage of $D^{\prime}$ is $1-\operatorname{negl}(\lambda)$ . □

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\colon G\times G\to G_{T}$ with $e(g^{a},g^{b})=e(g,g)^{ab}$ . On such a group DDH is easy: to test whether $(g^{a},g^{b},z)$ is a DH triple, check

e(g^{a},g^{b})\stackrel{{\scriptstyle?}}{{=}}e(g,z),

which holds iff $\log_{g}z\equiv ab\pmod{q}$ . Yet CDH—and a fortiori DLP—may remain hard, because the pairing reveals $g^{ab}$ only inside the target group $G_{T}$ , never as an element of $G$ . Such groups, called gap groups, separate DDH from CDH and found pairing-based cryptography. The moral is that DDH is a genuinely stronger assumption: choosing a “DDH group” means choosing a group that rules out pairings of this convenient kind on $G$ itself.

Remark 2.10 (The converses are open).

The reverse reductions are not known in general. Whether CDH implies DLP—whether the ability to compute $g^{ab}$ can be leveraged to extract $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. Practice therefore assumes exactly the strength a protocol 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

How hard can the discrete logarithm problem possibly be? 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 $\sigma\colon\mathbb{Z}/q\mathbb{Z}\to S$ encodes the element $g^{k}$ as the opaque string $\sigma(k)$ , and the algorithm may only ask an oracle for $\sigma(i+j)$ given $\sigma(i)$ and $\sigma(j)$ , and compare labels for equality. Two generic algorithms achieve $O(\sqrt{q})$ group operations; a matching lower bound then shows that, generically, nothing does better.

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(\sqrt{q})$ group operations and $O(\sqrt{q})$ stored group elements, deterministically and unconditionally.

Proof.

Let $m=\lceil\sqrt{q}\rceil$ . Since $m^{2}\geq q$ , every $x\in\{0,\dots,q-1\}$ decomposes as

x=i\cdot m+j,\qquad 0\leq i<m,\quad 0\leq j<m,

and the target relation $g^{x}=h$ becomes $g^{j}=h\cdot(g^{-m})^{i}$ . Baby steps: compute and store the table $\{(j,g^{j}):0\leq 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(\log q)$ operations) and for $i=0,1,2,\dots$ compute $h\cdot u^{i}$ 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(\sqrt{q})$ operations and $O(\sqrt{q})$ memory. □

Remark 2.12 (Memory is the bottleneck).

The $O(\sqrt{q})$ memory of BSGS, not its time, is what bites in practice: at the $128$ -bit security level no attacker can store $\sqrt{q}\approx 2^{128}$ 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(\sqrt{q})$ group operations and $O(1)$ storage.

Proof.

Sketch. Walk pseudo-randomly on $G$ , keeping with each visited element its known representation $g^{\alpha}h^{\beta}$ . Partition $G$ into three roughly equal sets $S_{1},S_{2},S_{3}$ by an easily computed function of the element’s label, and from $P=g^{\alpha}h^{\beta}$ step to

f(P)=\begin{cases}h\cdot P=g^{\alpha}h^{\beta+1},&P\in S_{1},\\[2.0pt] P^{2}=g^{2\alpha}h^{2\beta},&P\in S_{2},\\[2.0pt] g\cdot P=g^{\alpha+1}h^{\beta},&P\in S_{3},\end{cases}

each step updating $(\alpha,\beta)\in(\mathbb{Z}/q\mathbb{Z})^{2}$ explicitly at $O(1)$ cost. The sequence eventually cycles—a tail leading into a loop, the shape of the letter $\rho$ . Modelling $f$ as a random function on $q$ elements, the birthday bound (Math Guide, §“The union bound and a birthday calculation”) produces a collision $P_{i}=P_{j}$ , $i\neq j$ , within $O(\sqrt{q})$ steps in expectation. A collision gives $g^{\alpha_{i}}h^{\beta_{i}}=g^{\alpha_{j}}h^{\beta_{j}}$ , hence $g^{\alpha_{i}-\alpha_{j}}=h^{\beta_{j}-\beta_{i}}$ ; writing $h=g^{x}$ ,

\alpha_{i}-\alpha_{j}\equiv x\,(\beta_{j}-\beta_{i})\pmod{q},

and if $\beta_{j}\not\equiv\beta_{i}$ the difference is invertible modulo the prime $q$ , so $x\equiv(\alpha_{i}-\alpha_{j})(\beta_{j}-\beta_{i})^{-1}\pmod{q}$ . 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 $\beta_{j}\equiv\beta_{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 almost perfectly 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 $\sqrt{q}/P$ wall-clock time with modest communication. The security-relevant measure is therefore the cost of the attack—the total operation count $\sqrt{q}$ , read as the attacker’s budget—not the time on any single machine. A further constant-factor saving applies in groups admitting the $\pm$ automorphism $P\mapsto-P$ , as elliptic curves do: identifying $P$ with $-P$ halves the effective search space and lowers the expected count from $\sqrt{\pi q/2}$ to $\sqrt{\pi q/4}$ , a factor $\sqrt{2}$ that leaves the $\Theta(\sqrt{q})$ scaling untouched. The constant is the birthday integral: a random walk on $N$ points is still collision-free after $k$ steps with probability $\prod_{i<k}(1-i/N)\approx e^{-k^{2}/2N}$ (the product in the birthday calculation cited above), and summing over $k$ gives an expected first-collision index of $\int_{0}^{\infty}e^{-k^{2}/2N}\,dk=\sqrt{\pi N/2}$ .

The generic lower bound

The two attacks are not merely the best known; up to constants they are the best possible for any generic algorithm. This is Shoup’s theorem, the formal statement of the square-root barrier.

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

\frac{\binom{n+2}{2}+1}{q}\;=\;O\!\left(\frac{n^{2}}{q}\right).

In particular, constant success probability requires $n=\Omega(\sqrt{q})$ queries.

Proof.

Sketch—the linear-polynomial technique. In the idealisation, the challenge logarithm is an indeterminate $X$ drawn uniformly from $\mathbb{Z}/q\mathbb{Z}$ . By induction on the queries, every element the algorithm forms is $\sigma$ of a known linear polynomial $a_{i}+b_{i}X\bmod q$ 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 and can only guess, succeeding with probability $1/q$ . Information leaks only through an accidental collision: two distinct polynomials agreeing at the secret $x$ , that is, $(a_{i}-a_{j})+(b_{i}-b_{j})\,x\equiv 0\pmod{q}$ . 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 $\binom{n+2}{2}$ pairs, and the union bound (Math Guide, §“The union bound and a birthday calculation”) caps the collision probability at $\binom{n+2}{2}/q$ . Adding the $1/q$ guess yields the bound; solving $n^{2}/q=\Omega(1)$ gives $n=\Omega(\sqrt{q})$ . □

Corollary 2.16 (Why $\log_{2}q\geq 2\lambda$ ).

To force every generic attacker to spend at least $2^{\lambda}$ group operations— $\lambda$ bits of security against generic attacks—the prime group order must satisfy

\sqrt{q}\;\gtrsim\;2^{\lambda}\qquad\Longleftrightarrow\qquad\log_{2}q\;\geq\;% 2\lambda.

Proof.

Propositions 2.11 and 2.13 show that $\Theta(\sqrt{q})$ operations suffice for a generic attacker, and Theorem 2.15 shows no generic attacker does asymptotically better. Equating the attacker’s cost $\sqrt{q}$ with the target work factor $2^{\lambda}$ gives $q\approx 2^{2\lambda}$ ; demanding at least this much is $\log_{2}q\geq 2\lambda$ . □

Example 2.17 (The $128$ -bit target).

For $\lambda=128$ the corollary demands a prime group order with $\log_{2}q\geq 256$ . This explains the standardised $256$ -bit elliptic curves: NIST P-256 (secp256r1) has a $256$ -bit field and a $256$ -bit group order, so $\sqrt{q}\approx 2^{128.0}$ . The Pasta curves of §2.6, with $255$ -bit orders just above $2^{254}$ and about $126$ bits of security, sit just below this class. Contrast the multiplicative group $\mathbb{F}_{p}^{\times}$ : there the sub-exponential index calculus of Remark 2.18 forces $\log_{2}p$ into the thousands of bits for the same $\lambda$ . Elliptic curves earn their keep precisely because no sub-exponential, generic-beating algorithm 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 leak structure that beats it. The multiplicative group $\mathbb{F}_{p}^{\times}$ is the cautionary case: index calculus exploits the factorisation of integers into small primes—smooth numbers—to solve DLP in sub-exponential time

\exp\!\bigl{(}O\bigl{(}(\log p)^{1/3}(\log\log p)^{2/3}\bigr{)}\bigr{)},

far below $\sqrt{p}$ . No analogue is known for the points of a well-chosen elliptic curve over $\mathbb{F}_{p}$ : there is no useful notion of a “small” point over which to factor. This non-generic gap is why elliptic-curve groups can live at $256$ bits where $\mathbb{F}_{p}^{\times}$ must reach about $3072$ bits for the same security. It also means the rule $\log_{2}q\geq 2\lambda$ 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

The square-root barrier priced the attack at $\sqrt{q}$ for prime $q$ . If the group order factors, the discrete logarithm splits into independent pieces the size of the factors, and the difficulty collapses to that of the largest prime dividing the order. This is the Pohlig–Hellman reduction—the reason Definition 2.2 insisted on prime order.

Theorem 2.19 (Pohlig–Hellman).

Let $G=\langle g\rangle$ have order $N=\prod_{i=1}^{r}p_{i}^{e_{i}}$ with the $p_{i}$ distinct primes. Then a discrete logarithm in $G$ can be computed in

O\!\left(\sum_{i=1}^{r}e_{i}\bigl{(}\log N+\sqrt{p_{i}}\,\bigr{)}\right)

group operations. The term $\sqrt{p_{\max}}$ dominates, where $p_{\max}$ is the largest prime dividing $N$ .

Proof.

We compute $x=\log_{g}h$ modulo each prime power $p_{i}^{e_{i}}$ and recombine by the Chinese Remainder Theorem, the moduli being pairwise coprime with product $N$ .

Reduction to prime-power order. Fix $p=p_{i}$ , $e=e_{i}$ , and put $g_{i}=g^{N/p^{e}}$ , $h_{i}=h^{N/p^{e}}$ . Then $g_{i}$ has order exactly $p^{e}$ , and $\log_{g_{i}}h_{i}\equiv x\pmod{p^{e}}$ : raising to $N/p^{e}$ kills the part of $x$ coprime to $p$ ’s power and leaves $x\bmod p^{e}$ . It therefore suffices to solve DLP in $\langle g_{i}\rangle$ of order $p^{e}$ .

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

x\equiv x_{0}+x_{1}p+\dots+x_{e-1}p^{\,e-1}\pmod{p^{e}},\qquad 0\leq x_{k}<p.

Let $\gamma=g_{i}^{\,p^{e-1}}$ , an element of order exactly $p$ . Raising $h_{i}$ to the power $p^{e-1}$ gives

h_{i}^{\,p^{e-1}}=g_{i}^{\,xp^{e-1}}=\gamma^{\,x_{0}},

because every higher digit contributes a multiple of $p^{e}$ to the exponent and annihilates $\gamma$ . Thus $x_{0}$ is a single discrete logarithm in a group of prime order $p$ , solvable in $O(\sqrt{p})$ operations by BSGS or rho (Propositions 2.11 and 2.13). Having $x_{0}$ , set $h_{i}^{(1)}=h_{i}\cdot g_{i}^{-x_{0}}$ ; its logarithm is divisible by $p$ , and the same step at exponent $p^{e-2}$ yields $x_{1}$ . Iterating recovers all $e$ digits with $e$ prime-order DLPs of cost $O(\sqrt{p})$ each, plus $O(e\log N)$ 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=2^{256}-1$ . The order factors completely into

	$\displaystyle 2^{256}-1={}$	$\displaystyle 3\cdot 5\cdot 17\cdot 257\cdot 641\cdot 65537\cdot 274177\cdot 6% 700417\cdot 67280421310721$
		$\displaystyle\cdot 59649589127497217\cdot 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 $\sqrt{p_{\max}}\approx 2^{36.1}$ operations—about $2^{36}$ , nowhere near the apparent $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 $\lambda$ , the group order must be divisible by a prime $q$ with $\log_{2}q\geq 2\lambda$ , and the cryptographic group must be, or be restricted to, the subgroup of order $q$ . When the ambient group has order $N=h\cdot 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 $x\bmod h$ via Pohlig–Hellman on the order- $h$ part.

Remark 2.22 (Prime order, revisited).

Here is the deeper justification for “prime order” in Definition 2.2. Prime order $q$ makes Pohlig–Hellman vacuous (the only factor is $q$ itself), makes every non-identity element a generator (no element lands in a weak proper subgroup), and removes cofactor bookkeeping entirely. The Pasta curves below are engineered to have prime order: each group is its own prime-order subgroup, with cofactor $1$ .

2.6 Instantiation on elliptic curves; the Pasta curves

We now fix the concrete groups the remainder of the volume uses. Recall from the Math Guide (§“Elliptic curves”, with the group law in §“The group structure of $E(\mathbb{F}_{p})$ ”) that an elliptic curve over $\mathbb{F}_{p}$ , for $p>3$ prime, in short Weierstrass form is

E\colon y^{2}=x^{3}+ax+b,\qquad a,b\in\mathbb{F}_{p},\quad 4a^{3}+27b^{2}\neq 0,

and that its set of $\mathbb{F}_{p}$ -points,

E(\mathbb{F}_{p})=\bigl{\{}(x,y)\in\mathbb{F}_{p}^{2}:y^{2}=x^{3}+ax+b\bigr{\}% }\cup\{\mathcal{O}\},

equipped with chord-and-tangent addition and the point at infinity $\mathcal{O}$ 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 in its own habitat 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\mapsto[x]P$ , giving ECCDH and ECDDH. The group size is pinned down by the Hasse bound, likewise recalled.

Theorem 2.23 (Hasse bound, recalled).

For $E$ over $\mathbb{F}_{p}$ (Math Guide, §“The group structure of $E(\mathbb{F}_{p})$ ”),

\bigl{|}\#E(\mathbb{F}_{p})-(p+1)\bigr{|}\;\leq\;2\sqrt{p},\qquad\text{i.e.}% \qquad\#E(\mathbb{F}_{p})=p+1-t,\quad\lvert t\rvert\leq 2\sqrt{p},

where $t$ is the trace of Frobenius. The group order is thus $p+1$ up to a deviation of order $\sqrt{p}$ .

The parameter recipe for $\lambda$ -bit security follows: choose $p$ of about $2\lambda$ bits, so that $\#E(\mathbb{F}_{p})\approx p\approx 2^{2\lambda}$ , and insist by Corollary 2.21 that $\#E(\mathbb{F}_{p})$ be prime—cofactor $1$ . One then assumes ECDLP, ECCDH, and ECDDH at the level Corollary 2.16 predicts, provided the curve avoids the known structural attacks that beat the generic bound. The screening criteria are as follows.

Definition 2.24 (Secure-curve criteria).

A curve $E/\mathbb{F}_{p}$ of prime order $q=\#E(\mathbb{F}_{p})$ is admissible for $\lambda$ -bit DLP security if:

1.

(Size / generic.) The order satisfies $\log_{2}q\geq 2\lambda$ , so Pollard rho costs at least $2^{\lambda}$ operations (Corollary 2.16).
2.

(Prime order.) The order $q$ is prime, so Pohlig–Hellman is vacuous and the cofactor is $1$ (Corollary 2.21).
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(\mathbb{F}_{p})$ into $\mathbb{F}_{p^{k}}^{\times}$ and runs the sub-exponential index calculus of Remark 2.18 there; the threat is real only for small $k$ , as on supersingular curves—over a prime field $p>3$ , those with trace $t=0$ , so that $\#E(\mathbb{F}_{p})=p+1$ divides $p^{2}-1$ and $k\leq 2$ . A curve with $t\neq 0$ is ordinary.
4.

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

(Twist security.) The quadratic twist $E^{\prime}$ —the curve $dy^{2}=x^{3}+ax+b$ for a fixed nonsquare $d\in\mathbb{F}_{p}$ ; every $x\in\mathbb{F}_{p}$ is the $x$ -coordinate of a point of $E$ or of $E^{\prime}$ —should also have large prime order, so that computation cannot be pushed onto a weak twist by a fault or an invalid-point injection.

Definition 2.25 (The Pasta curves).

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

y^{2}=x^{3}+5

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

\#\mathrm{Pallas}=q\ \ (\text{Pallas defined over }\mathbb{F}_{p}),\qquad\#% \mathrm{Vesta}=p\ \ (\text{Vesta defined over }\mathbb{F}_{q}).

The order of each curve equals the field of definition of the other. Both primes are congruent to $1\bmod 2^{32}$ , 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 (Why a cycle, and what it buys).

The defining property— $\#\mathrm{Pallas}=q$ , the base field of Vesta, and $\#\mathrm{Vesta}=p$ , the base field of Pallas—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 $\lambda\approx 126$ . Criterion (5) fails for both curves—neither twist has prime order, and the Pallas twist falls below the SafeCurves $2^{100}$ twist-attack cost threshold—but the failure is rendered moot by mandatory point validation.

Proof.

Sketch, criterion by criterion.

(1) Each order is a $255$ -bit prime just above $2^{254}$ , so $\log_{2}q\approx 254.0$ and the bare generic cost is $\sqrt{q}\approx 2^{127.0}$ . Plain Pollard rho expects about $\sqrt{\pi q/2}\approx 2^{127.3}$ operations; the $\pm$ automorphism speedup of Remark 2.14 lowers this to $\sqrt{\pi q/4}\approx 2^{126.8}$ ; and the order- $6$ automorphism group of these $j$ -invariant- $0$ curves—the factor $\sqrt{m}$ for an order- $m$ automorphism group of Remark 2.28, here an extra $\sqrt{3}$ —lowers it to $\sqrt{\pi q/12}\approx 2^{126.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\neq 0$ . The embedding degree $k$ of each is enormous. For Pallas, $q-1=2^{32}\cdot 3^{2}\cdot 1709\cdot 24859\cdot C$ with $C$ a $194$ -bit composite, and $p^{(q-1)/32}\not\equiv 1$ and $p^{(q-1)/\ell}\not\equiv 1\pmod{q}$ for $\ell\in\{3,1709,24859\}$ , so the order $k$ of $p$ modulo $q$ is a multiple of $2^{28}\cdot 3^{2}\cdot 1709\cdot 24859>2^{56}$ ; for Vesta, $p-1=2^{32}\cdot 3\cdot 463\cdot C^{\prime}$ , and $q^{(p-1)/4}\not\equiv 1$ , $q^{(p-1)/\ell}\not\equiv 1\pmod{p}$ for $\ell\in\{3,463\}$ make $k$ a multiple of $2^{31}\cdot 3\cdot 463>2^{41}$ . Either extension field is astronomically beyond any feasible index-calculus target; MOV/Frey–Rück does not apply.

(4) Neither curve is anomalous: $\#\mathrm{Pallas}=q\neq p$ and $\#\mathrm{Vesta}=p\neq q$ , so the trace $t=p+1-q\neq 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\in\mathbb{F}_{p}$ supplies two affine points in total, on $E$ or on $E^{\prime}$ (one on each when $x^{3}+b=0$ ), so $\#E+\#E^{\prime}=2(p+1)$ and $\#E^{\prime}=2(p+1)-\#E=p+1+t$ ; hence $\#\mathrm{Pallas}^{\prime}=2(p+1)-q$ and $\#\mathrm{Vesta}^{\prime}=2(q+1)-p$ , which factor as

	$\displaystyle\#\mathrm{Pallas}^{\prime}$	$\displaystyle=3^{2}\cdot 7\cdot 8191\cdot 85021\cdot 11540602760389\cdot P_{17% 6},$
	$\displaystyle\#\mathrm{Vesta}^{\prime}$	$\displaystyle=3^{3}\cdot 7\cdot 13\cdot 2851\cdot 30097\cdot 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 $\sqrt{P_{176}}\approx 2^{87.6}$ , below the SafeCurves $2^{100}$ twist-security threshold; the Vesta twist clears the threshold at about $2^{108.2}$ . The failure is moot in our 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 arithmetic does neither. The pasta_curves crate carries points in full coordinates and has no $x$ -only code path; its deserialisation (from_bytes) reconstructs $y$ by taking the square root of $x^{3}+5$ , failing exactly when $x$ lies on the twist, where $x^{3}+5$ is a non-square, and even from_bytes_unchecked delegates to the checked path because a compressed encoding cannot skip the curve check, while points built from raw coordinates are gated on is_on_curve. This is the behaviour protocol specification § 5.4.9.6 mandates: its decoding map returns $\bot$ (failure) when $x^{3}+b$ has no square root, and an implementation must not assume that the root exists or that the encoding lies on the curve. Orchard deserialises its points through this routine, 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 governs, and the security level is about $126$ bits. □

Remark 2.28 ( $j$ -invariant $0$ and endomorphisms).

The shape $y^{2}=x^{3}+b$ gives $j$ -invariant $0$ , and with it an extra automorphism of order $3$ (Math Guide, §“The $j$ -invariant and the GLV endomorphism”): for $\omega$ a primitive cube root of unity in $\mathbb{F}_{p}$ , the cheap endomorphism $\phi(x,y)=(\omega x,y)$ acts on the group as multiplication by a fixed scalar $\zeta$ with $\zeta^{2}+\zeta+1\equiv 0\pmod{q}$ (the $\lambda$ of the Math Guide’s proposition), enabling the GLV speedup for honest scalar multiplication. The same endomorphism hands the attacker a slightly larger automorphism group, and with it the constant-factor Pollard-rho speedup used in Proposition 2.27—a factor $\sqrt{m}$ for an order- $m$ automorphism group—but that is a small constant and does not change the $\Theta(\sqrt{q})$ scaling. Beyond that constant, the extra automorphism is not known to weaken ECDLP; the danger lies only in small embedding degree and in anomalousness, both excluded above.

2.7 The quantum caveat: Shor’s algorithm

Every assumption above holds the adversary to classical PPT computation. Against a large fault-tolerant quantum computer the picture changes qualitatively, and honesty requires stating exactly what breaks and what survives.

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

There is a quantum algorithm that, given a cyclic group $G=\langle g\rangle$ of order $q$ with efficient group operations and a target $h=g^{x}$ , outputs $x$ in time polynomial in $\log q$ , succeeding with overwhelming probability. Consequently DLP—and with it CDH and DDH—falls in quantum polynomial time in any group, elliptic-curve groups included.

We do not prove the theorem; the shape of the algorithm is nevertheless worth recording. Discrete logarithm is an instance of the hidden subgroup problem over $(\mathbb{Z}/q\mathbb{Z})^{2}$ . The function $f(\alpha,\beta)=g^{\alpha}h^{-\beta}=g^{\alpha-x\beta}$ is constant exactly on the cosets of

H=\bigl{\{}(\alpha,\beta):\alpha\equiv x\beta\pmod{q}\bigr{\}}=\langle(x,1)% \rangle\subseteq(\mathbb{Z}/q\mathbb{Z})^{2},

a line of slope $x$ . The algorithm prepares a uniform superposition over $(\mathbb{Z}/q\mathbb{Z})^{2}$ , evaluates $f$ into a second register, and applies the quantum Fourier transform—the reversible change of basis into the characters of $(\mathbb{Z}/q\mathbb{Z})^{2}$ , the homomorphisms $\chi_{u,v}(\alpha,\beta)=e^{2\pi i(u\alpha+v\beta)/q}$ into the unit circle; measurement then samples characters trivial on $H$ , i.e. pairs $(u,v)$ with $ux+v\equiv 0\pmod{q}$ , and a handful of samples reveal the slope $x$ by classical linear algebra modulo $q$ . The whole procedure uses $O(\operatorname{poly}(\log q))$ qubits and gates, and it touches the group only through the black-box map $(\alpha,\beta)\mapsto g^{\alpha}h^{-\beta}$ , so it is agnostic to representation: elliptic-curve DLP falls exactly as $\mathbb{F}_{p}^{\times}$ 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. The two results coexist: the barrier bounds classical generic attackers; Shor is a quantum, non-generic attacker.

Remark 2.31 (What Shor breaks and what survives).

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. What it does not break:

•

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\lambda$ -bit key, or an $n=2\lambda$ -bit hash against preimages, retains $\lambda$ bits of quantum security. Generic quantum collision finding instead costs $\Theta(2^{n/3})$ queries, so in the query metric an output of about $3\lambda$ bits is needed for $\lambda$ -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 deliver the approximately $126$ -bit security of Proposition 2.27—the ground on which the Halo 2 constructions to come are built.

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\in\{\mathrm{Pallas},\mathrm{Vesta}\}$ with prime order $q_{C}$ and generator $g_{C}$ :

1.

ECDLP is hard in $\langle g_{C}\rangle$ : 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).
2.

ECCDH and, where needed, ECDDH hold in $\langle g_{C}\rangle$ (Definitions 2.4 and 2.5, transcribed additively).
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.