Proofs: Weil descent attack

Correctness of the Weil descent attack full

This proof shows: correctness, termination.

Let $K = \mathbb{F}_{q^2}$ with Frobenius $\sigma$, let $E : y^2 = g(x)(x - \beta)$ be as on the page, $T_2 = (\beta, 0)$, and let $C_0 : Y^2 = H(u)$ with $H = -(T - 2u)G(u)$. The code checks that $H$ is squarefree of degree $5$, so $C_0$ is a smooth curve of genus $2$ with one point $\infty$ at infinity. $J$ is its Jacobian, and we use the standard facts on Mumford representation (Cantor, Mumford): every class of degree $0$ is $[D - (\deg D)\infty]$ for a unique reduced divisor $D$, and semi-reduced divisors $D$ correspond to pairs $[U, V]$ with $U$ monic, $\deg V < \deg U$ and $U \mid H - V^2$, where $D$ is the divisor of the ideal $(U(u), Y - V(u))$. Cantor's algorithm computes the sum of classes in this form. Since $C_0$ is defined over $\mathbb{F}_q$, $\sigma$ acts on classes over $K$ by acting on the coefficients of $U$ and $V$, and a class fixed by $\sigma$ has a reduced pair with coefficients in $\mathbb{F}_q$, by uniqueness. For termination we treat the draws of line L15 as independent and uniform.

Lemma 1 (the frame). For each prime power $r^e \,\|\, n$ put $u_r = n / r^e$, $P_r = u_r P$ and $Q_r = u_r Q$. If $nQ = O$, then $Q \in \langle P \rangle$ if and only if $Q_r \in \langle P_r \rangle$ for every $r$. In that case, if $x_r P_r = Q_r$ for every $r$, the $x$ of line L9 satisfies $xP = Q$, and it is the only such $x$ in $[0, n)$.

Proof. The $u_r$ have greatest common divisor $1$, so there are integers $w_r$ with $\sum_r w_r u_r = 1$. If $Q = yP$, then $Q_r = y P_r$. Conversely, if $Q_r = x_r P_r$ for every $r$, then $Q = \sum_r w_r u_r Q = \sum_r w_r Q_r$. For $x \equiv x_r \pmod{r^e}$, $x P_r = x_r P_r$ because $P_r$ has order $r^e$, so $xP = \sum_r w_r x P_r = \sum_r w_r Q_r = Q$. Uniqueness in $[0, n)$ holds since $P$ has order $n$. $\square$

Lemma 2 (the cover). The map $\varphi(u, Y) = \big((N_\beta - u^2)/(T - 2u),\ Y(u - \beta)/(T - 2u)^2\big)$ sends $C_0$ to $E$. It has degree $2$, $\varphi^*(O) = W + \infty$ with $W = (T/2, 0)$, and $\varphi^*(T_2) = B + \iota B$ with $B = (\beta, Y_B)$ and $\iota$ the hyperelliptic involution.

Proof. Put $x(u) = (N_\beta - u^2)/(T - 2u)$. Since $T = \beta + \beta^q$ and $N_\beta = \beta \beta^q$, we have $\beta T - N_\beta = \beta^2$, so $x(u) - \beta = -(u - \beta)^2/(T - 2u)$. Also $(T - 2u)^2 g(x(u)) = G(u)$ by expanding. Hence $g(x)(x - \beta) = -G(u)(u - \beta)^2/(T - 2u)^3 = H(u)(u - \beta)^2/(T - 2u)^4$, which is the square of the second coordinate when $Y^2 = H(u)$. The function $x \circ \varphi$ has degree $2$ in $u$, which has degree $2$ on $C_0$, and $y \circ \varphi$ determines $Y$ from $u$, so $\varphi$ has degree $2$. The poles of $x \circ \varphi$ lie at $u = T/2$ and $u = \infty$. Here $H(T/2) = 0$, so $u = T/2$ is the single point $W$, and $\infty$ is a single point. The fibre over $O$ has degree $2$ and contains both, so $\varphi^*(O) = W + \infty$. The zeros of $x \circ \varphi - \beta$ are where $u = \beta$, that is at $B$ and $\iota B$. They are distinct, because $H(\beta) = -(T - 2\beta)G(\beta) \ne 0$: $T - 2\beta = \beta^q - \beta \ne 0$, and $G(\beta) = (T - 2\beta)^2 g(\beta) \ne 0$ since $x(\beta) = \beta$. Both points map to $T_2$, and the fibre has degree $2$. $\square$

Lemma 3 (the descent map). Let $\psi'(R) = (1 + \sigma)\,\varphi^*[R - O]$. Then $\psi'$ is a homomorphism from $E(K)$ to $J(\mathbb{F}_q)$, and lines L10 to L12 compute $\psi'(R)$ for every $R \in E(K)$.

Proof. $R \mapsto [R - O]$ is a group isomorphism from $E(K)$ to the classes of degree $0$ on $E$ over $K$, and $\varphi^*$ and $\sigma$ are group homomorphisms on classes. So $\psi'$ is a homomorphism, and its values are fixed by $\sigma$ because $\sigma^2$ is the identity on classes defined over $K$. So they lie in $J(\mathbb{F}_q)$. Since $\operatorname{div}(u - T/2) = 2W - 2\infty$, the class $\omega = [W - \infty]$ has $2\omega = 0$, and $\sigma \omega = \omega$ because $W$ is defined over $\mathbb{F}_q$. So $(1 + \sigma)\omega = 0$.

For $R = O$, $\psi'(O) = 0$. For $R = T_2$, Lemma 2 gives $\varphi^*[T_2 - O] = [B + \iota B - W - \infty]$, and $B + \iota B - 2\infty = \operatorname{div}(u - \beta)$, so this class is $[\infty - W] = \omega$, and $\psi'(T_2) = 0$. This is line L10.

Let now $R = (x_R, y_R) \ne T_2$. On the open set $C' = \{T - 2u \ne 0,\ u \ne \beta\}$ of $C_0$ over $K$, $\varphi$ is given by regular functions. By Lemma 2 the points outside $C'$ map to $O$ or $T_2$, so the fibre over $R$ lies in $C'$, and $\varphi^*(R)$ is the divisor of the ideal $I = (x \circ \varphi - x_R,\ y \circ \varphi - y_R)$ in the coordinate ring of $C'$. Now $x \circ \varphi - x_R = -U(u)/(T - 2u)$ with the $U$ of line L11, and $T - 2u$ is a unit on $C'$. Also $y \circ \varphi - y_R = (u - \beta)(T - 2u)^{-2}\big(Y - y_R (T - 2u)^2 (u - \beta)^{-1}\big)$ with a unit in front. The roots of $U$ are not $\beta$, because $x(\beta) = \beta \ne x_R$, so $u - \beta$ is invertible modulo $U$, and the polynomial $V$ of line L11 is congruent to $y_R (T - 2u)^2 (u - \beta)^{-1}$ modulo $U$ in the ring of $C'$. So $I = (U(u), Y - V(u))$. It contains $(Y - V)(Y + V) = H - V^2$, so $U \mid H - V^2$, and $[U, V]$ is the Mumford pair of $\varphi^*(R)$. Its class is $[\varphi^*(R) - 2\infty] = \varphi^*[R - O] + [W + \infty - 2\infty] = \varphi^*[R - O] + \omega$. Line L12 returns $[U, V] + \sigma[U, V] = \psi'(R) + (1 + \sigma)\omega = \psi'(R)$. $\square$

Lemma 4 (rows are true). If line L16 produces a row $e$ for a class $R = [U, V]$, then $R = \sum_{u_0 \in \mathcal{B}} e_{u_0} F_{u_0}$ in $J(\mathbb{F}_q)$.

Proof. If $U = 1$, then $R = 0$ and the row is empty. Otherwise the reduced divisor of $R$ is $D = \sum_i (u_i, V(u_i))$ over the roots $u_i \in \mathbb{F}_q$ of $U$ with multiplicity, and $R = \sum_i [(u_i, V(u_i)) - \infty]$. From $U \mid H - V^2$ we get $V(u_i)^2 = H(u_i)$, so $u_i \in \mathcal{B}$ and $V(u_i) = \pm Y_{u_i}$. Since $(u_i, Y) + (u_i, -Y) - 2\infty = \operatorname{div}(u - u_i)$, the term is $\pm F_{u_i}$ with that sign. If $Y_{u_i} = 0$ the two signs give the same class, and the root is simple, because $(u - u_i)^2 \mid H - 0$ is impossible for squarefree $H$. A double root with $V(u_i) \ne 0$ gives $\pm 2F_{u_i}$. $\square$

Lemma 5 (elimination). After $k$ relations have been processed in lines L18 to L20, every stored row $v$ satisfies $v \equiv \sum_i c^{(v)}_i e_i \pmod r$ for the combination $c^{(v)}$ kept with it, every dependency $c$ found satisfies $\sum_i c_i e_i \equiv 0$, and the dependencies found so far form a basis of the left kernel $\{c \in (\mathbb{Z}/r)^k : \sum_i c_i e_i \equiv 0\}$.

Proof. A new row $e_k$ starts with the unit vector at $k$ as its combination. Line L18 subtracts multiples of stored rows together with their combinations, and line L20 scales both by the same unit, so the relation is kept. The stored rows have distinct leading columns and zeros before them, and the new row is reduced column by column in increasing order, so a nonzero result has a new leading column. Hence the stored rows stay in echelon form, are independent, and span the same space as $e_1, \dots, e_k$, so their number is the rank $\rho_k$. Each relation adds a stored row or a dependency, so $k - \rho_k$ dependencies were found. The one found at relation $j$ has coefficient $1$ at $j$ and $0$ after $j$, so they are independent, and the left kernel has dimension $k - \rho_k$. $\square$

Lemma 6 (a dependency gives the logarithm). Let $D_1 \in J(\mathbb{F}_q)$ have order $r$ with $r \,\|\, \#J(\mathbb{F}_q)$, and $D_2 = x^* D_1$. If $c$ is a dependency with $A = \sum_i c_i a_i$ and $C = \sum_i c_i b_i$, then $A + x^* C \equiv 0 \pmod r$. So if $C \not\equiv 0$, line L19 returns $x^* \bmod r$.

Proof. Take the $c_i$ as integers in $[0, r)$. By Lemma 4, $\sum_i c_i R_i = \sum_{u_0} \big(\sum_i c_i e_{i, u_0}\big) F_{u_0} = r \sum_{u_0} w_{u_0} F_{u_0}$ for integers $w_{u_0}$. Let $h = \#J(\mathbb{F}_q)/r$. Then $h \sum_i c_i R_i = 0$. On the other side, $R_i = (a_i + x^* b_i) D_1 + r c'_i F_{u^*}$ with the $c'_i$ drawn at line L15, so $h \sum_i c_i R_i = h(A + x^* C) D_1 + \#J(\mathbb{F}_q) \sum_i c_i c'_i F_{u^*} = h(A + x^* C) D_1$. Hence $r \mid h(A + x^* C)$, and $r \nmid h$. $\square$

Lemma 7 (termination of GAUDRY). Under the hypotheses of Lemma 6, GAUDRY stops with probability $1$, and the expected number of draws is finite.

Proof. Let $m = \#J(\mathbb{F}_q)/r$ and write $\operatorname{ord}(F_{u^*}) = r^{\varepsilon} m'$ with $\varepsilon \in \{0, 1\}$, $m' \mid m$ and $r \nmid m'$. Choose $c^* \in [0, m')$ with $r c^* \equiv 1 \pmod{m'}$. Then $(1 - r c^*) F_{u^*}$ has order dividing $r$, and the elements of order dividing $r$ form a subgroup of the Sylow $r$-subgroup, which has order $r$, so it is $\langle D_1 \rangle$. Write $(1 - r c^*) F_{u^*} = \lambda D_1$. For each $b \in [0, r)$, the draw $a \equiv \lambda - b x^*$, $b_j = b$ and $c_j = c^*$ gives $R_j = \lambda D_1 + r c^* F_{u^*} = F_{u^*} = [u - u^*, Y_{u^*}]$, whose row is $+1$ at $u^*$. So each draw gives this row with a given $b_j = b$ with probability at least $1/(r^2 m)$, independently of the other draws. With probability $1$ there are eventually draws $j < k$ with this row and $b_j \ne b_k$, after a finite expected number of draws. The vector $c$ with $1$ at $k$ and $-1$ at $j$ is in the left kernel after relation $k$, with $\sum_i c_i b_i = b_k - b_j \ne 0$. $C$ is linear in $c$, and by Lemma 5 the dependencies found by then form a basis of the kernel, so one of them has $C \ne 0$. Line L19 stops at the first such dependency. $\square$

Correctness. If $nQ \ne O$, then $Q \notin \langle P \rangle$ and line L2 returns NONE correctly. Otherwise take a prime power $r^e \,\|\, n$. If the test of line L5 fails, baby-step giant-step on $\langle P_r \rangle$, of order $r^e$, returns $x_r$ with $x_r P_r = Q_r$ or reports correctly that $Q_r \notin \langle P_r \rangle$. If it holds, then $e = 1$, and $D_1 = \psi(P_r) \ne 0$ has $r D_1 = \psi(r P_r) = 0$ by Lemma 3, so $D_1$ has order $r$, and $r \,\|\, \#J(\mathbb{F}_q)$. Also $r \psi(Q_r) = \psi(nQ) = 0$, so $\psi(Q_r)$ lies in the subgroup of elements of order dividing $r$, which is $\langle D_1 \rangle$ as in Lemma 7. By Lemmas 6 and 7, GAUDRY returns $y$ with $\psi(Q_r) = y D_1$. If $Q_r = y' P_r$, then $y' D_1 = \psi(Q_r) = y D_1$, so $y \equiv y' \pmod r$ and line L7 accepts $x_r = y$. If $Q_r \notin \langle P_r \rangle$, then $y P_r \ne Q_r$ and line L7 returns NONE, which is correct by Lemma 1. When every prime power passes, Lemma 1 shows that line L9 returns the unique $x \in [0, n)$ with $xP = Q$.

Termination. The loop of line L3 runs once for each prime dividing $n$, baby-step giant-step terminates, and GAUDRY terminates with probability $1$ by Lemma 7. $\blacksquare$