• Home
• Music
• Books
• Problems
• Writeups
• Contact
• Blog

Smart Attack - Elliptic curves over ${\mathbb{Q}}_p$ and formal groups

This small exposition aims to give a sketch of how the Smart attack works. One can find the precise details in Silverman AEC Exercise 7.13.

Notation used:

• $K$ is a characteristic $0$ local field with discrete normalized valuation $v$
• $\mathcal{O}$ is the ring of integers of $K$
• $\pi$ a uniformizer of $K$
• $\mathfrak{m}$ is the maximal ideal of $\mathcal{O}$
• $k$ is the residue field of $K$
• $p$ is the characteristic of $k$
• $q=p^f$ is the order of $k$
• $E$ an elliptic curve over $K$

The outline of the Smart attack can be summarized as:

We have an exact sequence $0\to E_1(K)\to E_0(K)\to {\tilde{E}}_{ns}(K)\to 0$ due to Hensel’s lemma, and we have an isomorphism $E_1(K)\cong \hat{E}(\mathfrak{m})$ and finally an isomorphism of formal groups ${\log }_{\hat{E}}:\hat{E}(\mathfrak{m})\to \widehat{{\mathbb{G}}_a}(\mathfrak{m})$. In this post we shall attempt to decipher this summary.

For some intuition, one can consider the case that commonly appears in the Smart attack:

• $K={\mathbb{Q}}_p$
• $v=v_p$
• $\mathcal{O}={\mathbb{Z}}_p$
• $\pi =p$
• $\mathfrak{m}=p{\mathbb{Z}}_p$
• $k={\mathbb{F}}_p$

Exact sequence

First we shall consider the reduction map mod $\pi$. For any point $P\in {\mathbb{P}}^n(K)$, by choosing suitable homogeneous coordinates, when we take mod $\pi$ on each coordinate, we get a new point $\tilde{P}\in {\mathbb{P}}^n(k)$. In general, we denote reduction mod $\pi$ by adding a $\stackrel{~}{}$ on top. For instance given the point $[5,6,7]\in {\mathbb{P}}^2({\mathbb{Q}}_3)$, the reduction mod $3$ gives the point $[2,0,1]\in {\mathbb{P}}^2({\mathbb{F}}_3)$. This reduction map gives us the curve $\tilde{E}/k$.

Let ${\tilde{E}}_{ns}(k)$ be the group of nonsingular points on $\tilde{E}$. Since these points are nonsingular, we can lift them up to points in $E(K)$. This suggests we define the group $E_0(K)=\{P\in E(K):\tilde{P}\in \tilde{E}(k)\}$. This gives us a surjective map $E_0(K)\to \tilde{E}(k)$. The kernel of this map is evidently every point that gets mapped to the identity $\tilde{O}$ of $\tilde{E}(k)$, hence we define $E_1(K)=\{P\in E(K):\tilde{P}=\tilde{O}\}$ as the kernel of reduction. Hence by definition, we have the exact sequence

$$0\to E_1(K)\to E_0(K)\to \tilde{E}(k)\to 0$$

(One should verify the maps are indeed group morphisms)

Before we go on, we need a brief discussion on formal groups.

Formal groups

Intuitively, a formal group is a group law that is not explicitly defined over any set. The simplest example is the additive formal group, given by ${\hat{\mathbb{G}}}_a(X,Y)=X+Y$. We first define a formal group law over a ring $R$:

Definition: A one parameter commutative formal group law $\mathcal{F}$ over a ring $R$ is a power series $\mathcal{F}\in R[[X,Y]]$ satisfying:

• $\mathcal{F}(X,0)=X,\mathcal{F}(0,Y)=Y$
• $\mathcal{F}(X,\mathcal{F}(Y,Z))=\mathcal{F}(\mathcal{F}(X,Y),Z)\in R[[X,Y,Z]]$associativity
• $\mathcal{F}(X,Y)=\mathcal{F}(Y,X)$commutativity

As one typically can’t sum infinitely many elements in a ring, the formal group associated with the formal group law can only take on values on the nilpotent elements of $R$. However in the case of rings with a valuation, the notion of convergence is well defined, so in such cases the formal group can take on values in the elements with positive valuation. We denote $\mathcal{F}(I)$ as the group associated with the formal group law taking values in $I$. Typically $I$ would be the nilradical but in the case of rings with valuation, $I$ can be any ideal.

Example: The formal group law ${\hat{\mathbb{G}}}_a=X+Y$ corresponds to addition and the formal group law ${\hat{\mathbb{G}}}_m=X+Y+XY=(1+X)(1+Y)-1$ corresponds to multiplcation. The power series $\frac{X+Y}{1+XY}$ corresponds to velocity addition in special relativity. We have ${\hat{\mathbb{G}}}_a(p{\mathbb{Z}}_p)=(p{\mathbb{Z}}_p{)}^{+}\cong {\mathbb{Z}}_p^{+}$.

We shall now construct the formal group $\hat{E}$ associated to an elliptic curve $E$. Suppose we are given the Weiestrass equation of $E$:

$$y^2+a_{1}xy+a_{3}y=x^3+a_2{x}^2+a_{4}x+a_6$$

In this presentation, every point in the elliptic curves is given by two variables, while our formal group law can really only take in one variable. This motivates us to perform the substitution $z=-\frac{x}{y},w=-\frac{1}{y}$ and we obtain

$$w=z^3+(a_{1}z+a_2{z}^2)w+(a_3+a_{4}z)w^2+a_6{w}^3$$

Now by repeatedly substituting the expression into itself and by taking limits, we can obtain $w=f(z)\in \mathbb{Z}[a_1,\dots ,a_6][[z]]$. This gives us a one parameter parametrization of points on the curve. Let $g(z)$ be the corresponding point on the curve, we define the elliptic curve formal group law as

$$\hat{E}(X,Y)=g^{-1}(g(X)+g(Y))$$

For notation purposes, we let $(x(z),y(z))$ be the cprresponding point on the curve.

Like most algebric objects, we have a notion of morphisms of formal groups as well:

Definition: A morphism $\varphi :\mathcal{F}\to \mathcal{G}$ of formal group laws is a power series $\varphi \in R[[X]]$ such that

• $\varphi (0)=0$
• $\mathcal{G}(\varphi (X),\varphi (Y))=\varphi (\mathcal{F}(X,Y))$

Example We have the identity $\varphi (X)=X$ for every formal group law. Consider the power series over a $\mathbb{Q}$-algebra $\varphi (X)=\log (1+X)=X-\frac{X^2}{2}+\frac{X^3}{3}+\dots$, this is a morphism $\varphi :{\hat{\mathbb{G}}}_a\to {\hat{\mathbb{G}}}_m$ and it has an inverse, $e^X-1=X+\frac{X^2}{2!}+\frac{X^3}{3!}+\dots$, hence the formal group laws ${\hat{\mathbb{G}}}_a$ and ${\hat{\mathbb{G}}}_m$ are isomorphic over $\mathbb{Q}$-algebras.

We see that we have found an isomorphism between ${\hat{\mathbb{G}}}_a$ and ${\hat{\mathbb{G}}}_m$, which would make the discrete log problem quite easy whenever this exists. So now our goal is to find such an isomorphism for other formal groups. If we can find an isomorphism $\hat{E}\cong {\hat{\mathbb{G}}}_a$, the discrete log problem on the corresponding curve should be computatinally easy to solve. This isomorphism is given by the logarithm of formal groups:

Definition: For a formal group $\mathcal{F}$, ${\log }_{\mathcal{F}}$ is an isomorphism from $\mathcal{F}$ to ${\hat{\mathbb{G}}}_a$.

For $\mathbb{Q}$-algebras, such an isomorphism always exists and is given by

$${\log }_{\mathcal{F}}(T)=\int \frac{dT}{{\partial }_{X}F(0,T)}$$

where we require ${\log }_{\mathcal{F}}(0)=0$, fixing the constant of integration. One can quickly verify that we recover $\log (1+T)$ in the case of ${\hat{\mathbb{G}}}_m$. In the case of elliptic curves, the differential being integrated is the classic invariant differential of an elliptic curve

$$\frac{dz}{{\partial }_X\hat{E}(0,z)}=\frac{dx(z)}{2y(z)+a_{1}x(z)+a_3}$$

As the inverse of ${\log }_{\mathcal{F}}$ may not converge for a formal group associated with $\mathcal{F}$, we may not always have the isomorphism $\mathcal{F}(I)\cong {\hat{\mathbb{G}}}_a$, however for charateristic $0$ local fields (using the convention at the start), we have

$${\log }_{\mathcal{F}}:\mathcal{F}\left({\mathfrak{m}}^r\right)\to {\hat{\mathbb{G}}}_a\left({\mathfrak{m}}^r\right)$$

is an isomorphism if $r>\frac{v(p)}{p-1}$.

In summary, each point on a curve can be parametrized by a single parameter $z$, with $z=0$ being the identity. This gives rise to a formal group law $\hat{E}$ which takes this parameter as its input and we have an isomorphism $\hat{E}\cong {\hat{\mathbb{G}}}_a$.

Smart attack

Evidently $\hat{E}(\mathfrak{m})$ is isomorphic to the group of points on $E(K)$ such that $\frac{x}{y}$ has positive valuation. This turns out to be precisely the group $E_1(K)$ that we defined above as all such points must be in the kernel of the reduction map, hence nonsingular. From here we’re almost done. Suppose $E_{ns}(k)$ is a group of order $q$ and suppose we have $n\tilde{P}=\tilde{Q}$ in $E_{ns}(k)$. Let $\log$ be the composite map $E_1(K)\cong \hat{E}(\mathfrak{m})\cong {\hat{\mathbb{G}}}_a(\mathfrak{m})$. Lift $\tilde{P},\tilde{Q}$ to points $P,Q\in E_0(K)$, then since $nP-Q\in E_1(K)$, we have

$$n\log (qP)-\log (qQ)=q\log (nP-Q)=0(\mathrm{mod}{\mathfrak{m}}^{f+1})$$

which gives us some $n\in \frac{\mathcal{O}}{{\mathfrak{m}}^f}=\frac{\mathcal{O}}{(q)}$ as long as $\log (qP)\notin {\mathfrak{m}}^2$. Hence $n$ is a well defined multiplication map of $\tilde{E}(k)$, which gives us a solution to the DLP over $\tilde{E}(k)$.

References

• Johannes Anschütz - Lubin-Tate Spaces (Sommersemester 2021) lecture notes
• Joseph H. Silverman - The Arithmetic of Elliptic Curves