4
$\begingroup$

In cryptography there are two problems which are part of the foundation of modern public key cryptography. Both of them can be solved in polynomial time on quantum computers. I am talking about:

  • FACT

    Given: A composite number, i.e. a positiv integer which is the product of some prime numbers: $x = p_1 \cdot p_2 \cdot \ldots \cdot p_n$ You know only $x$.

    Wanted (calculation problem): At least one factor of this composite number.

    As a decision problem: For a given $k \le x$: Is there a factor $p_i \le k$?
    (You just need to solve the decision problem $\log x$ times to solve the calculation problem. So, as long as the complexity of the decision problem is polynomial or harder, both flavors of the problem belong to the same time-class.)

  • DISCRETE LOG

    Given: $x = a^n \mod p$. There $p$ is prime and you know $x$, $a$ and $p$.

    Wanted (calculation problem): Find $n$.

    As a decision problem: Is there some $n \le k$ such that $x=a^n \mod p$?
    (Also here you need to solve the decision problem only $\log p$ times to solve the calculation problem.)

I know, that both problems, as far as we know, are not in the complexity class $P$, i.e. for both problems there is no algorithm know that could solve them in polynomial time on a deterministic Turing Machine.

I know, that both problems can be solved in polynomial time on a non-deterministic Turing machine, which, per definition means, that both of them are in the class $NP$.

Let's suppose, that $P \ne NP$. Under this assumption $NP$ is partitioned into three sub-classes:

  • $P$
    All problems which are solvable in polynomial time on a deterministic Turing Machine
  • $NPC$
    NP-complete.
    The subset of $NP$ to which all problems in $NP$ can be reduced, i.e. the subset of $NP$ that is NP-hard.
  • $NPI$
    NP-intermediate
    All problems which are in $NP$ but neither in $P$ nor in $NPC$.

It is known, than $NPI$ is not empty if $P \ne NP$ (Ladner's theorem).

(If $N=NP$, then also $NPC=P$, which means, that $NPI$ must be empty.)

I know, that under the assumption that $P \ne NP$, FACT seems to be in $NPI$, since until now nobody could prove that FACT $\in NPC$.

But I could not find similar statements about DISCRETE LOG.

Here are my questions:

  • Is DISCRETE LOG know to be in $NPC$? Or is it thought to be in $NPI$?
  • If it is in $NPI$:
    • Is there a know algorithm to reduce FACT to DISCRETE LOG?
    • Or is there an algorithm to reduce DISCRETE LOG to FACT?
    • Are they maybe even equivalent, i.e. reduzibel in both directions?
Improve this question
$\endgroup$
0
6
$\begingroup$

No one knows, but:

  • It is suspected that neither factoring nor discrete logarithm are NP-complete, but we have no proof. (Evidence for the suspicion: they are in NP $\cap$ coNP. See, e.g., https://cstheory.stackexchange.com/q/159/5038, https://cstheory.stackexchange.com/q/167/5038 for factoring. It's similarly easy to prove that discrete log is in NP $\cap$ coNP; see, e.g., How hard is finding the discrete logarithm?. Moreover, if any problem in NP $\cap$ coNP is NP-complete, it follows that NP = coNP. This would be an unexpected result.)

  • It is suspected that there is no polynomial-time algorithm for factoring or discrete logarithm, but we have no proof. (Evidence for the suspicion: we haven't been able to find a polynomial-time algorithm for either, despite a lot of trying.)

  • There is no known (classical) reduction between discrete log and factoring. However, I personally wouldn't be shocked if one were found, or if both were found to be instances of some broader problem, or something. For instance, when we find an algorithm technique that works against one, historically often we've been able to adapt it to the other as well. So, they seem to be connected or related in some deep way.

Improve this answer
$\endgroup$
3
  • $\begingroup$ So, when there is no known reduction between both problems, how can the same algorithm (Shor's Algorithm) solve both of them on a quantum computer? I know how Shor's Algorithm works for factorization (by using QFT = Quantum Fourier Transformation to find the order of a cyclic group), but I couldn't find an intelligible description of Shor's Algorithm for solving the discrete logarithm. I just think that Shor also reduces the discrete log problem to QFT. $\endgroup$ – Hubert Schölnast Aug 28 '19 at 6:50
  • $\begingroup$ @HubertSchölnast the reduction you are talking about works by preparing an exponentially large superposition and then looking for the period in that monster. We know how to do this efficiently on a quantum computer only. $\endgroup$ – Dmitri Urbanowicz Aug 28 '19 at 9:41
  • 1
    $\begingroup$ I would like to note that, some instance of the DLog problem can be easy. How can there be insecure elliptic curves if the discrete logarithm problem is hard? $\endgroup$ – kelalaka Aug 29 '19 at 19:24
2
$\begingroup$

In regards to the relationship between discrete logarithm and factoring, it seems worth mentioning that both problems are special cases of the Hidden Subgroup Problem. Shor's Algorithm, under the covers, is really solving this problem. Here are some references: factorization, discrete log.

The last link also mentions how integer factorization can tecnically be reduced to discrete log, though it isn't quite the same situation as standard cryptographic uses of the discrete log (factoring N is the same taking the discrete log modulo N, while cryptographic uses take the discrete log modulo a prime).

Improve this answer
$\endgroup$
3
  • $\begingroup$ Thank you. Is there any evidence that standard classical algorithms (quadratic sieve, NFS, etc.) are also really solving the hidden subgroup problem, under the covers? Is there any understanding why classical algorithms that works for one also work for the other, with some adaption? $\endgroup$ – D.W.♦ Feb 24 at 5:26
  • $\begingroup$ That reduction is misleading. You can reduce integer factorization to discrete logs modulo composite numbers. However, that's not the discrete log problem people mean, when they talk about the hardness of discrete logs; they are usually talking about discrete logs modulo a prime. No one knows how to reduce factoring to discrete logs modulo a prime; yet for some reason the two problems seem to have a similar complexity, as best we can tell today. $\endgroup$ – D.W.♦ Feb 24 at 5:27
  • $\begingroup$ @D.W. Good point, I've incorporated this info into my answer. I think this might be a good illustration of the difficulty in reducing factorization of a composite number to discrete log over some prime number: there just isn't a natural choice of prime. $\endgroup$ – JSquared Mar 2 at 2:14

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.