Elliptic curves: discrete logarithm problem
Written by Dominik Joe Pantůček on 2018-05-10
curvescryptographyAlgebraic groups built on top of points of elliptic curves together with the scalar multiplication specified as repeated addition can be used as basic building blocks for asymmetric cryptography systems. The strength of these systems if derived from the toughness of the reversing the scalar multiplication operation. It is very expensive to reverse this operation and to answer a question like "how many times we have to multiply point G to get given point P". This problem is called Elliptic Curve Discrete Logarithm Problem - or ECDLP for short. In this article we show the toughness of this problem.
Note for readers: If you are here just to see the video, you can find it right here.
As we have shown, it is relatively easy to speed up the scalar multiplication operation to $O(log_2n)$[1]. The method double-and-add depicted in Picture 1 should refresh any memories about how this algorithm works.
Picture 1: Performing double-and-add scalar multiplication $R=13\cdot[4,5]$ on elliptic curve in simple Weierstrass form $y^2=x^3-2x+15$ over $\mathrm{GF}(23)$. Reversing this operation is, however, not feasible using similar approach. The only known algorithm to find out how many times we have to multiply a given generator to obtain a given resulting point is to traverse the group of points on the elliptic curve using the naive algorithm[2]. As can be seen in Picture 2, this surely yields the desired result - but for elliptic curves over finite field large enough (and therefore with enough rational points in the group) it would take too long to perform such reversal.
Picture 2: Reversing the scalar multiplication operation - finding how many times it is needed to multiply the point $G=[4,5]$ to obtain the point $R$ on elliptic curve in simple Weierstrass form $y^2=x^3-2x+15$ over $\mathrm{GF}(23)$. Using this iterative approach means that for any number we are trying to find, the complexity grows linearly with the number's size. It is therefore a problem of complexity $O(n)$. Compared to $O(log_2n)$ complexity of performing the multiplication using the double-and-add algorithm this makes the cryptography systems quite secure if we are working with number large enough. You can see how $n$ compares to $log_2n$ in Picture 3.
Picture 3: Comparison of $O(n)$ and $O(log_2n)$ algorithm complexity. But of course - everyone just wants to see the difference in action. So without further ado, just have a look at Video 3 below and see for yourself how the double-and-add algorithm compares to the attempt at reversing it.
Video 3: Comparison of double-and-add scalar multiplication algorithm and its naive reversal.
Now as we have covered the basics of elliptic curves in simple Weierstrass form, including the double-and-add algorithm and the elliptic curve discrete logarithm problem (the attempt to reverse the scalar multiplication operation), we are ready to see some real cryptography next week, so stay tuned. And rest assured, we will soon use it for securing our online communication as well. See you next week!