Scalar Multiplication on Elliptic Curve as Trapdoor Function

EC Cryptography Tutorials - Herong's Tutorial Examples

∟Scalar Multiplication on Elliptic Curve as Trapdoor Function

This section confirms that Scalar Multiplication on Elliptic Curve is a good Trapdoor Function by the comparing difficulty level against its reverse operation, which is the DLP.

In the previous tutorial, we mentioned that the Scalar Multiplication operation as defined in the Elliptic Curve Abelian Group is a good candidate to build a trapdoor function. Now let's confirm this by comparing the difficult level of the Multiplication operation and the DLP (Discrete Logarithm Problem) as its reverse operation.

Scalar Multiplication Operation Using Double-and-Add Algorithm

For a given point P on an elliptic curve, the scalar multiplication operation of P for n times is to find another point Q, such that:

   Q = nP = P+P+P+...+P

A straight forward algorithm to find Q is to perform n-1 addition operation as shown below:

Calculate 2P = P + P
Calculate 3P = 2P + P
Calculate 4P = 3P + P
Calculate 5P = 4P + P
Calculate 6P = 5P + P
Calculate 7P = 6P + P
Calculate 8P = 7P + P
...
Calculate nP = (n-1)P + P
Set Q = nP

However, we have another much faster algorithm, called double-and-add algorithm, to find Q:

Calculate 2P = double(P) = P + P
Calculate 3P = add(2P,P) = 2P + P              skip if 3P is not needed
Calculate 4P = double(2P) = 2P + 2P
Calculate 5P = add(4P,P) = 4P + P              skip if 5P is not needed
Calculate 6P = add(4P,2P) = 4P + 2P            skip if 6P is not needed
Calculate 7P = add(add(4P,2P),P) = 4P + 2P + P skip if 7P is not needed
Calculate 8P = double(4P) = 4P + 4P
...
Calculate nP = ... = 2^k-1P + ... + 2P + P
Set Q = nP

It can be easily proved that the double-and-add algorithm requires less than 2k operations, or O(k) operations, where k is the number of binary digits used to represent the integer n.

Here is an example to demonstrate the double-and-add algorithm taken from "Elliptic Curve Cryptography: a gentle introduction" by Andrea Corbellini at andrea.corbellini.name/2015/05/17 /elliptic-curve-cryptography-a-gentle-introduction/:

To calculate:
   Q = nP = 151*P, (n=151)

Express n in binary digits:
   n = 0b10010111, (8 digits, so k=8)

Based on the binary digits, we re-write 151*P as:
   151*P = 2⁷P+2⁴P+2²P+2P+P

Using the double-and-Add algorithm, 151*P can be calculated as:
   2⁷P+2⁴P+2²P+2P+P
   = P + (2P: double(P)), 2 operations
     + (2²P: double(2P)), 2 operations
       (2³P: double(2²P)), 1 operation
     + (2⁴P: double(2³P)), 2 operations
       (2⁵P: double(2⁴P)), 1 operation
       (2⁶P: double(2⁵P)), 1 operation
     + (2⁷P: double(2⁶P)), 2 operations

Total number of operation: 11

DLP (Discrete Logarithm Problem) Has No Efficient Algorithm

For a given point P on an elliptic curve, and another point Q, the DLP (Discrete Logarithm Problem) is to find integer n, such that:

   Q = nP = P+P+P+...+P

The only way to solve this DLP is the trial-and-error algorithm:

Calculate P, compare with Q
Calculate 2P = P + P, compare with Q
Calculate 3P = 2P + P, compare with Q
Calculate 4P = 3P + P, compare with Q
Calculate 5P = 4P + P, compare with Q
Calculate 6P = 5P + P, compare with Q
Calculate 7P = 6P + P, compare with Q
Calculate 8P = 7P + P, compare with Q
...
Calculate nP = (n-1)P + P, compare with Q

This will require n operations, or O(2^k) operations, where k is the number of binary digits used to represent integer n.

For the example of 151*P, we need 151 operations to find n, comparing to 11 operations to calculate 151*P.

For a larger n, the difference of the difficult levels is huge. For example, for n = 2⁶⁴:

Scalar Multiplication: Find Q, such that Q = nP requires:
    128 operations

DLP: Find n, such that Q = nP requires:
    2⁶⁴ = 9,223,372,036,854,775,808 operations