Question about the Result Analysis of Ekera's Method in Short DLP

Question

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?

Answer 1

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.