Discrete Logarithm Problem (DLP)

EC Cryptography Tutorials - Herong's Tutorial Examples

∟Discrete Logarithm Problem (DLP)

This chapter provides an introduction to the Discrete Logarithm Problem (DLP), which is the reverse operation of the exponentiation operation in Abelian Groups in multiplicative notation, or the scalar multiplication in additive notation. The DLP in many Abelian Groups is easy to solve. But the DLP in elliptic curve groups is very hard to solve, which make it a good candidate to create trapdoor functions.

Doubling or Squaring in Abelian Group

Scalar Multiplication or Exponentiation

What Is Discrete Logarithm Problem (DLP)

Examples of Discrete Logarithm Problem (DLP)

What Is Trapdoor Function

DLP and Trapdoor Function

Scalar Multiplication on Elliptic Curve as Trapdoor Function

Takeaways:

Point doubling (or squaring) is the addition (or multiplication) of two identical elements in an Abelian group in additive (multiplicative) notation.
Scalar multiplication is an extension of point doubling by adding the same point multiple times sequentially. This is also called point exponentiation in multiplicative notation.
The Discrete Logarithm Problem (DLP) is the reverse operation of the exponentiation operation in an Abelian Group in the multiplicative notation, or the reverse operation of the scalar multiplication operation in the additive notation.
The DLP is very easy to solve in some Abelian Groups and very difficult to solve in other Abelian Groups.
A trapdoor function is an operation that is much easier to perform than its reverse operation.
Multiplication of two large prime numbers is a trapdoor function, because the reverse operation, factoring a large number into prime numbers, is much harder.
Many Abelian Groups are not good candidates to create trapdoor functions, because their DLP are easy to resolve.
Elliptic Curve groups are good candidates to create trapdoor functions, because we have a very efficient double-and-add algorithm for the scalar multiplications and no efficient way for the reverse operation, which is the DLP.