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 7P is not needed
Calculate 4P = double(2P) = 2P + 2P
Calculate 5P = add(4P,P) = 4P + P              skip if 7P is not needed
Calculate 6P = add(4P,2P) = 4P + 2P            skip if 7P 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 = ... = 2k-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 = 27P+24P+22P+2P+P   

Using the double-and-Add algorithm, 151*P can be calculated as:
   27P+24P+22P+2P+P
   = P + (2P: double(P)), 2 operations
     + (22P: double(2P)), 2 operations
       (23P: double(22P)), 1 operation
     + (24P: double(23P)), 2 operations
       (25P: double(24P)), 1 operation
       (26P: double(25P)), 1 operation
     + (27P: double(26P)), 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 = (9n-1)P + P, compare with Q

This will requite n operations, or O(2k) 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 = 264:

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

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

So Scalar Multiplication operation in additive notation on an elliptic curve is indeed a good trapdoor function.

Last update: 2019.

Table of Contents

 About This Book

 Geometric Introduction to Elliptic Curves

 Algebraic Introduction to Elliptic Curves

 Abelian Group and Elliptic Curves

Discrete Logarithm Problem (DLP)

 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

 Finite Fields

 Generators and Cyclic Subgroups

 Reduced Elliptic Curve Groups

 Elliptic Curve Subgroups

 tinyec - Python Library for ECC

 EC (Elliptic Curve) Key Pair

 ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

 ECDSA (Elliptic Curve Digital Signature Algorithm)

 ECES (Elliptic Curve Encryption Scheme)

 Terminology

 References

 Full Version in PDF/EPUB