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

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.