queries to $\mathcal{H}_e$, we have that $e_i = e'_i$ for all $i \neq i^+$. Then, since $\text{sig}_{\text{agg}}$ and $\text{sig}'_{\text{agg}}$ both verify, by definition of the reconstructed vectors $\mathbf{v}_{1,1}, \mathbf{v}'_{1,1}$ in Algorithm C.7 and $\mathbf{v}_1, \mathbf{v}'_1$, we have

$$ \mathbf{A}\mathbf{v}_1 + \sum_{i \in [N]} e_i(\mathbf{G} - \mathbf{B}_i)\mathbf{v}_{2,i} = \sum_{i \in [N]} e_i\mathcal{H}(\mathbf{m}_i) \mod qR $$

$$ \mathbf{A}\mathbf{v}'_1 + \sum_{i \in [N]} e'_i(\mathbf{G} - \mathbf{B}'_i)\mathbf{v}'_{2,i} = \sum_{i \in [N]} e'_i\mathcal{H}(\mathbf{m}'_i) \mod qR, $$

such that $\|\mathbf{v}_1\|_2, \|\mathbf{v}'_1\|_2 \le ws\sqrt{N \cdot 2nd}$. We call $\Delta e = e_{i+} - e'_{i+}$. With the prior observations, combining the above equations gives

$$ \mathbf{A}(\mathbf{v}_1 - \mathbf{v}'_1) + \Delta e \cdot (\mathbf{G} - \mathbf{B})\mathbf{v}_{2,i+} = \Delta e \cdot \mathcal{H}(\mathbf{m}_{i+}) \mod qR $$

We note that $\mathbf{m}_{i+}$ was not queried for a signature, but it must have been queried to $\mathcal{H}$ (otherwise $\mathcal{A}$ would have had a negligible advantage to begin with). Hence, $\mathcal{T}_s$ contains an entry $(\mathbf{m}_{i+}, \mathbf{v}'')$ where $\mathbf{v}''$ was generated as in game $G_2$. Then, $\mathbf{v}''$ verifies $\mathbf{A}\mathbf{v}''_1 + (\mathbf{G} - \mathbf{B})\mathbf{v}''_2 = \mathcal{H}(\mathbf{m}_{i+}) \mod qR$. We then obtain

$$ \mathbf{A}(\mathbf{v}_1 - \mathbf{v}'_1 - \Delta e \cdot \mathbf{v}''_1) + \Delta e \cdot (\mathbf{G} - \mathbf{B})(\mathbf{v}_{2,i+} - \mathbf{v}''_2) = \mathbf{0} \mod qR, $$

which can be written $\bar{\mathbf{A}}\mathbf{x} = \mathbf{0} \mod qR$ for

$$ \mathbf{x} = \begin{bmatrix} \mathbf{v}_1 - \mathbf{v}'_1 \\ \Delta e \cdot \mathbf{v}_{2,i+} \end{bmatrix} - \Delta e \cdot \mathbf{v}'' \in \mathbb{R}^{d(2+k)}. $$

The adversary $\mathcal{A}$ does not know $\mathbf{v}''$ but only $\bar{\mathbf{A}}\mathbf{v}''$ mod $qR$ which takes $2^{nd \log_2 q}$ possible values. By [DORS08, Lem. 2.2], the entropy of $\mathbf{v}''$ given $\bar{\mathbf{A}}\mathbf{v}''$ mod $qR$ is at least $H_\infty(\mathbf{v}'') - nd \log_2 q$. Since $\mathbf{v}''$ is sampled by the simulator, it holds that $\mathbf{v}''_1 \sim \mathcal{D}_{R^{2d},s}$ and $\mathbf{v}''_2 \sim \mathbf{G}^{-1}(U(R_q^d))$. As a result, $H_\infty(\mathbf{v}'') = H_\infty(\mathcal{D}_{R^{2d},s}) + nd \log_2 q$. Then, by Lemma C.1, we have that $H_\infty(\mathcal{D}_{R^{2d},s}) \ge 2nd \log_2 s - 1$ as $s \ge \eta_\delta(\mathbb{Z}^{2nd})$ for some negligible $\delta > 0$. We thus obtain that the entropy of $\mathbf{v}''$ given $\bar{\mathbf{A}}\mathbf{v}''$ mod $qR$ is at least $2nd \log_2 s - 1 \gg 4\lambda$, and then that $\mathbf{x} = \mathbf{0}$ only with negligible probability. Finally, we have

$$ \begin{aligned} \|\mathbf{x}\|_2 &\le \sqrt{(\|\mathbf{v}_1\|_2 + \|\mathbf{v}'_1\|_2 + \|\Delta e\|_1 \|\mathbf{v}''_1\|_2)^2 + (\|\Delta e\|_1 \cdot (\|\mathbf{v}_{2,i+}\|_2 + \|\mathbf{v}''_2\|_2))^2} \\ &\le \sqrt{(2w \cdot (\sqrt{N} + 1) \cdot c's\sqrt{2nd})^2 + (2w \cdot 2(b-1)\sqrt{ndk})^2} \\ &= \beta, \end{aligned} $$

except with probability $2^{-4\lambda}$ that is due to Lemma 2.1 and the definition of $c'$. Therefore, $\mathbf{x}$ is a solution to M-SIS$_{n,d,d(2+k),q,\beta}$ except with negligible probability. Since we assumed that the hardness bound of the latter was $\varepsilon_{\text{M-SIS}}$, it thus hold that

$$ \text{frk} \le \varepsilon_{\text{M-SIS}} + \text{negl}(4\lambda) \qquad (8) $$
Combining Equation (8) with the result from the general forking lemma, we get

$$p_2 = \text{acc} \le \frac{Q_e}{|C|} + \sqrt{Q_e(\varepsilon_{\text{M-SIS}} + \text{negl}(4\lambda))}.$$

We can assume without loss of generality that $Q_e \le 2^\lambda$, and recalling that $C$ is chosen so that $|C| \ge 2^{2^\lambda}$, it holds $Q_e/|C| = \text{negl}(\lambda)$. Combined with Equations (5), (6), and (7), we get

$$\text{Adv}[\mathcal{A}] \le \frac{N}{(1 - 1/Q)^Q} \cdot \left( \varepsilon_{\text{M-LWE}} + \frac{Q_e}{|C|} + \sqrt{Q_e \varepsilon_{\text{M-SIS}}} \right) + \text{negl}(\lambda),$$

as claimed. When $\varepsilon_{\text{M-LWE}}$ and $\varepsilon_{\text{M-SIS}}$ are negligible in $\lambda$ and $3\lambda$ respectively, the bound is indeed negligible as $\frac{N}{(1-1/Q)^Q} \le 4N = \text{poly}(\lambda)$ whenever $Q \ge 2$. $\square$

## C.5 Performance Evaluation

We now evaluate the performance of our aggregate signature compared to the naive concatenation. For that we define the compression rate as

$$\text{compression rate} = \max \left( 0, 100 \cdot \left( 1 - \frac{|\text{sig}_{\text{agg}}|}{|\text{concatenation}|} \right) \right) \%.$$

However, to obtain a fair comparison, we cannot simply compare the concatenation of signatures produced by Algorithm C.4 with the aggregate signature output by Algorithm C.6. Indeed, in the case of a mere concatenation, the parameters used in Algorithm C.4 would not be optimal, one would instead use those for single GPV signatures, as described in Section 4. We thus compare below the size of an aggregate signature with the concatenation of signatures generated with better parameters, tailored to the single signature use-case. Concretely, although we use the same ring $R = \mathbb{Z}[x]/\langle x^n + 1 \rangle$, where $n = 256$, we select the optimal parameters from Table 4.3, that is $q \approx 2^{22.5}$, $d = 6$, $b = 2$, $s \approx 362140$ for single signatures, leading to signature size of $|\text{sig}_{\text{LW}*}| = 64461$ bits $\approx 7.87$ KB. Hence, the concatenation of $N$ signatures results in a naive aggregate signature of $|\text{concatenation}| = N \cdot |\text{sig}_{\text{LW}*}| = N \cdot 64461$ bits.

We estimate the aggregate signature size for different values of $N$ ranging from $N = 10$ to $N = 2000$. The bit-size of the aggregate signature is given by

$$|\text{sig}_{\text{agg}}| = nd(1/2 + \log_2(\text{ws}\sqrt{N})) + N \cdot nd[\log_2 q].$$

The parameters of our scheme are set according to Setup (Algorithm C.2) with $Q = 2^{40}$, where $q, d$ and $b$ are selected to guarantee sufficient security for the underlying M-SIS$_{n,d,d(2+k),q,\beta}$ and M-LWE$_{n,d,d,q,U(S_1)}^{dk}$ problems aiming for $\lambda = 128$ using the methodology from Section A, while minimizing the aggregate signature size. Since the parameters increase with $N$ (typically the bound $\beta$), the values of $q$ and $d$ will naturally depend on $N$ accordingly. Hence, when $N$ increases the modulus $q$ and rank $d$ need to be increased to preserve the security of the
scheme, which results in lower compression rates. The higher $N$ gets, the more we would have to increase $q$ and $d$, and we thus expect that passed a certain threshold $N$ the concatenation would become better than our aggregate signature. Nevertheless, in practical use cases of aggregate signatures the number of signers stays in the low hundreds which in our case offer up to 10% compression rate compared to the naive concatenation, as shown in Table C.1.

<table><caption>**Table C.1.** Comparison estimates of our aggregate signature and the concatenation of LW signatures over module lattices. Sizes of $N \cdot |\text{sig}_{\text{LW}^*}|$ and $|\text{sig}_{\text{agg}}|$ are expressed in KB. All the parameters are chosen for an M-SIS and M-LWE security of at least $\lambda = 128$ bits in the Core-SVP model.</caption><thead><tr><th>$N$</th><th>5</th><th>10</th><th>50</th><th>100</th><th>500</th><th>1000</th><th>2000</th></tr></thead><tbody><tr><td>$N \cdot |\text{sig}_{\text{LW}^*}|$<br>$(d, q)$</td><td>39.3<br>(6, 2<sup>22.5</sup>)</td><td>78.7<br>(6, 2<sup>22.5</sup>)</td><td>393.4<br>(6, 2<sup>22.5</sup>)</td><td>786.9<br>(6, 2<sup>22.5</sup>)</td><td>3934.4<br>(6, 2<sup>22.5</sup>)</td><td>7868.8<br>(6, 2<sup>22.5</sup>)</td><td>15737.6<br>(6, 2<sup>22.5</sup>)</td></tr><tr><td>$|\text{sig}_{\text{agg}}|$<br>$(d, q)$</td><td>38.5<br>(7, 2<sup>29.7</sup>)</td><td>71.4<br>(7, 2<sup>30</sup>)</td><td>345.1<br>(7, 2<sup>30.99</sup>)</td><td>706.1<br>(7, 2<sup>31.6</sup>)</td><td>3615.8<br>(7, 2<sup>32.7</sup>)</td><td>7444.0<br>(7, 2<sup>33.6</sup>)</td><td>15319.1<br>(7, 2<sup>34.99</sup>)</td></tr><tr><td>Comp. Rate</td><td>2.26%</td><td>9.29%</td><td>12.29%</td><td>10.26%</td><td>8.10%</td><td>5.39%</td><td>2.66%</td></tr></tbody></table>