Discrete Logarithm Problem with Elliptic Curves

Consider an elliptic curve EE, with generator GG and another element TT. Then DLP is finding dd, such that

G+G+G+...+GG+G+G+...+G (d times)(d \ times) =dG=T= d*G = T

To understand the practical implications, we visualize this geometrically on the curve EE :- we first find generator GG on EE, then add GG to it to locate 2G2G.

This is considered the first hop (computationally, it is executing the group operation). Then, we add GG again to mark the value of 3G3G, which is the second hop. By repeating this process, dd times, we finally reach point TT on the curve EE.

As it turns out, finding the number of hops is computationally hard.

So, the starting point is known for elliptic curves, i.e., the generator GG, the final point is known, TT, then DLP is essentially to find the number of hops taken to reach TT from GG.

IMPORTANT Note - for elliptic curves, we use the discrete logarithm problem as:

dd is private key and TT is the public key d=Kprd=K_{pr} - an integer, which is the number of hops in above explanation T=dG=KpubT = dG = K_{pub} This is a point on curve EE, i.e., group element, i.e., it has an xx and yy co-ordinate so T=(xT,yT)T = ( x_T, y_T )

As we define dd as the private key and TT as the public key, the practical implication of the above is that given a known public key, it is very hard to compute the private key.

Terminology note - Generator is also commonly referred to as "base point", so GG is a base point for curve EE.

Credits

Special thanks to Prof. Christof Paar for providing a fantastic Introduction to Cryptography.

Last updated

Was this helpful?