**EC Cryptography Tutorials - Herong's Tutorial Examples** - Version 1.00, by Dr. Herong Yang

DLP And Trapdoor Function

This section exams the difficulty level of the Discrete Logarithm Problem (DLP) in several Abelian Group examples to see if them can be used to build trapdoor functions.

Now we understand what is a trapdoor function. Let's review at the Exponentiation (or Scalar Multiplication) operation Abelian Groups again. We want to know if it can be used as a trapdoor function, because its reversion operation, the DLP seems to be harder to solve.

DLP Example 1: Arithmetic addition over the integer set of ..., -2, -1, 0, 1, 2, ... is an Abelian Group. Its DLP is too easy to solve.

Given P and (Q = nP), find the smallest n as: n = Q/P

So this Abelian Group is not suitable to build a trapdoor function:

DLP Example 2: Arithmetic multiplication over the rational number set of ..., -1, -1/2, -1/3, 0, 1/3, 1/2, 1, ... is an Abelian Group. Its DLP is not that easy solve. But we have efficient algorithms to get it done.

Given P and (Q = P^{n}), find the smallest n as: n = log_{P}(Q)

So this Abelian Group is not suitable to build a trapdoor function:

DLP Example 3: Modular 10 arithmetic addition over the integer set of 0, 1, 2, ..., 9 is an Abelian Group. Its DLP is too easy to solve:

Given P and (Q = nP), find smallest n as: n = Q/P (mod 10)

So this Abelian Group is not suitable to build a trapdoor function:

DLP Example 4: Modular 11 arithmetic multiplication over the integer set of 1, 2, ..., 10 is an Abelian Group. Its DLP is not that easy solve. But we have efficient algorithms to get it done.

Given P and (Q = P^{n}), find the smallest n as: n = log_{P}(Q) (mod 11)

So this Abelian Group is not suitable to build a trapdoor function:

DLP Example 5: Modular 6700417 arithmetic multiplication over the integer set of 1, 2, ..., 6700416 is an Abelian Group. Its DLP is not that easy solve. But we have efficient algorithms to get it done.

Given P and (Q = P^{n}), find the smallest n as: n = log_{P}(Q) (mod 6700417)

So this Abelian Group is not suitable to build a trapdoor function:

DLP Example 6:
Points on the elliptic curve y^{2} = x^{3} - 7x + 10
with the addition operation defined by the rule of chord
is an Abelian Group. Its DLP is very hard solve when n large number.
There is no known algorithms to get it done efficiently.

Given P and Q on the curve, find the smallest n, such that: Q = nP

So this Abelian Group is good candidate to build a trapdoor function. In the next tutorial, we will compare the effort of performing the scalar multiplication with the effort of solving the DLP to demonstrate that this is a good trapdoor function.

Last update: 2019.

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)