2
$\begingroup$

By definition, the discrete logarithm problem is to solve the following congruence for $x$ and it is known that there are no efficient algorithm for that, in general.

$$\begin{align*} b^x\equiv r&\pmod p\quad(1)\end{align*}$$ It is to find $x$ (if exists any) for given $r,b$ as integers smaller than a prime $p$.

Am I right so far? please correct me if I am misunderstanding anything.

In elliptic curve cryptography it is said that in $P=a\times G$ we can not calculate $a$ by knowing $P$ and $G$ because the discrete logarithm problem is hard to solve. I don't understand that how is this related to equation 1. I mean is that only terminology similar in both problems?

To clarify my question lets imagine that a genius from future generations can finally introduce a solution to equation 1 which is done in feasible time by using an average hardware set up of the time. The algorithm they propose is capable of finding $x$ (if exists) for any given prime $p$ and any given $r, b$. Now, I want to know that is this invention a threat to security of elliptic curve cryptography? In other words, will the knowledge of such algorithm help in retrieving $a$ from $P$?

If yes please explain how is this relation defined and what is the math flow by which we can calculate $a$ from $P$, which I guess will have to pass through solving a congruence similar to equation 1.

If no please tell me what is different between the hardness of discrete logarithm problem in elliptic curves and in that of equation 1 and why is this terminology used here.

$\endgroup$
5

2 Answers 2

6
$\begingroup$

The discrete logarithm problem can be defined for any finite cyclic group, not just the multiplicative group modulo a prime number. The most famous instance is the problem that you describe, but it is not the only one.

Groups can be written with multiplicative notation (as with the multiplicative group modulo $p$), so that the group operation is written as $*$, $\times$, $\cdot$ or simply implicit. In all of these cases we take the natural notation for repeated use of the group operation with a single element i.e. $b^2:=b*b$ and similar generalisations. Thus the generic discrete logarithm problem for a cyclic group $C$ written in multiplicative notation generated by $b$ is given $r\in C$ find an integer $x$ such that $b^x=r$.

Other groups are written with additive notation (this is usually reserved for abelian groups, including elliptic curve groups). In this case the group operation is denoted $+$ (but should not be read as addition in the usual sense) and again there is a natural notation for repeated use of the group operation with a single elements i.e. $2G=G+G$ and so forth. When written in this way the discrete logarithm problem for a cyclic group $C$ generated by $G$ becomes: given $P\in C$ find an integer $x$ such that $xG=P$.

There is not believed to be a clear translation between discrete logarithm problems in different groups. There are some groups where the discrete logarithm problem is easy (e.g. additive groups modulo $p$, multiplicative groups modulo $2^n$ and even (in a quasi-polynomial sense) multiplicative group of $GF(2^n)$).

For the particular case of multiplicative groups modulo $p$ the best known (classical) attack is the number field sieve which solves the problem in sub exponential time. This attack can be applied only to very rare classes of elliptic curve (MOV curves) and the best known generic attacks against elliptic curves are ``square root'' attacks that apply to all groups.

Note that all discrete logarithm problems can be solved in (quantum) polynomial time by Shor's algorithm.

$\endgroup$
3
  • $\begingroup$ Thank you for your answer. Please be more specific about the final question. Is the answer a Yes, or No? I am still confused. $\endgroup$
    – PouJa
    Oct 6, 2021 at 11:31
  • $\begingroup$ No. There is no known way to transfer the problem. $\endgroup$
    – Daniel S
    Oct 6, 2021 at 13:17
  • 1
    $\begingroup$ Also note that all cyclic groups are isomorphic to every other cyclic group of the same order. So $(\mathbb{Z}/{(p-1)}\mathbb{Z})^+$ and $(\mathbb{Z}/p\mathbb{Z})^\times$ are isomorphic for prime $p$, and yet discrete logarithms in $(\mathbb{Z}/{(p-1)}\mathbb{Z})^+$ are easy and discrete logarithms in $(\mathbb{Z}/p\mathbb{Z})^\times$ are hard. $\endgroup$
    – Myria
    Oct 6, 2021 at 21:00
0
$\begingroup$

Let $E$ be an elliptic curve defined over a finite field $\mathbb{F}_p$:

$$E : y^2 = x^3 + Ax + B \text{ with } A, B \in \mathbb{F}_p$$

Let $P$ and $T$ be points in $E(\mathbb{F}_p)$. Find an integer $a$ so that

$$ P =aG$$

This is the problem for elliptic curves. The Problem can be rewritten using a logarithm:

$$ a = log_G (P)$$

You can compare that to the "standard" discrete logarithm:

$$ b^x \equiv r \mod p \Rightarrow x = log_b(r)$$

Do you now see the similarities?

Note: Your genius should have an efficient way to break it, not because he has unlimited resources. And yes, if you got an efficient way to break the discrete logarithm, you can use a variation of that to break elliptic curves. The main point of elliptic curve crypto is, that the calcuations are faster than for the "standard" discrete logarithm systems (there are a lot of different other pros for ecc).

$\endgroup$
4
  • $\begingroup$ what is the point in writing $P=a\times G$ as $ a = log_G (P)$? Why we cannot say $a=P\times G^-1$? When talking about logarithm there should be a base and a power. Here $G$ is not raised to the power of $a$. is it? @titanlord $\endgroup$
    – PouJa
    Oct 6, 2021 at 12:30
  • $\begingroup$ Why do you say that calculations in elliptic curves are faster while calculating $r$ from $b$ and $x$ seems way more straight forward in comparison to that of calculating $P$ from $a$ and $G$ with those adding and doubling functions that involves calculation of modular inverse many times in between? @Titanlord $\endgroup$
    – PouJa
    Oct 6, 2021 at 12:42
  • $\begingroup$ In $\mathbb{F}$ one can rewrite the problems like I did. This should show you the similarities of the problems. The known attacks on the discrete log problem are the basis for the attacks on elliptic curve. E.g. Baby-Step-Giant-Step. $\endgroup$
    – Titanlord
    Oct 6, 2021 at 14:20
  • $\begingroup$ You may calculate that faster on paper. But a computer with standard operations needs a long time for calculating an exponent in $\mathbb{F}$.In reality this results in way more operations, than needed for the add and double approach. $\endgroup$
    – Titanlord
    Oct 6, 2021 at 14:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.