4
$\begingroup$

Shor's algorithm is for finding period $r$ such that $a^r\equiv 1\bmod N$. Knowing period we can factor $N$.

In RSA we encrypt message $m$ by $m^e\bmod N$ ($e$ and $N$ are public keys).

Let us pick the message (and so we know $m$) and encrypt to get $y\equiv m^e\bmod N$.

Can Shor's algorithm be modified to get $d$ (the private decryption key) directly such that $y^d\equiv m\bmod N$ without factoring $N$? (the equation $y^d\equiv m\bmod N$ looks similar to $a^r\equiv 1\bmod N$)

If so, is there any advantage in terms of the number of qubits needed?

To clarify: I want to learn $d$ before learning any other information which will factor on a classical computer in $BPTIME$. Casting the problem as a discrete logarithm problem requires knowledge of order of $m$ which already factors $N$ without finding $d$. I want to find $d$ without knowing other information which can factor $N$ before learning $d$.

$\endgroup$

1 Answer 1

3
$\begingroup$

First, welcome to the quantum stack exchange. Please find below an answer, in two parts:

  1. Given $m \in \mathbb Z_N^*$ and $y = m^e$, computing $d$ so that $m = y^d$ is the discrete logarithm problem (DLP).

    Shor's quantum algorithm for the DLP — that is also described in [Shor94] alongside Shor's order-finding and factoring algorithms — solves this problem (when slightly generalized as in e.g. [E19p] to work in the cyclic subgroup of $\mathbb Z_N^*$ that is generated by $m$).

    However, it is not more efficient than Shor's order-finding algorithm. Furthermore, it requires the order $r$ of $m$ to be known, and if you know $r$ or a multiple thereof then you can factor $N$ classically (with probability very close to one via [E21b], provided that you select $m$ uniformly at random from $\mathbb Z_N^*$ at the outset, and this is easy).

    Another possible option is of course to compute the order $r$ of $m$, or a multiple thereof, and to use that $d \equiv e^{-1} \text{ mod } r$, if this is what you are looking for? This would not save qubits. It may perhaps save runs when using Shor's original reduction, but not when using [E21b]. Yet another option is to use the variation in [E21a] that computes $d$ without requiring $r$ to be known beforehand, but this variation is also less efficient (and it in fact computes both $d$ and $r$ even if you need not explicitly compute $r$ in the post-processing to compute $d$). In short, I think that this all boils down to a question of semantics, because once you learn $d$, you know that $ed - 1$ is a multiple of $r$, and so you can use [E21b] to factor $N$ classically.

  2. If you are looking to achieve an advantage by phrasing the RSA integer factoring problem (IFP) as a DLP, then you may instead wish to have a look at [EH17]. In this work, we pick $g$ uniformly at random from $\mathbb Z_N^*$, for $N = pq$ a random RSA integer, compute $$x = g^{(N+1)/2} = g^{(p+q)/2},$$ classically, and then compute the logarithm $d = \log_g x$ using a quantum algorithm that leverages that $d$ is short in relation to the order of $g$ with overwhelming probability, and which critically does not require the order to be known. With high probability of success, this algorithm yields $d = (p+q)/2$, and since we also know that $N = pq$ it is then trivial to solve for $p$ and $q$ classically.

    This DLP-based algorithm is more efficient than Shor's order finding-based approach [E20], but it only works for RSA integers (it can be extended to other special forms, but factoring RSA integers is arguably the interesting case).

(Note that $d$ in the second part of this answer is different from $d$ in the first part, and that the order $r$ of $m$ is also the order of $y$ by construction since $e$ is coprime to $\lambda(N)$ in RSA. Note also that $d$ in the first part of this answer would typically be on $[0, r)$, in which case $d$ is not the full private key, although it will decrypt $y$.)

$\endgroup$
7
  • $\begingroup$ I thought for Shor's discrete log algorithm modulo $N$, the factorization of $N$ has to be known. And so solving $y^d\equiv m\bmod N$ is not quite possible by Shor's algorithm for discrete log as factorization of $N$ is unknown. Am I wrong? $\endgroup$
    – Turbo
    Jul 27, 2023 at 0:27
  • $\begingroup$ @Turbo You would need to know the order $r$ of $m$, but to compute $r$ classically without the complete factorization of $N$ is hard. You would also need the complete factorization of $p - 1$ for $p$ the prime factors of $N$. (If you had an efficient classical algorithm for computing $r$, then you could use it to factor $N$.) $\endgroup$ Jul 27, 2023 at 0:36
  • $\begingroup$ So we cannot compute $d$ as discrete logarithm problem without factoring using your idea? $\endgroup$
    – Turbo
    Jul 27, 2023 at 0:42
  • $\begingroup$ @Turbo Maybe without explicitly factoring $N$, if you count the "Another possible option (..)" paragraph in the first part of my answer as a valid solution? It depends on what you mean by "without factoring". Once you learn $d$, then $ed - 1$ is a multiple of the order $r$, and so you can factor $N$ completely via E21b. $\endgroup$ Jul 27, 2023 at 0:53
  • $\begingroup$ I want to learn $d$ before learning any other information which will factor on a classical computer. $\endgroup$
    – Turbo
    Jul 27, 2023 at 1:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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