**EC Cryptography Tutorials - Herong's Tutorial Examples** - v1.03, by Herong Yang

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-1}P + ... + 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^{7}P+2^{4}P+2^{2}P+2P+P Using the double-and-Add algorithm, 151*P can be calculated as: 2^{7}P+2^{4}P+2^{2}P+2P+P = P + (2P: double(P)), 2 operations + (2^{2}P: double(2P)), 2 operations (2^{3}P: double(2^{2}P)), 1 operation + (2^{4}P: double(2^{3}P)), 2 operations (2^{5}P: double(2^{4}P)), 1 operation (2^{6}P: double(2^{5}P)), 1 operation + (2^{7}P: double(2^{6}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^{64}:

Scalar Multiplication: Find Q, such that Q = nP requires: 128 operations DLP: Find n, such that Q = nP requires: 2^{64}= 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.

Table of Contents

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)

►Scalar Multiplication on Elliptic Curve as Trapdoor Function

Generators and Cyclic Subgroups

tinyec - Python Library for ECC

ECDH (Elliptic Curve Diffie-Hellman) Key Exchange

ECDSA (Elliptic Curve Digital Signature Algorithm)