Why Elliptic Curve Cryptography?

Q. Why does modern cryptography prefer the discrete log problem over the additive group of points on an Elliptic Curve defined over a Finite Field rather than integer factorization or the discrete log problem over the multiplicative group of a Finite Field?

A. A cryptographic algorithm is said to have a security level of $n$ bits if the best known attack can break it in $2^n$ steps. So if the naive brute force/exhaustive search is the best known attack for any algorithm the security level will be same as the key size in bits. However most asymmetric algorithms have much better attacks than the naive attack & hence their security level is lesser than the key size. For e.g. the Discrete Log problem on which Diffie Hellman is based on has a very powerful attack called as Index Calculus, which can solve the Discrete Log problem in sub-exponential time. To compensate for this attack, we have to use very large key sizes in DH. To get 112 bit security, DH needs 2048 bit key size.

Index Calculus uses smooth numbers. Likewise, the General Number Field Sieve for Integer Factorzation using smooth numbers means RSA also requires a 2048 bit key size to get 112 bit security. Unlike the multiplicative group of a Finite Field, the group of Elliptic Curve points doesn’t have a straightforward notion of smoothness & any methods similiar to Index Calculus haven’t been discovered in this group. Hence in Elliptic Curve Cryptography, you can get 112 bit security with just 224 bit Key Size.

Key Size for 112 bit security

\[\begin{array}{c|c}\hline {\textbf{Algorithm}} & {\textbf{Size}} \\\hline RSA & 2048 \\\hline DH & 2048 \\\hline ECDH & 224 \\\hline \end{array}\]

Note: For asymmetric algorithms like the above, key size typically refers to the size of the modulus.

So one can use an elliptic curve group that is smaller in size than a regular DH group while maintaining the same level of security. In most situations, the result is smaller key sizes, bandwidth savings and faster operations.

The MOV attack

The MOV (Menezes-Okamoto-Vanstone) attack transforms a Discrete Log problem in an Elliptic Curve Group into a Discrete Log Problem in the Multiplicative Group of a Finite Field - i.e. ECDLP to DLP. Since Index Calclus is possible in DLP, it may become easier to solve the DLP & thus solve the ECDLP.

Some pre-requisite topics before we discuss the MOV attack

What is a bilinear map?

We can look at linear & bilinear maps using the example of Vector Spaces.

Let

• $U, V, W$ be vector spaces
• $\lbrace u, u_1, u_2 \in U \rbrace$ , $\lbrace v, v_1, v_2 \in V \rbrace$
• $\alpha$ is a scalar

 

$f_1 : V \mapsto W \space (f_1$ is a map from $V$ to $W$)

$f_1$ is a linear map if

• $f_1(v_1 + v_2) = f_1(v_1) + f_1(v_2)$

• $f_1(\alpha v) = \alpha f_1(v)$

 

$f_2 : U$ X $V \mapsto W \space (f_2$ is a map from $U$ X $V$ to $W)$

$f_2$ is a bilinear map if

• $f_2(u_1 + u_2, v) = f_2(u_1, v) + f_2(u_2, v)$

• $f_2(u, v_1 + v_2) = f_2(u, v_1) + f_2(u, v_2)$

• $f_2(\alpha u, v) = \alpha f_2(u, v) = f_2(u, \alpha v)$

This means that the map is linear in $u$ if $v$ is fixed & is linear in $v$ if $u$ is fixed.

Roots of Unity

$t$ is an $n$-th root of unity if $t^n = 1$. If you are unfamiliar with “Roots of Unity”, you can take a look at this video.

However, the video talks about the complex roots of unity and not in other structures like a finite field.

Let’s consider roots of unity in a finite field of prime order say $\mathbb F_5 = \lbrace 0, 1, 2, 3, 4 \rbrace$. Every element in this field except for $0$ when raised to $4$ gives $1$. For e.g. $3^4 \bmod 5 \equiv 1$. So every element in the field $\mathbb F_5$ is a $4$-th root of unity. This is because for any non zero element $a \in \mathbb F_q$, we know that $a^q = a$ & hence $a^{q - 1} = 1$ by Lagrange’s Theorem. So every element $a$ in a finite field of prime order $q$ is a ($q-1$)-th root of unity.

Next let’s consider Extension Fields, fields of prime power order i.e. $\mathbb F_{q^t}$

The order of all non-zero $a \in \mathbb F_{q^t}$ is either $q^{t}-1$ or something which divides $q^{t}-1$.

Hence $a^{q^t - 1} = 1$ for all non-zero $a \in \mathbb F_{q^t}$

Hence every non-zero element in an extension field also is a ($q^{t}-1$)-th root of unity.

Embedding Degree

Let $E$ be an elliptic curve defined over a prime field $\mathbb F_q$. Let $P$ be a point of order $m$ where $m$ is prime & is also coprime with $q$.

If $k$ is the smallest positive integer such that

$q^k \equiv 1 \bmod m$

then $k$ is called as the embedding degree of the curve $E(\mathbb F_q)$ with respect to $m$.

Torsion Points and Torsion Groups

$E$ is an elliptic curve defined over a prime field $\mathbb F_q$. A point $P \in E(\mathbb F_q)$ satisfying $mP = \mathcal O$ is called a $m$-torsion point. The subgroup of all $m$-torsion points in $E(\mathbb F_q$) is called the $m$-torsion subgroup of $\mathbb F_q$ & is denoted by $E(\mathbb F_q)[m] = \lbrace P \in E : mP = \mathcal O \rbrace$.

Since the Extension field $\mathbb F_{q^c}$ is bigger than base field $\mathbb F_q$, it’s likely that the $m$-torsion group of the curve over the Extension Field is bigger than the $m$-torsion group of the curve base field. We get the biggest $m$-torsion group when $c$ is equal to the embedding degree of the Curve at $m$ - i.e. going to a bigger extension field than $\mathbb F_{q^k}$ doesn’t add any more $m$-torsion points. Hence $E(\mathbb F_{q^k})[m]$ is called the full $m$-torsion group (where $k$ is the embedding degree of the Curve with respect to $m$).

The Full Torsion Group has multiple subgroups, we use 2 of these subgroups in the Weil Pairing.

• $\mathbb G_1$ - all points in this subgroup are in the Curve over the base field i.e. they are in $E(\mathbb F_q)$.

• $\mathbb G_2$ - all points in this subgroup are in $E(\mathbb F_{q^k})$ with none of them being in $E(\mathbb F_q)$. There are multiple such subgroups, it doesn’t matter which one is chosen.

The Weil Pairing

Since $k$ is the embedding degree of the Curve with respect to $m$,

$q^k \equiv 1 \bmod m$

This can be written as $q^k = mx + 1$

$\therefore q^k - 1 = mx$

$\therefore m$ divides $q^k - 1$

Consider the Extension Field $\mathbb F_{q^k}$. The multiplicative group of this extension field i.e. $\mathbb F^{\star}_{q^k}$ excludes the element $0$ and hence it’s order is $q^k - 1$. Since $m$ divides the order of the multiplicative group, by the Fundamental Theorem of Cyclic Groups, it has a unique subgroup $\mathbb G_T$ of order $m$.

When the additional constraint $m \nmid (q - 1)$ is satisfied, the Weil pairing which is a map from $\mathbb G_1$ X $\mathbb G_2$ to the multipicative group $\mathbb G_T$ can be constructed.

$e_m : \mathbb G_1 \times \mathbb G_2 \mapsto G_T$

$e_m$ takes as input a pair of $m$-torsion points $A$ & $B$ where $A \in \mathbb G_1$ and $B \in \mathbb G_2$. The map gives as output an $m^{th}$ root of unity $e_m(A,B)$. The output of the Weil Pairing when raised to $m$ always gives $1$ - i.e. ${e_m(A,B)}^m = 1$.

Note again that $\mathbb G_1$ & $\mathbb G_2$ are Elliptic Curve Groups while $\mathbb G_T$ is a Multiplicative Group.

These are the properties of the Weil Pairing

• Bilinear:

The Right Hand Side of the Weil Pairing bilinearity is multiplicative rather than the additive bilinearity we saw earlier with Bilinear Maps of Vector Spaces.

$\quad e_m(A_1 + A_2, B) = e_m(A_1, B).e_m(A_2,B)$

$\quad e_m(A, B_1 + B_2) = e_m(A, B_1).e_m(A,B_2)$

Let $G_1$ & $G_2$ be the generators of the 2 Elliptic Curve Groups. Let $\alpha$ & $\beta$ be scalars.

$\quad e_m(\alpha G_1, \beta G_2) = e_m(\beta G_1, \alpha G_2) = e_m(\alpha\beta G_1, G_2) = e_m(G_1, \alpha\beta G_2) = e_m(G_1, \alpha G_2)^{\beta} = e_m(G_1, G_2)^{\alpha\beta}$

• Identity:

   $e_m(A, A) = 1$ for all $A \in E[m]$.

• Alternation:

   $e_m(A,B) = e_m(B,A)^{-1}$ for all $A, B \in E[m]$.

• Non-Degeneracy:

  $e_m(A, \mathcal O) = 1$ for all $A \in E[m]$

  If $e_m(A, B) = 1$ for all $B \in E[m]$, then it means $A = \mathcal O$

Finally, the MOV Attack

Consider an Elliptic Curve $E$ over the field $\mathbb F_q$

We are given points $P$ & $Q$ both of prime order $m$ such that

$Q = rP$

We have to find $r$. This is the Elliptic Curve Discrete Log problem.

Since $P$ is a $m$-torsion point & it’s a point on the Curve over the base field, $P, Q \in \mathbb G_1$

The Steps:

1) Compute the order of the Elliptic Curve over the Extension field i.e. $n = \text# E(\mathbb F_{q^k})$. Since the $m$-Torsion group of $E(\mathbb F_q)$ is a subgroup of $E(\mathbb F_{q^k})$, $m$ divides $n$ (Lagrange’s Theorem)

2) Choose a random point $T \in E(\mathbb F_{q^k})$ such that $T \notin E(\mathbb F_q)$

3) Compute $S = (\frac {n}{m}) T$. If $S = \mathcal O$, then go back to step 2 & chose another random point $T$. If it’s not $\mathcal O$, then it’s a point of order $m$ as shown below

$S = (\frac {n}{m}) T$

$\therefore mS = nT$

Let $t$ be the order of $T$. By Lagrange’s Theorem, $t$ divides the order of $E(\mathbb F_{q^k})$. i.e. $t$ divides $n$. So $n$ can be written as $n = dt$ for some $d$.

$\therefore mS = dtT$

Since $tT = \mathcal O$, $dtT = \mathcal O$.

$\therefore mS = \mathcal O$

So the order of $S$ is $m$.

4)

$P, rP \in \mathbb G_1$

$S \in \mathbb G_2$

Compute the 2 Weil Pairing values

$u = e_m(P, S)$

$v = e_m(rP, S)$ ($rP$ is $Q$ which we know)

$u, v \in \mathbb F_{q^k}$

Since the Weil Pairing is bilinear & $r$ is a scalar,

$v = {e_m(P, S)}^r$

Since $u = e_m(P, S)$, we get

$v = u^r$.

This is the Discrete Log problem(DLP) in the multiplicative group of $\mathbb F_{q^k}$. So we have transformed the ECDLP $Q = rP$ into the DLP $u = v^r$.

5) If $q^k$ is not too large, then $u=v^r$ can be solved using Index Calculus & $r$ can be found. So we have solved $Q = rP$

If the embedding degree $k$ is very large, transforming the ECDLP on $E(\mathbb F_q)$ to a DLP on $\mathbb F_{q^k}$ won’t help. But if the the embedding degree is small enough, then the DLP can become significantly easier. For e.g., a curve with a 256-bit $q$ usually offers 128 bits of security. But if it has an embedding degree $2$, then we can map the discrete logarithm to the field $\mathbb F_{q^2}$ which offers only 60 bits of security which can be broken by Index Calculus.

Mitigation

To ensure that an elliptic curve $E$ defined over $\mathbb F_q$ is immune to the MOV attack, it is sufficient to check that $m$, the order of the base point $P \in E(\mathbb F_q)$, does not divide $q^k - 1$ for all small $k$ for which the $DLP$ in $\mathbb F^{\star}_{q^k}$ is considered tractable. If the order of $P$, i.e. $m \gt 2^{160}$, then it suffices to check this condition for all $k \in [1,20]$.

The actual construction/computation of the Weil Pairing using Rational Functions is beyond the scope of this post.