0
$\begingroup$

In section 4.4 of the paper "Quantum algorithms for computing short discrete logarithms and factoring RSA integers", for an arbitrary set $\left\{ (j_i, k_i):1\le i\le s \right\}$ chosen from measured results $\left\{ (j_i, k_i):1\le i\le t \right\}$ ($t$ is the number of times the circuit is excecuted), the algorithm searches all possible $d$ that saitisfies $$\sqrt{d^2+\sum_{t\,=\,1}^{s}({\left\{ dj_i+2^mk_i \right\}_{2^{l+m}}\,)^2}} < \sqrt{s/4+1}\cdot 2^m$$ Note that $d$ is strictly bounded by $\sqrt{s/4+1}\cdot 2^m$. To do this the algorithm should go as follows:

  1. Prepare an array $D:=\left\{ 0,\,...,\, B - 1 \right\}$, where $B$ is the ceiling of $\sqrt{s/4+1}\cdot 2^m$. Denote $d$ as the first element of $D$.

  2. Choose an arbiyary set $S\subset\left\{ (j_i, k_i):1\le i\le t \right\}$ of size $s$.

  3. Test whether $d$ and $S$ satisfy the above inequality. If test fails, then return to step 2 (this time choose a different $S$).

  4. Test whether $d$ is the desired answer (i.e. whether $x\equiv g^{d}$). If test fails, then remove $d$ from $D$ and return to step 3.

  5. Output $d$.

Here step 2 and 3 are meaningless and can be removed from these steps. In my understanding, if the integer can be factored into two primes, then there is no difference compared with an exhaustive search of $d$ from $0$ to $\sqrt{s/4+1}\cdot 2^m$ (where one exhaustive search of $d$ from $0$ to $2^m$ suffices to find an answer). In what part do I understand wrong in this section?

$\endgroup$
3
$\begingroup$

The idea here is essentially as follows:

  1. We classify the pairs $(j, k)$ produced by the quantum algorithm as either good or bad.

    For a good pair, it holds that $| \{ dj + 2^m k \}_{2^{\ell + m}} | \le 2^{m-2}$.

  2. We lower-bound the probability of the quantum algorithm producing a good pair when run.

  3. We show that given $s$ good pairs, we can solve for the logarithm $d$ using lattice-based techniques.

    Here, $s \ge 1$ is a small parameter that may be freely selected. Increasing $s$ reduces the amount of work that needs to be performed in each run of the quantum algorithm, at the expense of having to run the algorithm multiple times. We gain approximately $\ell \approx m/s$ bits of information on the logarithm $d$ in each run that produces a good pair, for $m$ the bit length of $d$.

  4. The reason we exhaust all subsets of $s$ pairs from the set of $t$ pairs produced in the $t$ runs is that we need all $s$ pairs to be good when solving for $d$. We have no simple way of telling good pairs apart from bad pairs, besides attempting to solve for $d$.

    To understand what the issue is, note that we know nothing about the size of $| \{ dj + 2^m k \}_{2^{\ell + m}} |$ for bad pairs. Including a bad pair $(j, k)$ for which $| \{ dj + 2^m k \}_{2^{\ell + m}} |$ is much larger than $2^m$ when forming the lattice $L$ and vector $\mathbf v$ would make it impractical to solve for $d$.

  5. Of course, we do not propose to exhaust all $d$ from $0$ up to $B \sim 2^m$, and to check for each candidate $d$ whether $x \equiv g^d$. Such an approach would be completely impractical. Furthermore, there would then be no reason for the quantum part of the algorithm.

    What we do propose is to enumerate all vectors $\mathbf u$ in the lattice $L$ that are within bounded distance $B$ of the known vector $\mathbf v$: If the pairs $(j, k)$ used to form $L$ and $\mathbf v$ are all good, there will be few candidates for $\mathbf u$. Furthermore, we can efficiently find these candidates for $\mathbf u$. The logarithm $d$ sought is the last component of $\mathbf u$. Hence, we check for each candidate $\mathbf u$ whether $x \equiv g^d$ and if so return $d$.

    So the short answer is that you must somehow have missed that we are enumerating vectors in a lattice $L$.

Also, please note the following:

  • There is a follow-up work, in which we analyze and capture the complete distribution induced by the quantum algorithm. This allows us to remove the need to classify pairs as good or bad. Instead, we may include all pairs in $L$ and $\mathbf v$. This removes the need to exhaust subsets and improves efficiency.

  • There is a typo in the pre-print; $s/4$ should be $s/2^{4}$. This was corrected in the conference version.

$\endgroup$
4
  • $\begingroup$ Hello Martin. I am reading your follow-up work (2020) and I am confused about the probability distribution. The paper improves the post information process by simulating the distribution of quantum algortihm to set minimum s and R. However, the derivation of the distribution explicitly requires d - the answer of DLP to be known. In what part do I understand wrong about your algorithm? Appreciate your patient answer. $\endgroup$ Sep 18 at 11:50
  • 1
    $\begingroup$ I am not sure if I understand your question @Cloudwin.ZL, but I'll try to answer: In the 2020 paper, I derive a closed-form expression for the probability of observing given outputs from the quantum algorithm. I then use this expression to construct a high-resolution histogram for the output distribution. This allows me to understand and sample the distribution known logarithms d. The distribution varies very little in d (unless d is divisible by a large power of two). This allows me to draw conclusion about how our post-processing algorithm would perform for random d. $\endgroup$ Sep 19 at 12:08
  • 1
    $\begingroup$ I only now realized that edits are only allowed for 5 mins, so here comes a second reply to @Cloudwin.ZL, in the interest of perhaps being a bit more clear: 1. The histogram for the distribution, when tabulated in log(alpha), varies little in the logarithm d (for d is an m bit integer, and not a very large power of two, etc.). 2. It is essentially the size of alpha that determines how hard it is to solve for d in the classical post-processing. 3. Feel free to send me an e-mail if you still feel confused. $\endgroup$ Sep 19 at 13:00
  • $\begingroup$ I believe the similarity of probility distrbitions between different d is the missing key for my understanding. Really appreciate your reply. $\endgroup$ Sep 21 at 17:26

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.