<table><caption>Table 12: Summary of the values for the Jensen's gap $2^z$ at crossover points of our combined classical-quantum enumeration attacks against Kyber and the quasi-square root speed up $\sqrt{\#T \cdot h}$. We remark that exact crossovers happen at fractional values of $z$. In this table we round down threshold values of $z$. MAXDEPTH is abbreviated to MD. The results are estimated from the bounds $C = 1$, DF($W$) = 1, QD($W$) = 1, $b = 1/64$.</caption><thead><tr><th rowspan="2">MD</th><th rowspan="2">Kyber</th><th colspan="6">less likely to be feasible</th><th colspan="6">more likely to be feasible</th></tr><tr><th colspan="6">Crossover points when comparing quasi-square-root against the total GCOST (cf. Table 6) with ...<br>...W as in Section 4.1</th><th colspan="6">...W as in Section 4.2</th></tr><tr><th></th><th></th><th>LB/UB</th><th>UB/UB</th><th>LB/LB</th><th>LB/UB</th><th>UB/UB</th><th>LB/LB</th><th>LB/UB</th><th>UB/UB</th><th>LB/LB</th><th>LB/UB</th><th>UB/UB</th><th>LB/LB</th></tr></thead><tbody><tr><td rowspan="3">2<sup>40</sup></td><td>-512</td><td>z &ge; 0, k &le; 25<br>Cost &ge; 2<sup>74</sup></td><td>z &ge; 35, k &le; 11<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 31, k &le; 59<br>Cost &ge; 2<sup>89</sup></td><td>z &ge; 8, k &le; 24<br>Cost &ge; 2<sup>90</sup></td><td>z &ge; 51, k &le; 12<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 47, k &le; 63<br>Cost &ge; 2<sup>89</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-768</td><td>z &ge; 14, k &le; 75<br>Cost &ge; 2<sup>166</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &ge; 31, k &le; 67<br>Cost &ge; 2<sup>164</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-1024</td><td>z &ge; 47, k &le; 115<br>Cost &ge; 2<sup>261</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &ge; 63, k &le; 105<br>Cost &ge; 2<sup>262</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">2<sup>64</sup></td><td>-512</td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>63</sup></td><td>z &ge; 23, k &le; 11<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 19, k &le; 59<br>Cost &ge; 2<sup>89</sup></td><td>z &ge; 0, k &le; 24<br>Cost &ge; 2<sup>82</sup></td><td>z &ge; 39, k &le; 5<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 35, k &le; 54<br>Cost &ge; 2<sup>89</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-768</td><td>z &ge; 2, k &le; 64<br>Cost &ge; 2<sup>165</sup></td><td>z &ge; 60, k &le; 33<br>Cost &ge; 2<sup>170</sup></td><td>z &ge; 57, k &le; 77<br>Cost &ge; 2<sup>165</sup></td><td>z &ge; 19, k &le; 67<br>Cost &ge; 2<sup>164</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-1024</td><td>z &ge; 34, k &le; 105<br>Cost &ge; 2<sup>262</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &ge; 51, k &le; 100<br>Cost &ge; 2<sup>262</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="3">2<sup>96</sup></td><td>-512</td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>63</sup></td><td>z &ge; 7, k &le; 2<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 5, k &le; 40<br>Cost &ge; 2<sup>90</sup></td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>81</sup></td><td>z &ge; 30, k &le; 1<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 30, k &le; 40<br>Cost &ge; 2<sup>89</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-768</td><td>z &ge; 0, k &le; 61<br>Cost &ge; 2<sup>137</sup></td><td>z &ge; 44, k &le; 12<br>Cost &ge; 2<sup>170</sup></td><td>z &ge; 41, k &le; 77<br>Cost &ge; 2<sup>165</sup></td><td>z &ge; 3, k &le; 67<br>Cost &ge; 2<sup>164</sup></td><td>z &ge; 60, k &le; 12<br>Cost &ge; 2<sup>171</sup></td><td>z &ge; 58, k &le; 62<br>Cost &ge; 2<sup>164</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-1024</td><td>z &ge; 18, k &le; 100<br>Cost &ge; 2<sup>262</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &ge; 35, k &le; 100<br>Cost &ge; 2<sup>262</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td rowspan="4">&infin;</td><td>-512</td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>63</sup></td><td>z &ge; 6, k &le; 1<br>Cost &ge; 2<sup>97</sup></td><td>z &ge; 5, k &le; 40<br>Cost &ge; 2<sup>90</sup></td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>81</sup></td><td>z &ge; 30, k &le; 1<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 30, k &le; 40<br>Cost &ge; 2<sup>89</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-768</td><td>z &ge; 0, k &le; 37<br>Cost &ge; 2<sup>119</sup></td><td>z &ge; 8, k &le; 3<br>Cost &ge; 2<sup>171</sup></td><td>z &ge; 5, k &le; 31<br>Cost &ge; 2<sup>166</sup></td><td>z &ge; 0, k &le; 37<br>Cost &ge; 2<sup>144</sup></td><td>z &ge; 34, k &le; 3<br>Cost &ge; 2<sup>170</sup></td><td>z &ge; 31, k &le; 31<br>Cost &ge; 2<sup>165</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>-1024</td><td>z &ge; 0, k &le; 33<br>Cost &ge; 2<sup>212</sup></td><td>z &ge; 8, k &le; 3<br>Cost &ge; 2<sup>269</sup></td><td>z &ge; 5, k &le; 1<br>Cost &ge; 2<sup>263</sup></td><td>z &ge; 0, k &le; 33<br>Cost &ge; 2<sup>238</sup></td><td>z &ge; 35, k &le; 3<br>Cost &ge; 2<sup>268</sup></td><td>z &ge; 32, k &le; 11<br>Cost &ge; 2<sup>263</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td>&infin;<sub>k=0</sub></td><td>-512</td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>89</sup></td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>97</sup></td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>89</sup></td><td>z &ge; 30, k = 0<br>Cost &ge; 2<sup>90</sup></td><td>z &ge; 30, k = 0<br>Cost &ge; 2<sup>98</sup></td><td>z &ge; 30, k = 0<br>Cost &ge; 2<sup>90</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>-768</td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>165</sup></td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>170</sup></td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>165</sup></td><td>z &ge; 31, k = 0<br>Cost &ge; 2<sup>165</sup></td><td>z &ge; 31, k = 0<br>Cost &ge; 2<sup>171</sup></td><td>z &ge; 31, k = 0<br>Cost &ge; 2<sup>165</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr><tr><td></td><td>-1024</td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>262</sup></td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>268</sup></td><td>z &ge; 6, k = 0<br>Cost &ge; 2<sup>262</sup></td><td>z &ge; 32, k = 0<br>Cost &ge; 2<sup>263</sup></td><td>z &ge; 32, k = 0<br>Cost &ge; 2<sup>269</sup></td><td>z &ge; 32, k = 0<br>Cost &ge; 2<sup>263</sup></td><td></td><td></td><td></td><td></td><td></td><td></td></tr></tbody></table>
<table><caption>Table 13: Summary of the values for the Jensen's gap $2^z$ at crossover points of our combined classical-quantum enumeration attacks against Kyber and the canonical 128, 192, 256 bit security respectively. We remark that exact crossovers happen at fractional values of $z$. In this table we round down threshold values of $z$. MAXDEPTH is abbreviated to MD. Cost is as in Table 6. The results are estimated from the bounds $C = 1$, DF($W$) = 1, QD($W$) = 1, $b = 1/64$.</caption><thead><tr><th rowspan="2">MD</th><th rowspan="2">Kyber</th><th colspan="3">less likely to be feasible</th><th colspan="3">more likely to be feasible</th></tr><tr><th>LB/UB</th><th>UB/UB</th><th>LB/LB</th><th>LB/UB</th><th>UB/UB</th><th>LB/LB</th></tr></thead><tbody><tr><td rowspan="4">2<sup>40</sup></td><td>-512</td><td>z &ge; 0, k &le; 25<br>Cost &ge; 2<sup>74</sup></td><td>z &ge; 21, k &le; 28<br>Cost &ge; 2<sup>126</sup></td><td>z &ge; 12, k &le; 92<br>Cost &ge; 2<sup>127</sup></td><td>z &ge; 0, k &le; 39<br>Cost &ge; 2<sup>110</sup></td><td>z &ge; 36, k &le; 24<br>Cost &ge; 2<sup>127</sup></td><td>z &ge; 28, k &le; 96<br>Cost &ge; 2<sup>126</sup></td></tr><tr><td>-768</td><td>z &ge; 3, k &le; 92<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 62, k &le; 33<br>Cost &ge; 2<sup>190</sup></td><td>z &ge; 56, k &le; 114<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 18, k &le; 80<br>Cost &ge; 2<sup>191</sup></td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &gt; 64</td></tr><tr><td>-1024</td><td>z &ge; 50, k &le; 112<br>Cost &ge; 2<sup>255</sup></td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &gt; 64</td></tr><tr><td>-1024</td><td>z &ge; 38, k &le; 100<br>Cost &ge; 2<sup>254</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &gt; 64</td></tr><tr><td rowspan="4">2<sup>64</sup></td><td>-512</td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>63</sup></td><td>z &ge; 9, k &le; 28<br>Cost &ge; 2<sup>126</sup></td><td>z &ge; 0, k &le; 92<br>Cost &ge; 2<sup>127</sup></td><td>z &ge; 0, k &le; 24<br>Cost &ge; 2<sup>82</sup></td><td>z &ge; 24, k &le; 24<br>Cost &ge; 2<sup>127</sup></td><td>z &ge; 16, k &le; 79<br>Cost &ge; 2<sup>127</sup></td></tr><tr><td>-768</td><td>z &ge; 0, k &le; 64<br>Cost &ge; 2<sup>169</sup></td><td>z &ge; 50, k &le; 33<br>Cost &ge; 2<sup>190</sup></td><td>z &ge; 44, k &le; 114<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 6, k &le; 67<br>Cost &ge; 2<sup>190</sup></td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &ge; 60, k &le; 106<br>Cost &ge; 2<sup>191</sup></td></tr><tr><td>-1024</td><td>z &ge; 22, k &le; 100<br>Cost &ge; 2<sup>254</sup></td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &gt; 64</td><td>z &ge; 55, k &le; 100<br>Cost &ge; 2<sup>254</sup></td></tr><tr><td>-1024</td><td>z &ge; 22, k &le; 100<br>Cost &ge; 2<sup>254</sup></td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &gt; 64</td><td>z &gt; 64</td></tr><tr><td rowspan="4">2<sup>96</sup></td><td>-512</td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>63</sup></td><td>z &ge; 0, k &le; 4<br>Cost &ge; 2<sup>112</sup></td><td>z &ge; 0, k &le; 40<br>Cost &ge; 2<sup>96</sup></td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>81</sup></td><td>z &ge; 9, k &le; 5<br>Cost &ge; 2<sup>126</sup></td><td>z &ge; 0, k &le; 58<br>Cost &ge; 2<sup>127</sup></td></tr><tr><td>-768</td><td>z &ge; 0, k &le; 61<br>Cost &ge; 2<sup>137</sup></td><td>z &ge; 34, k &le; 33<br>Cost &ge; 2<sup>190</sup></td><td>z &ge; 28, k &le; 77<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 0, k &le; 67<br>Cost &ge; 2<sup>170</sup></td><td>z &ge; 50, k &le; 26<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 45, k &le; 77<br>Cost &ge; 2<sup>190</sup></td></tr><tr><td>-1024</td><td>z &ge; 22, k &le; 100<br>Cost &ge; 2<sup>254</sup></td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &gt; 64</td><td>z &ge; 39, k &le; 100<br>Cost &ge; 2<sup>254</sup></td><td rowspan="2">z &gt; 64</td><td rowspan="2">z &gt; 64</td></tr><tr><td>-1024</td><td>z &ge; 22, k &le; 100<br>Cost &ge; 2<sup>254</sup></td><td>z &ge; 13, k &le; 1<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 13, k &le; 1<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 13, k &le; 1<br>Cost &ge; 2<sup>255</sup></td></tr><tr><td rowspan="4">&infin;</td><td>-512</td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>63</sup></td><td>z &ge; 0, k &le; 1<br>Cost &ge; 2<sup>103</sup></td><td>z &ge; 0, k &le; 40<br>Cost &ge; 2<sup>95</sup></td><td>z &ge; 0, k &le; 26<br>Cost &ge; 2<sup>81</sup></td><td>z &ge; 1, k &le; 1<br>Cost &ge; 2<sup>127</sup></td><td>z &ge; 0, k &le; 40<br>Cost &ge; 2<sup>119</sup></td></tr><tr><td>-768</td><td>z &ge; 0, k &le; 37<br>Cost &ge; 2<sup>119</sup></td><td>z &ge; 0, k &le; 3<br>Cost &ge; 2<sup>179</sup></td><td>z &ge; 0, k &le; 31<br>Cost &ge; 2<sup>171</sup></td><td>z &ge; 0, k &le; 37<br>Cost &ge; 2<sup>144</sup></td><td>z &ge; 13, k &le; 3<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 5, k &le; 31<br>Cost &ge; 2<sup>191</sup></td></tr><tr><td>-1024</td><td>z &ge; 0, k &le; 33<br>Cost &ge; 2<sup>212</sup></td><td>z &ge; 22, k &le; 3<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 13, k &le; 1<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 0, k &le; 33<br>Cost &ge; 2<sup>238</sup></td><td>z &ge; 48, k &le; 3<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 40, k &le; 11<br>Cost &ge; 2<sup>255</sup></td></tr><tr><td>-1024</td><td>z &ge; 13, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 19, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 13, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>120</sup></td><td>z &ge; 1, k &le; 0<br>Cost &ge; 2<sup>127</sup></td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>120</sup></td></tr><tr><td rowspan="3">&infin;<sub>k=0</sub></td><td>-512</td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>95</sup></td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>103</sup></td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>95</sup></td><td>z &ge; 5, k &le; 0<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 11, k &le; 0<br>Cost &ge; 2<sup>191</sup></td><td>z &ge; 5, k &le; 0<br>Cost &ge; 2<sup>191</sup></td></tr><tr><td>-768</td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>171</sup></td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>176</sup></td><td>z &ge; 0, k &le; 0<br>Cost &ge; 2<sup>171</sup></td><td>z &ge; 40, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 46, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 40, k &le; 0<br>Cost &ge; 2<sup>255</sup></td></tr><tr><td>-1024</td><td>z &ge; 13, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 19, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 13, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 40, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 46, k &le; 0<br>Cost &ge; 2<sup>255</sup></td><td>z &ge; 40, k &le; 0<br>Cost &ge; 2<sup>255</sup></td></tr></tbody></table>
# I Lower-Bounding Additive and Multiplicative Jensen's Gaps

Let $X$ be the random variable for $\#T$ with support $\text{supp}(X) \subset [1, +\infty)$, $\mu = \mathbb{E}[X] < \infty$, $\sigma^2 = \mathbb{V}[X] < \infty$. In this section, we explore two different derivations for lower bounds of the additive $(\sqrt{\mathbb{E}[X]} - \mathbb{E}[\sqrt{X}])$ and multiplicative $(\sqrt{\mathbb{E}[X]}/\mathbb{E}[\sqrt{X}])$ Jensen's gaps of $X$. As part of our derivations, we will use the notion of Hölder continuity, which we recall next.

**Definition 2 (Hölder continuity).** A real function $f: \mathbb{R} \to \mathbb{R}$ is $\alpha$-Hölder continuous over an interval $(a, b) \subset \mathbb{R}$ if for any $x, y \in (a, b)$, there exists $M > 0$ such that $|f(x) - f(y)| \le M \cdot |x - y|^\alpha$.

## I.1 Bounding the Additive Jensen's Gap

To lower bound the additive gap, we start by proving that the square root function $\sqrt{x}$ is $\frac{1}{2}$-Hölder continuous.

**Lemma 2.** $\sqrt{x}$ is $\frac{1}{2}$-Hölder continuous over $(0, \infty)$ with $M \ge 1$.

*Proof.* Let $x, y \ge 0$. First we write

$$|\sqrt{x} - \sqrt{y}| = \frac{|\sqrt{x} - \sqrt{y}| \cdot |\sqrt{x} + \sqrt{y}|}{|\sqrt{x} + \sqrt{y}|} = \frac{|x - y|}{\sqrt{x} + \sqrt{y}} = \sqrt{|x - y|} \cdot \frac{\sqrt{|x - y|}}{\sqrt{x} + \sqrt{y}}.$$

Now, we note that $|x - y| \le |x| + |y| = x + y \le x + y + 2\sqrt{xy} = (\sqrt{x} + \sqrt{y})^2$. Since $\sqrt{x}$ is strictly increasing over $(0, \infty)$, it holds that

$$|x - y| \le (\sqrt{x} + \sqrt{y})^2 \iff \sqrt{|x - y|} \le \sqrt{x} + \sqrt{y}. \iff \frac{\sqrt{|x - y|}}{\sqrt{x} + \sqrt{y}} \le 1.$$

Hence, $|\sqrt{x} - \sqrt{y}| = \sqrt{|x - y|} \cdot \frac{\sqrt{|x - y|}}{\sqrt{x} + \sqrt{y}} \le \sqrt{|x - y|}$, which concludes the proof. $\square$

**Lemma 3.** The additive Jensen's gap of $X$ is in absolute value $|\mathbb{E}[\sqrt{X}] - \sqrt{\mu}| \le \sqrt{\sigma}$.

*Proof.* Following [35, Eq 1.1], it holds that

$$ \begin{aligned} |\mathbb{E}[\sqrt{X}] - \sqrt{\mu}| &= \left| \sum_{x \in \text{supp}(X)} \left[ \sqrt{x} \Pr[X = x] \right] - \sqrt{\mu} \right| \\ &= \left| \sum_{x \in \text{supp}(X)} (\sqrt{x} - \sqrt{\mu}) \Pr[X = x] \right| && (\text{by } \sum_{x \in \text{supp}(X)} \Pr[X = x] = 1) \\ &\le \sum_{x \in \text{supp}(X)} |\sqrt{x} - \sqrt{\mu}| \Pr[X = x] \end{aligned} $$
$$ \leq \sum_{x \in \text{supp}(X)} \sqrt{|x - \mu|} \Pr[X = x] \qquad (\text{by Lemma 2}) $$

$$ = \mathbb{E}[\sqrt{|x - \mu|}] \qquad (\text{by definition of } \mathbb{E}) $$

$$ \leq \sqrt{\mathbb{E}[|x - \mu|]} \qquad (\text{by Jensen's inequality}) $$

$$ \leq \mathbb{E}[(x - \mu)^2]^{1/4} \qquad (\text{by Jensen's inequality}) $$

$$ = \sqrt{\sigma}. \qquad (\text{by definition of } \sigma) $$

This concludes the proof. □

From this the following bound on $\mathbb{E}[\text{GCOST}(\text{QPE}(\mathcal{W}))]$ can be derived.

**Lemma 4.** $\mathbb{E}[\text{GCOST}(\text{QPE}(\mathcal{W}))] \geq \sqrt{h}(\sqrt{\mu} - \sqrt{\sigma}) \cdot \text{GCOST}(\mathcal{W})$, where $h$ is the height of $\mathcal{T}$.

*Proof.* From Lemma 3, it holds that

$$ \begin{aligned} |\mathbb{E}[\sqrt{X}] - \sqrt{\mu}| \leq \sqrt{\sigma} &\iff -\sqrt{\sigma} \leq \mathbb{E}[\sqrt{X}] - \sqrt{\mu} \leq \sqrt{\sigma} \\ &\iff \mathbb{E}[\sqrt{X}] \geq \sqrt{\mu} - \sqrt{\sigma}. \end{aligned} $$

Since it holds that

$$ \text{GCOST}(\text{QPE}(\mathcal{W})) = \text{WQ}(\mathcal{T}, \mathcal{W}) \cdot \text{GCOST}(\mathcal{W}), $$

and under Conjecture 1, letting $X = \#\mathcal{T}$, the statement follows. □

## I.2 Bounding the Multiplicative Jensen's Gap

We start by proving that the natural logarithm function $\ln(x)$ is $\frac{1}{2}$-Hölder continuous and that $\ln \sqrt{x}$ is $\frac{1}{2}$-Hölder continuous.

**Lemma 5.** $\ln(x)$ is $\frac{1}{2}$-Hölder continuous over $[1, \infty)$ with $M \geq 1$.

*Proof.* Let $p = 2$. We note that $\frac{d}{dx} \ln x = \frac{1}{x}$, and that $x, y \geq 1$. Then

$$ \begin{aligned} |\ln x - \ln y| &= \left|\int_x^y \frac{dt}{t}\right| \leq \int_{\min(x,y)}^{\max(x,y)} \left|\frac{1}{t}\right| dt \\ &\leq \left(\int_{\min(x,y)}^{\max(x,y)} 1^2 dt\right)^{1/2} \left(\int_{\min(x,y)}^{\max(x,y)} \left|\frac{1}{t}\right|^2 dt\right)^{1/2} \quad (\text{by Hölder's inequality}) \\ &= |y - x|^{1/2} \left(\int_{\min(x,y)}^{\max(x,y)} \frac{1}{t^2} dt\right)^{1/2} \\ &\leq |y - x|^{1/2} \left(\int_1^\infty \frac{1}{t^2} dt\right)^{1/2} \leq |y - x|^{1/2} \cdot \left[-\frac{1}{x}\right]_1^\infty = |y - x|^{1/2}. \end{aligned} $$

□
**Lemma 6.** $\ln \sqrt{x}$ is $\frac{1}{2}$-Hölder continuous over $[1, \infty)$ with $M \ge 1/2$.

*Proof.* The statement follows immediately as

$$|\ln \sqrt{x} - \ln \sqrt{y}| = \frac{1}{2} |\ln x - \ln y| \le \frac{1}{2} |x - y|^{1/2},$$

where the second inequality follows from Lemma 5. □

**Lemma 7.** Given a multiplicative Jensen's gap $2^z$ such that $E[\sqrt{x}] = 2^{-z} \sqrt{E[x]}$, then $z \le \frac{1}{2 \ln 2} \sqrt{\sigma}$.

*Proof.* First, we take logarithms, i.e.,

$$E[\sqrt{x}] = 2^{-z} \sqrt{E[x]} \iff \ln E[\sqrt{x}] = -z \ln 2 + \ln \sqrt{\mu}.$$

Then we upper bound $z$ as

$$
\begin{align*}
z &= \frac{1}{\ln 2} (\ln \sqrt{\mu} - \ln \mathbb{E}[\sqrt{x}]) \\
  &\le \frac{1}{\ln 2} (\ln \sqrt{\mu} - \mathbb{E}[\ln \sqrt{x}]) && (\text{by Jensen's inequality, } \mathbb{E} \ln \le \ln \mathbb{E}) \\
  &= \frac{1}{\ln 2} \sum_{\text{supp}(X)} (\ln \sqrt{\mu} - \ln \sqrt{x}) \Pr[X = x] \\
  &\le \frac{1}{\ln 2} \sum_{\text{supp}(X)} |\ln \sqrt{\mu} - \ln \sqrt{x}| \Pr[X = x] \\
  &\le \frac{1}{\ln 2} \sum_{\text{supp}(X)} \frac{1}{2} |\mu - x|^{1/2} \Pr[X = x] && (\text{by Lemma 6}) \\
  &= \frac{1}{2 \ln 2} \mathbb{E}[|\mu - x|^{1/2}] && (\text{by definition of } \mathbb{E}) \\
  &\le \frac{1}{2 \ln 2} \mathbb{E}[(x - \mu)^2]^{1/4} = \frac{1}{2 \ln 2} \sqrt{\sigma} && (\text{by applying Jensen's inequality twice})
\end{align*}
\hfill \square
$$

We can conclude with the following bound on $\mathbb{E}[\text{GCOST}(\text{QPE}(\mathcal{W}))]$.

**Lemma 8.** $\mathbb{E}[\text{GCOST}(\text{QPE}(\mathcal{W}))] \ge 2^{-\frac{1}{2\ln 2}\sigma} \sqrt{\mu \cdot h} \cdot \text{GCOST}(\mathcal{W})$, where $h$ is the height of $\mathcal{T}$.

*Proof.* Using Lemma 7, it holds that

$$\mathbb{E}[\sqrt{X}] = 2^{-z} \sqrt{\mu} \ge 2^{-\frac{1}{2\ln 2} \sqrt{\sigma}} \sqrt{\mu}.$$

Combined with

$$\text{GCOST}(\text{QPE}(\mathcal{W})) = \text{WQ}(\mathcal{T}, \mathcal{W}) \cdot \text{GCOST}(\mathcal{W}),$$

and under Conjecture 1, letting $X = \#\mathcal{T}$ concludes the proof. □
### I.3 Experimentally Estimating $\sqrt{\sigma}$

Unfortunately, we are not aware of any techniques to estimate the variance of $\#\mathcal{T}(g)$ for an element $g \in Z_k$ of a pruned enumeration tree. Therefore, we have implemented an extension to the experiments from Appendix D originally used to experimentally measure some multiplicative Jensen's gaps. This extension lets us measure the unbiased sample variance $s^2$ of the number of nodes $\#\mathcal{T}(g)$. Using $s^2$ as an estimate for the variance $\sigma^2$ of the distribution, we then plot $\sqrt[4]{s^2}$ as an estimate for $\sqrt{\sigma}$ in Figs. 27 and 28.

Our results seem to indicate that $\sqrt{\sigma}$ increases with the dimension of the tree $\beta$ and with the height of the subtree $\beta - k$, suggesting that deeper subtrees are more exposed to variations in their size compared to shallower trees. The value of the measured estimates $\sqrt[4]{s^2}$ seems also to stay relatively low (in absolute value) in our experiments, peaking at around 20. In any case, these experiments are no more or less conclusive than those in Appendix D, and hence this analysis does not seem to significantly improve on the methodology used in Section 5.2 for estimating the cost of the attack, that is testing multiple values of possible Jensen's gaps.
<figure><img src="image_87.png" /><figcaption>(a) $n = 72$ (cf. Table 7), block size $\beta = 50$, 10<sup>th</sup> tour, $k = 20$.</figcaption></figure>

<figure><img src="image_88.png" /><figcaption>(b) $n = 72$ (cf. Table 7), block size $\beta = 60$, 10<sup>th</sup> tour, $k = 20$.</figcaption></figure>

<figure><img src="image_89.png" /><figcaption>(c) $n = 72$ (cf. Table 7), block size $\beta = 70$, 10<sup>th</sup> tour, $k = 20$.</figcaption></figure>

Figure 27: Measurement on the Jensen’s gap of subtrees of height $h = \beta - k$ rooted on level $k$ in pruned enumeration experiments. The height $h$ is reduced in the last few blocks of the basis of dimension smaller than $\beta$. As the block index $i$ increases, we plot the measurements done during enumeration of the projective sublattice $\pi_i(\text{span}_Z(b_i, \dots, b_{i+\beta}))$. Blue dots are the squared root of the average, green dots are the average of the squared root, black dots are the fourth root of the unbiased sample variance.
<figure><img src="image_90.png" /><figcaption>(a) $n = 72$ (cf. Table 7), block size $\beta = 50$, 10<sup>th</sup> tour, $k = 30$.</figcaption></figure>

<figure><img src="image_91.png" /><figcaption>(b) $n = 72$ (cf. Table 7), block size $\beta = 60$, 10<sup>th</sup> tour, $k = 30$.</figcaption></figure>

<figure><img src="image_92.png" /><figcaption>(c) $n = 72$ (cf. Table 7), block size $\beta = 70$, 10<sup>th</sup> tour, $k = 30$.</figcaption></figure>

Figure 28: Continuation of Fig. 27.