6
$\begingroup$

Whenever I read about elliptic curve cryptography (ECC), the writer always works over a finite field. But as I understand it there is no group-theoretic reason not to use $\mathbb{Q}$ as the underlying field (you still get an abelian group, lots of things about this group are still unknown).

Is there any reason why nobody does ECC over $\mathbb{Q}$? Is there some known attack that makes it insecure? Is it just too inefficient?

$\endgroup$

2 Answers 2

6
$\begingroup$

I am assuming you mean strictly doing everything in $\Bbb Q$, including eventual transmission. It is not sensible to do computations in $\Bbb Q$ and reducing to $\mathbb F_p$ before sending out since that is harder to do and you do not gain anything. The summary of the following discussion is that you cannot use any generated points to keep secrets.


Points $P$ in an Elliptic Curve $E$ over $\Bbb Q$ are of the form $$P=T+k_1Q_1+k_2Q_2+\cdots+k_rQ_r \quad k_1,\dots,k_r\in\Bbb Z$$ where $r$ is the rank of $E$ and $T$ is a torsion point.

It is well-known that there at most 16 possible $T$ by Mazur's Torsion Theorem.
The maximum value of $r$ is unknown: the current best result is 18.
There are known examples that has rank at least 28 but for those we do not know the exact $r$.
This means that when we construct Elliptic Curves over $\Bbb Q$, more or less it is generated by $\leq 18$ points, by choosing $k_1,\dots,k_r$. i.e. there are not many possibilities for $Q_i$'s, so you need $k_i$'s to be difficult to guess.

Now the problem is, given $P$, generally you can find $k_1,\dots,k_r$ easily.
Whenever you add some $Q_i$, the values in the point $(X,Y)$ increases significantly.
Moreover, the size is strictly increasing after the small values and the growth is predictable.
This means looking at $P$ you can tell the range of values for $k_i$ and it will be trivial to test these values.

Let us look at an example.

The Elliptic Curve $$E:=Y^2=X^3-27X+90$$ has rank 2 generated by $Q_1=(-5,10),Q_2=(-3,12)$.
Take $P=(-5,10)$ and consider $\varphi(P)=\{P,[2]P,[3]P,\dots\}$.
We will get: $$\left\{(-5,10),\left(\dfrac{394}{25}, \dfrac{-7478}{125} \right), \left(\dfrac{148795}{269361},\dfrac{1212735770}{139798359} \right), \left(\dfrac{25189696321}{5592048400},\dfrac{-3233187530793631}{418173379352000}\right),\left(\dfrac{41697179388698395}{10487471993072881}, \dfrac{7244632674771290918438950}{1074004796869053110612279}\right),\dots\right\}$$

Notice that the growth is exponential. More precisely, the maximum value of numerator and denominator of $x$-coordinates is roughly squared when it goes from $P\to 2P$. So if indeed a generated $P$ is of the form $P=k_1Q_1$, then using this reference it is easy to tell what $k_1$ is like. In practice there are formula for the sizes.

The same method can be generalized to include all $Q_i$'s, so if I look at a generated $P$, the sizes of the coordinates will already tell me what kind of $k_i$'s are used to generate it. Therefore you cannot use it to keep secrets since they are guessable. This does not happen in finite fields since the values wrap around and you cannot tell how many times that occurs.

$\endgroup$
1
  • $\begingroup$ Quite. Not forgetting that a practical cryptosystem has a limited bandwidth for communication. After $n$ duplications the denominator and the numerator have been, crudely speaking, raised to power $2^n$. Meaning that transmitting those rational numbers takes a very long time :-) $\endgroup$ Commented Oct 12, 2019 at 19:28
4
$\begingroup$

You are right. The computation is just too inefficient. The best known attack on ECDLP, the pollard rho attack, would be useless against elliptic curves over the rationals.

Consider this, if you were to do the computations over a finite field of say 512-bits, you will only have to deal with 512-bit intermediate values along the way. Considering the same elliptic curve over the rationals and using the same operations (computing $[k]P$, say) would give us the same security (computing $[k]P$ over a finite field and computing $[k]P$ over the rationals then converting into the finite field equivalent is the same!).

Although I do agree that over the rationals, there are highly desirable qualities, such as an infinite abelian group, it is just too bothersome to be implemented.

$\endgroup$
8
  • $\begingroup$ But if it's so much more inefficient, wouldn't that allow one smaller key sizes to balance it out? $\endgroup$
    – JeremyKun
    Commented Feb 17, 2014 at 4:24
  • $\begingroup$ @JeremyKun That would be inadvisable for the system would now be weaker. Also, using a small key size would not exploit the "infiniteness" of using EC over the rationals. So, why use the rationals if you are not going to use its property? $\endgroup$
    – BlackAdder
    Commented Feb 17, 2014 at 4:34
  • $\begingroup$ I think you're saying, "addition is less efficient over $\mathbb{Q}$ but we don't know how to quantify how much less efficient it is." I'm trying to justify why to use finite fields, when the rationals seem like a perfectly fine choice a priori. Less knowledge is one good reason, and not being able to quantify tradeoffs is another. But "why bother?" is not. $\endgroup$
    – JeremyKun
    Commented Feb 17, 2014 at 14:49
  • 1
    $\begingroup$ @JeremyKun I agree with you and do apologise for the sketchy-ness of my answer. But as mentioned, we tend to do cryptography over finite fields just because it makes sense computationally. The reason we do ECC over a finite field is the same reason why we perform powermod in RSA (where you take mod over successive powers rather than mod after the powering is done). It is not too difficult to quantify now quickly the numbers grow for performing addition/multiplication in the rationals. Note that firstly, we need to allocate space for two sets of numerators and denominators. $\endgroup$
    – BlackAdder
    Commented Feb 18, 2014 at 0:56
  • $\begingroup$ cont': Now, each successive addition and doubling grows, very roughly, wrt degree $4$ in terms of the $x$-coordinate. So we can imagine our initial value to blow up after a while. $\endgroup$
    – BlackAdder
    Commented Feb 18, 2014 at 1:00

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .