the size of the quadratic constraints set. We also define $L = \ell_1 + \ell_2 + L_x + L_M$. As is done in [YAZ$^{+19}$], we employ the homomorphic commitment scheme from [BDL$^{+18}$] over the integers. More precisely, we define

$$ \mathbf{C} = \begin{bmatrix} \mathbf{I}_{\ell_1} & \mathbf{C}_1 \\ \mathbf{0}_{L_x+L_M \times \ell_1} & \mathbf{I}_{L_x+L_M} \mathbf{C}_2 \end{bmatrix} \in \mathbb{Z}_q^{(\ell_1+L_x+L_M) \times L}, $$

with $\mathbf{C}_1 \leftarrow U(\mathbb{Z}_q^{\ell_1 \times (L_x+L_M+\ell_2)}), \mathbf{C}_2 \leftarrow U(\mathbb{Z}_q^{(L_x+L_M) \times \ell_2})$. Let $p = 2^\lambda$ be the maximal magnitude of the challenges, and $M > 1$ the repetition rate of the rejection sampling procedure. We then set $\delta, t, T$ as per Corollary E.1, namely $\delta = \sqrt{\frac{32}{25 \log_2 e} \cdot \frac{\lambda+1}{L}}$, $t = \sqrt{(\lambda+2)/(\pi \log_2 e)}$ and $T = p \sqrt{5(1+\delta)/(8L)}$. Next define $s_2 = (-t+\sqrt{t^2+\ln(M)/\pi})^{-1} \cdot T$. We define the rejection sampling function by $\mathbf{p}(\mathbf{v}, \mathbf{z}) = \min(1, \mathcal{D}_{\mathbb{Z}^L, s_2}(\mathbf{z})/(M \cdot \mathcal{D}_{\mathbb{Z}^L, s_2}(\mathbf{z}-\mathbf{v})))$ for all $\mathbf{v}, \mathbf{z} \in \mathbb{Z}^L$. Finally, let aCommit be an auxiliary commitment scheme with randomness space $\{0, 1\}^\kappa$ and message space $\mathbb{Z}_q^{k+2(\ell_1+L_x+L_M)}$, and that is binding and hiding. The following interactive protocol involves a prover $\mathcal{P}$ with public input $\bar{\mathbf{A}} \in \mathbb{Z}_q^{k \times L_x}, \mathbf{y} \in \mathbb{Z}_q^k$, and $\mathcal{M} \subseteq [L_x]^3$ with $|\mathcal{M}| = L_M$ and private input $\mathbf{x} \in \mathbb{Z}_q^{L_x}$. The verifier $\mathcal{V}$ is only given the public input. In the protocol, $\mathcal{P}$ must convince $\mathcal{V}$ in zero-knowledge that they know $\mathbf{x}$ verifying

$$ \left\{ \begin{array}{l} \bar{\mathbf{A}}\mathbf{x} = \mathbf{y} \mod q \\ \forall (h, i, j) \in \mathcal{M}, \mathbf{x}[h] = \mathbf{x}[i]\mathbf{x}[j] \mod q \end{array} \right. \qquad (14) $$

**Theorem E.1.** The protocol described in Figure E.1 is complete with completeness error at most $\delta_c = 1 - 1/M + \text{negl}(\lambda)$.

We define $\beta_\infty = 8ps_2 \log_2 L$ and $\beta_2 = 8ps_2 \sqrt{L}$. Assume HNF-SIS$_{\ell_1, L, q, \beta_\infty, \beta_2}$ is $\delta_{SIS}$-hard and that aCommit is $\delta_h^a$-binding. Then, there exists an extractor $\mathcal{E}$ that for any $\bar{\mathbf{A}}, \mathbf{y}, \mathcal{M}$ and any PPT cheating prover $\hat{\mathcal{P}}$, if $\hat{\mathcal{P}}$ can convince a verifier $\mathcal{V}$ without knowing a witness with probability at least $2/(2p+1) + \varepsilon$ for a non-negligible $\varepsilon$, then $\mathcal{E}$ can extract an $\mathbf{x}$ that verifies (14) in polynomial time, except with probability $\delta_{SIS}$.

Finally, assume that HNF-LWE$_{\ell_2, \ell_1+L_x+L_M, q, \psi_1}$ is $\delta_{LWE}$-hard, and that the commitment aCommit is $\delta_h^a$-hiding. Then, there exists a simulator $\mathcal{S}$ that with input $\bar{\mathbf{A}}, \mathbf{y}, \mathcal{M}$ outputs a transcript that is $(\delta_h^a + 2^{-\lambda-1}(1+1/M) + \delta_{LWE})$-indistinguishable from the transcript of an honest execution of the protocol with a prover knowing a witness $\mathbf{x}$ satisfying (14).

Although the proof of Theorem E.1 follows naturally from that of [YAZ$^{+19}$], we give it in Section E.3. The above protocol can be turned into a non-interactive zero-knowledge argument of knowledge via the Fiat-Shamir heuristic in the random oracle model. In this case, the resulting proof does not contain the whole transcript as some elements are uniquely determined by the others for the proof to be correct. More precisely, the proof is $\pi = (\alpha, \rho, \mathbf{c}_1, \mathbf{z}_0, \mathbf{z}_1)$ where the challenge $\alpha = H(\bar{\mathbf{A}}, \mathbf{y}, \mathcal{M}, C_{aux}; \mathbf{AUX})$ with $\mathbf{AUX}$ an auxiliary input. The verification algorithm then re-computes $\mathbf{t}$ from the verification equation (4), $\mathbf{c}_2$ from
$\mathbf{r} \leftarrow U(Z_q^{\ell_x})$

$\mathbf{t} \leftarrow \bar{\mathbf{A}}\mathbf{r} \bmod q$

$\mathbf{s}_1 \leftarrow \psi_1^L$

$\mathbf{s}_2 \leftarrow D_{\mathcal{M}L, s_2}$

Let $\mathbf{a}, \mathbf{b}$ be $L_{\mathcal{M}}$-dimensional vectors

For $e \in [L_{\mathcal{M}}]$, let $(h, i, j)$ be the $e$-th element of $\mathcal{M}$

$\mathbf{a}[e] \leftarrow \mathbf{r}[h] - \mathbf{r}[i]\mathbf{x}[j] - \mathbf{r}[j]\mathbf{x}[i]$

$\mathbf{b}[e] \leftarrow -\mathbf{r}[i]\mathbf{r}[j]$

$\mathbf{c}_1 \leftarrow \mathbf{C}\mathbf{s}_1 + \begin{bmatrix} 0_{\ell_1} \\ \mathbf{x} \\ \mathbf{a} \\ \mathbf{0}_{\ell_1} \\ \mathbf{r} \\ \mathbf{b} \end{bmatrix} \bmod q$

$\mathbf{c}_2 \leftarrow \mathbf{C}\mathbf{s}_2 + \begin{bmatrix} \mathbf{r} \\ \mathbf{b} \end{bmatrix} \bmod q$

$\rho \leftarrow U(\{0, 1\}^\kappa)$

$C_{aux} \leftarrow \mathbf{a}\mathbf{Commit}(\mathbf{t}\|\mathbf{c}_1\|\mathbf{c}_2; \rho)$

$C_{aux}$

$\alpha \leftarrow U([-p, p])$

$\alpha$

$\mathbf{z}_0 \leftarrow \alpha\mathbf{x} + \mathbf{r}$

$\mathbf{z}_1 \leftarrow \alpha\mathbf{s}_1 + \mathbf{s}_2$

Abort with probability $1 - \mathbf{p}(\alpha\mathbf{s}_1, \mathbf{z}_1)$

$\mathbf{t}, \mathbf{c}_1, \mathbf{c}_2, \rho, \mathbf{z}_0, \mathbf{z}_1$

Let $\mathbf{d}$ be an $L_{\mathcal{M}}$-dimensional vector

For $e \in [L_{\mathcal{M}}]$, let $(h, i, j)$ be the $e$-th element of $\mathcal{M}$

$\mathbf{d}[e] \leftarrow \alpha\mathbf{z}_0[h] - \mathbf{z}_0[i]\mathbf{z}_0[j]$

Accept if:

(1) $C_{aux} = \mathbf{a}\mathbf{Commit}(\mathbf{t}\|\mathbf{c}_1\|\mathbf{c}_2; \rho)$

(2) $\|\mathbf{z}_1\|_\infty \le s_2 \log_2 L$

(3) $\|\mathbf{z}_1\|_2 \le s_2 \sqrt{L}$

(4) $\bar{\mathbf{A}}\mathbf{z}_0 = \alpha\mathbf{y} + \mathbf{t} \bmod q$

(5) $\mathbf{C}\mathbf{z}_1 + \begin{bmatrix} 0_{\ell_1} \\ \mathbf{z}_0 \\ \mathbf{d} \end{bmatrix} = \alpha\mathbf{c}_1 + \mathbf{c}_2 \bmod q$

**Fig. E.1.** Zero-knowledge Argument of Knowledge for Equation (14) with compacted commitments.

equation (5) and $C_{aux}$ from equation (1). We end up with a proof of size

$$ |\pi| = [\log_2(2p+1)] + \kappa + (\ell_1 + L_{\mathbf{x}} + L_{\mathcal{M}})[\log_2 q] + L_{\mathbf{x}}[\log_2 q] \\ + L[\log_2(s_2 \log_2 L)] \quad (15) $$

$$ = [\log_2(2p+1)] + \kappa + (\ell_1 + 2L_{\mathbf{x}} + L_{\mathcal{M}})[\log_2 q] + L[\log_2(s_2 \log_2 L)] \quad (16) $$

The last term in (15) does not appear in the proof size of [YAZ+19] as they treat $\mathbf{z}_1$ (and $\mathbf{z}_2$ in their case) as vectors in $\mathbb{Z}_q$. However, due to the rejection sampling, one has that they are Gaussian vectors and we can therefore reduce the amount of storage needed. Depending on the chosen parameters, this simple observation reduces the proof size by up to 20%.
### E.3 Proof of Theorem E.1

*Proof.* Completeness: Consider an honest execution of the protocol, i.e., between a prover $\mathcal{P}[\overline{\mathbf{A}}, \mathbf{y}, \mathcal{M}; \mathbf{x}]$ with $\mathbf{x}$ satisfying (14), and a verifier $\mathcal{V}[\overline{\mathbf{A}}, \mathbf{y}, \mathcal{M}]$. Since the execution is honest and since a Commit does not use any internal randomness other than $\rho$, (1) is trivially verified. Next, due to the rejection sampling, $\mathcal{P}$ respond in the third move only with probability $p(\alpha \mathbf{s}_1, \mathbf{z}_1)$. By Corollary E.1, it holds that the prover responds with probability at least $(1-2^{-\lambda})/M$, and that $\mathbf{z}_1$ is within statistical distance $2^{-\lambda-1}(1+1/M)$ of $\mathcal{D}_{\mathbb{Z}^L, s_2}$. We further condition on a non-aborting transcript. Lemma 2.3 combined with the union bound gives

$$ \mathbb{P}[\|\mathbf{z}_1\|_{\infty} > s_2 \log_2 L \lor \|\mathbf{z}_1\|_2 > s_2 \sqrt{L}] \le 2^{-\lambda-1} \left(1 + \frac{1}{M}\right) + 2^{-2L} + 2Le^{-\pi \log_2 L} $$

Equation (4) is easily verified as $\overline{\mathbf{A}}\mathbf{z}_0 = \overline{\mathbf{A}}(\alpha\mathbf{x}+\mathbf{r}) = \alpha(\overline{\mathbf{A}}\mathbf{x})+\overline{\mathbf{A}}\mathbf{r} = \alpha\mathbf{y}+\mathbf{t} \bmod q$. Now, let $e \in [L_{\mathcal{M}}]$ and let $(h, i, j)$ be the $e$-th element of $\mathcal{M}$. We have

$$ \begin{aligned} \mathbf{d}[e] &= \alpha \mathbf{z}_0[h] - \mathbf{z}_0[i] \mathbf{z}_0[j] \\ &= \alpha(\alpha \mathbf{x}[h] + \mathbf{r}[h]) - (\alpha \mathbf{x}[i] + \mathbf{r}[i])(\alpha \mathbf{x}[j] + \mathbf{r}[j]) \\ &= \alpha^2(\mathbf{x}[h] - \mathbf{x}[i]\mathbf{x}[j]) + \alpha(\mathbf{r}[h] - \mathbf{r}[i]\mathbf{x}[j] - \mathbf{r}[j]\mathbf{x}[i]) + (-\mathbf{r}[i]\mathbf{r}[j]) \\ &= \alpha \mathbf{a}[e] + \mathbf{b}[e] \bmod q. \end{aligned} $$

As a result, it holds that $\mathbf{d} = \alpha\mathbf{a} + \mathbf{b} \bmod q$. It thus yields

$$ \begin{aligned} \mathbf{C}\mathbf{z}_1 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{z}_0 \\ \mathbf{d} \end{bmatrix} &= \mathbf{C}(\alpha\mathbf{s}_1 + \mathbf{s}_2) + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \alpha\mathbf{x} + \mathbf{r} \\ \alpha\mathbf{a} + \mathbf{b} \end{bmatrix} \bmod q \\ &= \alpha \left( \mathbf{C}\mathbf{s}_1 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{x} \\ \mathbf{a} \end{bmatrix} \right) + \left( \mathbf{C}\mathbf{s}_2 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{r} \\ \mathbf{b} \end{bmatrix} \right) \bmod q \\ &= \alpha\mathbf{c}_1 + \mathbf{c}_2 \bmod q, \end{aligned} $$

proving (5). Combining it all yields

$$ \mathbb{P}[\langle \mathcal{P}[\overline{\mathbf{A}}, \mathbf{y}, \mathcal{M}; \mathbf{x}], \mathcal{V}[\overline{\mathbf{A}}, \mathbf{y}, \mathcal{M}] \rangle \neq 1] \le 1 - 1/M + \text{negl}(\lambda). $$

*Extractor:* Now, assume that a cheating prover $\hat{\mathcal{P}}$ can convince the verifier that they possess a witness for $(\overline{\mathbf{A}}, \mathbf{y}, \mathcal{M})$ with probability $2/(2p+1)+\varepsilon$ for some non-negligible $\varepsilon$. We construct the extractor $\mathcal{E}$ that uses $\hat{\mathcal{P}}$ via black-box access. First, $\mathcal{E}$ runs $\hat{\mathcal{P}}$ until it obtains an accepting transcript $(\mathbf{t}, \mathbf{c}_1, \mathbf{c}_2, \alpha, \mathbf{z}_0, \mathbf{z}_1)$. Between each run, $\mathcal{E}$ rewinds the inner randomness of $\hat{\mathcal{P}}$ to have the same first move response. This first transcript is obtained in expected time $T_1 = (2/(2p+1)+\varepsilon)^{-1}$. Then, $\mathcal{E}$ re-iterates the same process but sends challenges $\alpha' \neq \alpha$ to $\hat{\mathcal{P}}$. Assuming a Commit is $\delta_b^a$-binding and since the first move always uses the same randomness, $\mathcal{E}$ can therefore obtain another accepting transcript $(\mathbf{t}, \mathbf{c}_1, \mathbf{c}_2, \alpha', \mathbf{z}'_0, \mathbf{z}'_1)$
in expected time $T_2 = (1/(2p+1) + \epsilon - \delta_b^a)^{-1}$. It then continues running $\hat{\mathcal{P}}$ with challenges $\alpha'' \notin \{\alpha, \alpha'\}$ to get a third accepting transcript $(\mathbf{t}, \mathbf{c}_1, \mathbf{c}_2, \alpha'', \mathbf{z}_0'', \mathbf{z}_1'')$ in expected time $T_3 = (\epsilon - \delta_b^a)^{-1}$. The total expected time is therefore $T = T_1 + T_2 + T_3 \le \text{poly}(\lambda)$. Finally, the extractor $\mathcal{E}$ outputs the witness $\bar{\mathbf{x}} = (\alpha' - \alpha)^{-1}(\mathbf{z}_0' - \mathbf{z}_0)$ mod $q$. We now analyze the correctness of $\mathcal{E}$. We further define $\Delta_1 = \alpha' - \alpha$ and $\Delta_2 = \alpha'' - \alpha$. First, we have

$$ 
\begin{aligned}
\bar{\mathbf{A}}\bar{\mathbf{x}} &= \Delta_1^{-1}(\bar{\mathbf{A}}\mathbf{z}_0' - \bar{\mathbf{A}}\mathbf{z}_0) \mod q \\
&= \Delta_1^{-1}(\alpha'\mathbf{y} + \mathbf{t} - (\alpha\mathbf{y} + \mathbf{t})) \mod q \quad (\text{by (4)}) \\
&= \Delta_1^{-1}(\alpha' - \alpha)\mathbf{y} \mod q \\
&= \mathbf{y} \mod q.
\end{aligned}
$$

We now prove that $\bar{\mathbf{x}}$ verifies the quadratic constraints except with probability $\delta_{\text{SIS}}$. For that, we define $\mathbf{e}' = \mathbf{z}'_1 - \mathbf{z}_1$, $\mathbf{e}'' = \mathbf{z}''_1 - \mathbf{z}_1$, $\mathbf{f}' = \mathbf{z}'_0 - \mathbf{z}_0$, $\mathbf{f}'' = \mathbf{z}''_0 - \mathbf{z}_0$, and $\mathbf{g}' = \mathbf{d}' - \mathbf{d}$, $\mathbf{g}'' = \mathbf{d}'' - \mathbf{d}$. The verification equation (5) gives

$$ 
\left\{ 
\begin{array}{l}
\mathbf{C}\mathbf{e}' + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{f}' \\ \mathbf{g}' \end{bmatrix} = \Delta_1 \mathbf{c}_1 \mod q \\[2ex]
\mathbf{C}\mathbf{e}'' + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{f}'' \\ \mathbf{g}'' \end{bmatrix} = \Delta_2 \mathbf{c}_1 \mod q.
\end{array}
\right.
$$

Cancelling the right-hand side provides us with

$$ \mathbf{C}(\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}'') + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ (\Delta_2 \mathbf{f}' - \Delta_1 \mathbf{f}'') \\ (\Delta_2 \mathbf{g}' - \Delta_1 \mathbf{g}'') \end{bmatrix} = \mathbf{0} \mod q. $$

The first block then gives $[\mathbf{I}_{\ell_1}|\mathbf{C}_1](\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}'') = \mathbf{0} \mod q$. Yet, we can bound the norms of $\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}''$ using the verification equations (2) and (3) and get $\|\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}''\|_{\infty} \le 8ps_2 \log_2 L = \beta_{\infty}$ and $\|\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}''\|_2 \le 8ps_2 \sqrt{L} = \beta_2$. Since we assume that HNF-SIS$_{\ell_1,L,q,\beta_{\infty},\beta_2}$ is $\delta_{\text{SIS}}$-hard, then no PPT adversary can solve it with advantage more than $\delta_{\text{SIS}}$. Hence, we get that $\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}'' = \mathbf{0}$ except with probability at most $\delta_{\text{SIS}}$. We now condition on $\Delta_2 \mathbf{e}' - \Delta_1 \mathbf{e}'' = \mathbf{0}$. The second and third blocks in the above yields $\Delta_2 \mathbf{f}' = \Delta_1 \mathbf{f}'' \mod q$ and $\Delta_2 \mathbf{g}' = \Delta_1 \mathbf{g}'' \mod q$. We now define $\bar{\mathbf{r}} = \mathbf{z}_0 - \alpha \bar{\mathbf{x}} \mod q$. Then

$$ \mathbf{z}'_0 - \alpha' \bar{\mathbf{x}} = \mathbf{z}'_0 - \Delta_1 \bar{\mathbf{x}} - \alpha \bar{\mathbf{x}} = \mathbf{z}'_0 - \mathbf{f}' - \alpha \bar{\mathbf{x}} \mod q = \bar{\mathbf{r}} \mod q \quad (17) $$

$$ 
\begin{aligned}
\mathbf{z}''_0 - \alpha'' \bar{\mathbf{x}} &= \mathbf{z}''_0 - \Delta_2 \bar{\mathbf{x}} - \alpha \bar{\mathbf{x}} = \mathbf{z}''_0 - \Delta_2 \Delta_1^{-1} \mathbf{f}' - \alpha \bar{\mathbf{x}} \\
&= \mathbf{z}''_0 - \Delta_2 \Delta_2^{-1} \mathbf{f}'' - \alpha \bar{\mathbf{x}} \mod q \\
&= \bar{\mathbf{r}} \mod q.
\end{aligned}
\quad (18) $$
Now let $e \in [L_M]$ and $(h, i, j)$ be the $e$-th element of $M$. We have

$$
\begin{align*}
\mathbf{d}[e] &= \alpha \mathbf{z}_0[h] - \mathbf{z}_0[i] \mathbf{z}_0[j] \\
&= \alpha(\alpha \bar{\mathbf{x}}[h] + \bar{\mathbf{r}}[h]) - (\alpha \bar{\mathbf{x}}[i] + \bar{\mathbf{r}}[i])(\alpha \bar{\mathbf{x}}[j] + \bar{\mathbf{r}}[j]) \\
&= \alpha^2(\bar{\mathbf{x}}[h] - \bar{\mathbf{x}}[i]\bar{\mathbf{x}}[j]) + \alpha(\bar{\mathbf{r}}[h] - \bar{\mathbf{r}}[i]\bar{\mathbf{x}}[j] - \bar{\mathbf{r}}[j]\bar{\mathbf{x}}[i]) + (-\bar{\mathbf{r}}[i]\bar{\mathbf{r}}[j]) \\
&= \mathbf{c}[e]\alpha^2 + \mathbf{a}[e]\alpha + \mathbf{b}[e].
\end{align*}
$$

Due to Equations (17) and (18), we also have $\mathbf{d}' = \alpha'^2\mathbf{c} + \alpha'\mathbf{a} + \mathbf{b}$ and $\mathbf{d}'' = \alpha''^2\mathbf{c} + \alpha''\mathbf{a} + \mathbf{b}$. Hence, since $\Delta_1^{-1}\mathbf{g}' = \Delta_2^{-1}\mathbf{g}'' \mod q$, we obtain

$$ (\alpha' + \alpha)\mathbf{c} + \mathbf{a} = (\alpha'' + \alpha)\mathbf{c} + \mathbf{a} \mod q $$

which leads to $(\alpha'' - \alpha)\mathbf{c} = \mathbf{0} \mod q$. Since $\alpha'' \neq \alpha'$ and $q$ is prime, then $\alpha'' - \alpha' \in \mathbb{Z}_q^\times$ and therefore $\mathbf{c} = \mathbf{0} \mod q$. This proves that for all $(h, i, j) \in M$, $\bar{\mathbf{x}}[h] = \bar{\mathbf{x}}[i]\bar{\mathbf{x}}[j] \mod q$. As a result, the output of $\mathcal{E}$ is correct except with probability at most $\delta_{\text{SIS}}$.

**Simulator:** We construct the following simulator $\mathcal{S}$ that simulates the distribution of an honest transcript but only using the public inputs. It proceeds as follows

1. $\alpha \leftarrow U([-p, p])$

2. $\mathbf{z}_0 \leftarrow U(\mathbb{Z}_q^{L_\alpha})$

3. $\mathbf{t} \leftarrow \bar{\mathbf{A}}\mathbf{z}_0 - \alpha\mathbf{y} \mod q$

4. For $e \in [L_M]$, let $(h, i, j)$ be the $e$-th element of $M$. Then, $\mathbf{d}[e] \leftarrow \alpha \mathbf{z}_0[h] - \mathbf{z}_0[i] \mathbf{z}_0[j]$

5. $\mathbf{z}_1 \leftarrow \mathcal{D}_{\mathbb{Z}^{L_\alpha}, s_2}$

6. $\mathbf{c}_1 \leftarrow U(\mathbb{Z}_q^{\ell_1+L_\alpha+L_M})$

7. $\mathbf{c}_2 \leftarrow \mathbf{C}\mathbf{z}_1 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{z}_0 \\ \mathbf{d} \end{bmatrix} - \alpha\mathbf{c}_1 \mod q$

8. $\rho \leftarrow U(\{0, 1\}^\kappa)$

9. $C_{\text{aux}} \leftarrow \text{aCommit}(\mathbf{t} \| \mathbf{c}_1 \| \mathbf{c}_2; \rho)$

10. $C'_{\text{aux}} \leftarrow \text{aCommit}(\mathbf{0}; \rho)$

11. Output $(C_{\text{aux}}, \alpha, \mathbf{t}, \mathbf{c}_1, \mathbf{c}_2, \rho, \mathbf{z}_0, \mathbf{z}_1)$ with probability $1/M$ and $(C'_{\text{aux}}, \alpha, \perp)$ otherwise.

We now prove that the output of $\mathcal{S}$ is computationally indistinguishable from the transcript of an honest execution of the protocol. We proceed by game hopping. **Game $G_0$:** This corresponds to an honest execution.

**Game $G_1$:** Here, the prover $\mathcal{P}$ retrieves the challenge $\alpha$ from the honest verifier by sending $\text{aCommit}(\mathbf{0}; \rho)$ for some $\rho \leftarrow U(\{0, 1\}^\kappa)$. It then rewinds the verifier to its initial state including its inner randomness. It then proceeds as follows:

1. $\mathbf{r} \leftarrow U(\mathbb{Z}_q^{L_\alpha})$

2. $\mathbf{t} \leftarrow \bar{\mathbf{A}}\mathbf{r} \mod q$

3. $\mathbf{s}_1 \leftarrow \psi_1^L$

4. $\mathbf{s}_2 \leftarrow \mathcal{D}_{\mathbb{Z}^{L_\alpha}, s_2}$
5. For $e \in [L_M]$, let $(h, i, j)$ be the $e$-the element of $M$. Then, $\mathbf{a}[e] \leftarrow \mathbf{r}[h] - \mathbf{r}[i]\mathbf{x}[j] - \mathbf{r}[j]\mathbf{x}[i]$ and $\mathbf{b}[e] \leftarrow -\mathbf{r}[i]\mathbf{r}[j]$

6. $\mathbf{c}_1 \leftarrow \mathbf{C}\mathbf{s}_1 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{x} \\ \mathbf{a} \end{bmatrix} \bmod q$

7. $\mathbf{c}_2 \leftarrow \mathbf{C}\mathbf{s}_2 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{r} \\ \mathbf{b} \end{bmatrix} \bmod q$

8. $\mathbf{z}_0 \leftarrow \alpha\mathbf{x} + \mathbf{r}$

9. $\mathbf{z}_1 \leftarrow \alpha\mathbf{s}_1 + \mathbf{s}_2$

10. Set the binary variable abort to 1 with probability $1 - \mathfrak{p}(\alpha\mathbf{s}_1, \mathbf{z}_1)$

11. $\rho \leftarrow U(\{0, 1\}^\kappa)$

12. $C_{aux} \leftarrow \mathbf{a}\mathbf{Commit}(\mathbf{t}\|\mathbf{c}_1\|\mathbf{c}_2; \rho)$ and it sends $C_{aux}$ to the verifier

13. When receiving $\alpha'$ from the verifier, the prover aborts if abort = 1 and otherwise sends $(\mathbf{t}, \mathbf{c}_1, \mathbf{c}_2, \rho, \mathbf{z}_0, \mathbf{z}_1)$.

**Game G2:** It is identical to $G_1$ except in the computation of $\mathbf{t}$ and $\mathbf{c}_2$. They are instead computed to verify equations (4) and (5) in the verification:

1. $\mathbf{t} \leftarrow \bar{\mathbf{A}}\mathbf{z}_0 - \alpha\mathbf{y} \bmod q$

2. For $e \in [L_M]$, let $(h, i, j)$ be the $e$-the element of $M$. Then, $\mathbf{d}[e] \leftarrow \alpha\mathbf{z}_0[h] - \mathbf{z}_0[i]\mathbf{z}_0[j]$

3. $\mathbf{c}_2 \leftarrow \mathbf{C}\mathbf{z}_1 + \begin{bmatrix} \mathbf{0}_{\ell_1} \\ \mathbf{z}_0 \\ \mathbf{d} \end{bmatrix} - \alpha\mathbf{c}_1 \bmod q$

**Game G3:** It is identical to $G_2$ except for the computation of $C_{aux}$.

1. $C_{aux} \leftarrow \mathbf{a}\mathbf{Commit}(\mathbf{0}; \rho)$ if abort = 1 and $C_{aux} \leftarrow \mathbf{a}\mathbf{Commit}(\mathbf{t}\|\mathbf{c}_1\|\mathbf{c}_2; \rho)$ otherwise.

**Game G4:** It is identical to $G_3$ except in the computation of $\mathbf{z}_1$ and abort.

1. $\mathbf{z}_1 \leftarrow \mathcal{D}_{\mathbb{Z}^{L_s, s_2}}$

2. Set abort = 1 with probability $1 - 1/M$ and 0 otherwise

**Game G5:** It is identical to $G_4$ except in the computation of $\mathbf{c}_1$.

1. $\mathbf{c}_1 \leftarrow U(\mathbb{Z}_{q}^{\ell_1+L_x+L_M})$

**Game G6:** It is identical to $G_5$ except in the computation of $\mathbf{z}_0$

1. $\mathbf{z}_0 \leftarrow U(\mathbb{Z}_{q}^{L_x})$

We now prove that each game is indistinguishable from the next. First, since the verifier $\mathcal{V}$ is honest, the challenge $\alpha'$ is fully determined by its inner randomness. As it is rewinded, we always have $\alpha' = \alpha$. All other variables are identically distributed, which gives

$$ \Delta(\text{View}_{G_0}(\mathcal{V}), \text{View}_{G_1}(\mathcal{V})) = 0. \qquad (19) $$
By the completeness of the protocol, $t$ and $c_2$ are uniquely determined by the other variables and the verification equations (4) and (5). Thus

$$ \Delta(\text{View}_{G_1}(\mathcal{V}), \text{View}_{G_2}(\mathcal{V})) = 0. \qquad (20) $$

Since aCommit is $\delta_h^a$-hiding, it holds that a PPT adversary $\mathcal{A}$ can distinguish between games $G_2$ and $G_3$ with advantage at most $\delta_h^a$.

$$ |\mathbb{P}[\mathcal{A}(\text{View}_{G_2}(\mathcal{V})) = 1] - \mathbb{P}[\mathcal{A}(\text{View}_{G_3}(\mathcal{V})) = 1]| \le \delta_h^a. \qquad (21) $$

Then, by Corollary E.1, it directly holds that the computation of $z_1$ and abort in $G_4$ is within statistical distance $2^{-\lambda-1}(1+1/M)$ of that of game $G_3$. Hence

$$ \Delta(\text{View}_{G_3}(\mathcal{V}), \text{View}_{G_4}(\mathcal{V})) \le 2^{-\lambda-1}(1+1/M). \qquad (22) $$

We then use the hiding property of the commitment scheme from [BDL$^{+18}$] to argue that $G_4$ and $G_5$ are indistinguishable under the LWE assumption. The details are already provided in [YAZ$^{+19}$. More precisely, since we assume that HNF-LWE$_{\ell_2, \ell_1+L_x+L_M, q, \psi_1}$ is $\delta_{LWE}$-hard, then for any PPT adversary $\mathcal{A}$ we get

$$ |\mathbb{P}[\mathcal{A}(\text{View}_{G_4}(\mathcal{V})) = 1] - \mathbb{P}[\mathcal{A}(\text{View}_{G_5}(\mathcal{V})) = 1]| \le \delta_{LWE}. \qquad (23) $$

In $G_5$, $z_0 = \alpha x + r$ where $r$ is uniform in $\mathbb{Z}_{q^\lambda}^\times$ and independent of $\alpha x$. Hence, $z_0$ is also uniform in $\mathbb{Z}_{q^\lambda}^\times$. Thus:

$$ \Delta(\text{View}_{G_5}(\mathcal{V}), \text{View}_{G_6}(\mathcal{V})) = 0. \qquad (24) $$

Then, the distribution of the transcript in $G_6$ no longer depends on the witness $x$ and is exactly the same as the output of $\mathcal{S}$. Combining Equations (19), (20), (21), (22), (23) and (24) yields

$$ |\mathbb{P}[\mathcal{A}(\text{View}_{G_0}(\mathcal{V})) = 1] - \mathbb{P}[\mathcal{A}(\mathcal{S}(\bar{\mathbf{A}}, \mathbf{y}, \mathcal{M})) = 1]| \le \delta_h^a + 2^{-\lambda-1}(1+1/M) + \delta_{LWE}, $$
as desired. $\square$

## F Instantiating the Protocols

In this section we show how to instantiate the different relations to be proven in zero-knowledge with the proof system of [YAZ$^{+19}$. More precisely, we need to have zero-knowledge arguments for the opening of an Ajtai commitment, and for the verification equation of our signature with efficient protocols. We detail both in Sections F.1 and F.2. For completeness and for performance comparison purposes, we also instantiate the construction Libert et al. [LLM$^{+16}$] with the framework of [YAZ$^{+19}$].

When concretely evaluating these proofs, we consider the optimizations proposed in Appendix E, consisting in compacting the commitments of the original framework and in better parameter selections, which leads to substantial efficiency improvements.
## F.1 Proof of Commitment Opening.

Consider a prover with private input $\mathbf{m} \in \{0, 1\}^{m_3}$ and $\mathbf{r}' \sim D_{\mathbb{Z}^{m_1}, \sigma_3}$, and public input $\mathbf{p}\mathbf{p}, \mathbf{p}\mathbf{k}$. Recall that by Lemma 2.3, we have $\|\mathbf{r}'\|_{\infty} \le \sigma_3 \log_2 m_1$ with overwhelming probability. We can thus define $\alpha_3 = [\sigma_3 \log_2 m_1]$ and assume that $\mathbf{r}' \in [-\alpha_3, \alpha_3]^{m_1}$. The prover wishes to prove that

$$ \mathbf{A}\mathbf{r}' + \mathbf{D}\mathbf{m} = \mathbf{c} \mod q \wedge \|\mathbf{r}'\|_{\infty} \le \alpha_3 \wedge \mathbf{m} \in \{0, 1\}^{m_1}. $$

We thus transform this relation into one that fits the Yang et al. framework. For that, we first define $\mathbf{a}_3 = \alpha_3 \mathbf{1}_{m_1}$. Next, we define $\mathbf{r}'' = \mathbf{r}' + \mathbf{a}_3 \in [0, 2\alpha_3]^{m_1}$. Let $k_{\alpha_3} = \lfloor \log_2 2\alpha_3 \rfloor + 1$ and define$^{11}$ $\mathbf{g}_{\alpha_3} = \lfloor (2\alpha_3 + 2^{i-1})/2^i \rfloor \rfloor_{i \in [k_{\alpha_3}]} \in \mathbb{Z}^{1 \times k_{\alpha_3}}$, and $\mathbf{G}_{\alpha_3} = \mathbf{I}_{m_1} \otimes \mathbf{g}_{\alpha_3}$. We then denote by $\bar{\mathbf{r}}' \in \{0, 1\}^{m_1 k_{\alpha_3}}$ a binary decomposition of $\mathbf{r}''$ along $\mathbf{g}_{\alpha_3}$, i.e., that verifies $\mathbf{r}'' = \mathbf{G}_{\alpha_3} \bar{\mathbf{r}}'$. Such a decomposition can be efficiently computed. It now suffices to prove the following

$$ \mathbf{A}\mathbf{G}_{\alpha_3}\bar{\mathbf{r}}' + \mathbf{D}\mathbf{m} = \mathbf{c} + \mathbf{A}\mathbf{a}_3 \mod q \wedge \bar{\mathbf{r}}' \in \{0, 1\}^{m_1 k_{\alpha_3}} \wedge \mathbf{m} \in \{0, 1\}^{m_3}. $$

By defining $\bar{\mathbf{A}} = [\mathbf{A}\mathbf{G}_{\alpha_3}|\mathbf{D}]$, $\mathbf{x} = [\bar{\mathbf{r}}']^T|\mathbf{m}^T]^T$, $\mathbf{y} = \mathbf{c} + \mathbf{A}\mathbf{a}_3$ and $\mathcal{M} = \{(i, i, i); i \in [m_1 k_{\alpha_3} + m_3]\}$, we have $((\bar{\mathbf{A}}, \mathbf{y}, \mathcal{M}); \mathbf{x}) \in \mathcal{R}^*$. The length of the witness is $L_{\mathbf{x}} = m_1 k_{\alpha_3} + m_3$, and the size of $\mathcal{M}$ is $L_{\mathcal{M}} = L_{\mathbf{x}}$. Note that since $q$ is prime, the constraint $\mathbf{x}[i] = \mathbf{x}[i]^2 \mod q$ indeed implies that $\mathbf{x}[i] \in \{0, 1\}$.

When $m_1 \gg \lambda$, the fast mode of Section 4.2 compresses the size of the witness and the constraint set as we now prove that $\mathbf{H}\mathbf{r}'$ has coefficients bounded by $\sigma_3 \sqrt{m_1} \log_2 \lambda$. It yields a witness of size $L_{\mathbf{x}} = m_1 + k(\lfloor \log_2(2\sigma_3 \sqrt{m_1} \log_2 \lambda) \rfloor + 1) + m_3$, with $k = \lambda/\log_2(9/5)$, and $L_{\mathcal{M}} = L_{\mathbf{x}} - m_1$.

## F.2 Proof of Message-Signature Pair Possession.

Here, the prover has a private input $\mathbf{m} \in \{0, 1\}^{m_3}$ and $(\tau, \mathbf{v}) \in \mathbb{Z}_q \times \mathbb{Z}^m$ and has to prove

$$ \mathbf{A}\mathbf{v}_1 - \mathbf{B}\mathbf{v}_2 + \tau \mathbf{G}\mathbf{v}_2 - \mathbf{D}\mathbf{m} = \mathbf{u} \mod q, $$

where $\mathbf{v}_1 \in \mathbb{Z}^{m_1}$ and $\mathbf{v}_2 \in \mathbb{Z}^{m_2}$, with $\|\mathbf{v}_1\|_{\infty} \le \sigma_1 \log_2 m_1$, $\|\mathbf{v}_2\|_{\infty} \le \sigma_1 \log_2 m_2$, $\tau \in \mathcal{T}$ and $\mathbf{m} \in \{0, 1\}^{m_3}$. We define

$$ \left\{ \begin{array}{lll} \alpha_1 = \lfloor \sigma_1 \log_2 m_1 \rfloor & k_{\alpha_1} = \lfloor \log_2 2\alpha_1 \rfloor + 1 & \mathbf{g}_{\alpha_1} = \lfloor (2\alpha_1 + 2^{i-1})/2^i \rfloor \rfloor_{i \in [k_{\alpha_1}]} \\ \alpha = \lfloor \sigma \log_2 m_2 \rfloor & k_{\alpha} = \lfloor \log_2 2\alpha \rfloor + 1 & \mathbf{g}_{\alpha} = \lfloor (2\alpha + 2^{i-1})/2^i \rfloor \rfloor_{i \in [k_{\alpha}]} \\ & k_{q'} = \lfloor \log_2 q' \rfloor + 1 & \mathbf{g}_{q'} = \lfloor (q' + 2^{i-1})/2^i \rfloor \rfloor_{i \in [k_{q'}]} \end{array} \right. $$

Further, we define $\mathbf{a}_1 = \alpha_1 \mathbf{1}_{m_1}$ and $\mathbf{a} = \alpha \mathbf{1}_{m_2}$. Next, we set $\mathbf{G}_{\alpha_1} = \mathbf{I}_{m_1} \otimes \mathbf{g}_{\alpha_1}$, and $\mathbf{G}_{\alpha} = \mathbf{I}_{m_2} \otimes \mathbf{g}_{\alpha}$. We define $\mathbf{v}'_1 = \mathbf{v}_1 + \mathbf{a}_1$, and $\mathbf{v}'_2 = \mathbf{v}_2 + \mathbf{a}$. We then denote $\bar{\mathbf{v}}_j$ their respective binary decomposition along $\mathbf{g}_{\alpha_1}, \mathbf{g}_{\alpha}$, i.e., such that $\mathbf{G}_{\alpha_1} \bar{\mathbf{v}}_1 = \mathbf{v}'_1$, and $\mathbf{G}_{\alpha} \bar{\mathbf{v}}_2 = \mathbf{v}'_2$. We also denote by $\bar{\tau}$ the binary decomposition of $\tau$ along $\mathbf{g}_{q'}$ such that $\tau = \mathbf{g}_{q'} \bar{\tau}$. We need however to deal with the product term $\tau \mathbf{v}_2$. We use

<footnote>$^{11}$ Choosing $\mathbf{g}_{\alpha_3}$ this way ensures that for any binary vector $\mathbf{x}$, $\mathbf{g}_{\alpha_3} \mathbf{x} \in [0, 2\alpha_3]$.</footnote>
the same idea as for subset-sums from the framework of Yang et al. [YAZ+19]. For that, we define $\mathbf{u}_2 = \mathbf{Gv}_2 \in \mathbb{Z}^n$, and $\mathbf{u}'_2 = \tau \mathbf{u}_2$. This gives an additional linear relation, but fewer decompositions. The prover now has to prove that

$$ \left\{ \begin{array}{l} \mathbf{A}\mathbf{G}_{\alpha_1}\bar{\mathbf{v}}_1 - \mathbf{B}\mathbf{G}_{\alpha}\bar{\mathbf{v}}_2 + \mathbf{u}'_2 - \mathbf{D}\mathbf{m} = \mathbf{u} + \mathbf{A}\mathbf{a}_1 - \mathbf{B}\mathbf{a} \bmod q \\ \mathbf{G}\mathbf{G}_{\alpha}\bar{\mathbf{v}}_2 - \mathbf{u}_2 = \mathbf{G}\mathbf{a} \bmod q \\ -\tau + \mathbf{g}_{q'}\bar{\tau} = 0 \bmod q \end{array} \right. $$

We thus define $\mathbf{x} = [\tau|\bar{\tau}|\bar{\mathbf{v}}_1|\bar{\mathbf{v}}_2|\mathbf{m}|\mathbf{u}_2|\mathbf{u}'_2] \in \mathbb{Z}^{L_{\mathbf{x}}}$, where $L_{\mathbf{x}} = 1 + k_{q'} + m_1 k_{\alpha_1} + m_2 k_{\alpha} + m_3 + 2n$, as well as

$$ \bar{\mathbf{A}} = \begin{bmatrix} \mathbf{0}_{n \times 1} & \mathbf{0}_{n \times k_{q'}} & \mathbf{A}\mathbf{G}_{\alpha_1} & -\mathbf{B}\mathbf{G}_{\alpha} & -\mathbf{D} & \mathbf{0}_{n \times n} & \mathbf{I}_n \\ \mathbf{0}_{n \times 1} & \mathbf{0}_{n \times k_{q'}} & \mathbf{0}_{n \times m_1 k_{\alpha_1}} & \mathbf{G}\mathbf{G}_{\alpha} & \mathbf{0}_{n \times m_3} & -\mathbf{I}_n & \mathbf{0}_{n \times n} \\ -1 & \mathbf{g}_{q'} & \mathbf{0}_{n \times m_1 k_{\alpha_1}} & \mathbf{0}_{1 \times m_2 k_{\alpha}} & \mathbf{0}_{1 \times m_3} & \mathbf{0}_{1 \times n} & \mathbf{0}_{1 \times n} \end{bmatrix} $$

and $\mathbf{y} = [\mathbf{u} + \mathbf{A}\mathbf{a}_1 - \mathbf{B}\mathbf{a}|\mathbf{G}\mathbf{a}'|0] \bmod q \in \mathbb{Z}_q^{2n+1}$. Finally, we define $\mathcal{M}_1 = \{(i, i, i); i \in [2, 1 + k_{q'} + m_1 k_{\alpha_1} + m_2 k_{\alpha} + m_3]\}$, which corresponds to the coefficients that need to be binary. We then need to add the relations $\mathbf{u}'_2 = \tau \mathbf{u}_2$. For that, we define

$$ \mathcal{M}_2 = \{(1 + k_{q'} + m_1 k_{\alpha_1} + m_2 k_{\alpha} + m_3 + n + i, 1, \\ 1 + k_{q'} + m_1 k_{\alpha_1} + m_2 k_{\alpha} + m_3 + i); i \in [n]\}, $$

and construct $\mathcal{M} = \mathcal{M}_1 \cup \mathcal{M}_2$. The witness has length $L_{\mathbf{x}}$, and $\mathcal{M}$ is of size $L_{\mathcal{M}} = L_{\mathbf{x}} - n - 1$. Using the fast mode instead proves that $\mathbf{H}_1\mathbf{v}_1, \mathbf{H}_2\mathbf{v}_2$ have coefficients bounded by $\sigma_1\sqrt{m_1}\log_2\lambda$ and $\sigma_2\sqrt{m_2}\log_2\lambda$ respectively. It yields a witness of size $L_{\mathbf{x}} = 1 + k_{q'} + m_1 + m_2 + m_3 + 2n + k(\lfloor\log_2(2\sigma_1\sqrt{m_1}\log_2\lambda)\rfloor + \lfloor\log_2(2\sigma_2\sqrt{m_2}\log_2\lambda)\rfloor + 2)$, with $k = \lambda/\log_2(9/5)$, and $L_{\mathcal{M}} = L_{\mathbf{x}} - m_1 - m_2 - n - 1$.

**Remark F.1.** In the case where $q' = q$, the tag does not need to be decomposed in binary form. However, when the proof system is run only a few number of times, we need to drastically increase the size of challenges to reach a negligible soundness error. For example, to obtain a negligible soundness error in one iteration, one needs to take challenges of size $p = 2^{\lambda}$. Because the SIS bound for the proof system is $\beta_{\infty} = \text{poly}(\lambda) \cdot p^2$, one must take $q$ to be polynomially larger than $p^2$. In Algorithm 3.1, choosing $q' = q$ then leads to a tag space $\mathcal{T}$ of size at least $\text{poly}(\lambda)2^{2\lambda}$. As a result, the proof of Lemma 3.2 incurs an exponential reduction loss of $1/|\mathcal{T}| = 2^{-2\lambda}/\text{poly}(\lambda)$. To circumvent this limitation, one can choose $q' = \text{poly}(\lambda) \ll q$ to make the reduction loss acceptable. It implies that the signature verification must ensure that $\tau < q'$, which we consider when proving possession of a message-signature pair.

## F.3 Instantiating [LLM+16] with $\mathcal{R}^*$

The original construction by Libert et al. [LLM+16] uses the binary decomposition of the commitment $\mathbf{c}$ instead of using the commitment itself. It additionally bases itself on the Boyen signature scheme, and involves an extra
matrix $\mathbf{D} \in \mathbb{Z}_q^{n \times 2nk}$, where $k = \lceil \log_2 q \rceil$. For a fair comparison, we detail here how to use the framework from [YAZ$^{+19}$] for the construction of [LLM$^{+16}$]. For this section only, we set the parameters differently according to [LLM$^{+16}$]. We thus have $m = 2nk$, $\sigma_1 = \sigma\sqrt{1+8(N+1)^2m^3}$. Also, prior to being signed, the message blocks are encoded using $b \mapsto (1-b, b)$. This means that although the relevant message information is of $mN$ bits, it is treated as a message of $2mN$ bits. To be thorough, one would need to prove that the message is properly encoded in addition to proving that the message is binary. This can be done by proving the additional relation $(\mathbf{I}_{mN} \otimes [1 \ 1])\mathbf{m} = \mathbf{1}_{mN}$ which proves that the consecutive bits $b, 1-b$ indeed sum to 1. Since the relation is proven modulo $q$, one must make sure that the coefficients are $\mathbf{m}$ are also proven binary. For simplicity, we do not take this into account in the estimations of Table H.1. The matrices $\mathbf{A}_i$ are uniform in $\mathbb{Z}_q^{n \times m}$, but the commitment key matrices $\mathbf{D}_i$ are uniform in $\mathbb{Z}_q^{2n \times 2m}$. We define $\mathbf{H} = \mathbf{I}_{2n} \otimes [2^0 \dots 2^{k-1}]$. Since the binary decomposition operator is non-linear, the verification equation has to be splitted into two equations as follows.

$$ \begin{cases} \mathbf{A}\mathbf{v}_1 + \mathbf{A}_0\mathbf{v}_2 + \sum_{i \in [\ell]} \mathbf{A}_i(\tau[i]\mathbf{v}_2) - \mathbf{D}\mathbf{w} = \mathbf{u} \bmod q, \\ \mathbf{H}\mathbf{w} = \mathbf{D}_0\mathbf{r} - \sum_{i \in [N]} \mathbf{D}_i\mathbf{m}_i \bmod q, \end{cases} $$

with $\|\mathbf{v}_1\|_{\infty}, \|\mathbf{v}_2\|_{\infty} \le \sigma \log_2 m$, $\|\mathbf{r}\|_{\infty} \le \sigma_1 \log_2 2m$ as well as $\tau \in \{0, 1\}^{\ell}, \mathbf{m} \in \{0, 1\}^{2mN}$, and $\mathbf{w} \in \{0, 1\}^{2nk}$. We define $\alpha, \alpha_1, k_\alpha, k_{\alpha_1}, \mathbf{g}_\alpha, \mathbf{g}_{\alpha_1}$ in a similar way as Section F. We then define $\mathbf{a} = \alpha \mathbf{1}_m, \mathbf{a}_1 = \alpha_1 \mathbf{1}_{2m}$ and set $\mathbf{G}_\alpha = \mathbf{I}_m \otimes \mathbf{g}_\alpha$ and $\mathbf{G}_{\alpha_1} = \mathbf{I}_{2m} \otimes \mathbf{g}_{\alpha_1}$. Then, we define $\mathbf{u}_i = \mathbf{A}_i \mathbf{v}_2 \in \mathbb{Z}^n$, as well as $\mathbf{u}'_i = \tau[i]\mathbf{u}_i$ constituting $2\ell$ vectors$^{12}$ of $\mathbb{Z}^n$. The verification equations thus become

$$ \begin{cases} \mathbf{A}\mathbf{G}_\alpha \overline{\mathbf{v}}_1 + \mathbf{A}_0\mathbf{G}_\alpha \overline{\mathbf{v}}_2 + \sum_{i \in [\ell]} \mathbf{u}'_i - \mathbf{D}\mathbf{w} = \mathbf{u} + (\mathbf{A} + \mathbf{A}_0)\mathbf{a} \bmod q, \\ \mathbf{D}_0\mathbf{G}_{\alpha_1} \overline{\mathbf{r}} + \sum_{i \in [N]} \mathbf{D}_i\mathbf{m}_i - \mathbf{H}\mathbf{w} = \mathbf{D}_0\mathbf{a}_1 \bmod q, \\ \mathbf{A}_i\mathbf{G}_\alpha \overline{\mathbf{v}}_2 - \mathbf{u}_i = \mathbf{A}_i\mathbf{a} \quad \text{for all } i \in [\ell], \end{cases} $$

We thus define $\mathbf{x} = [\tau|\overline{\mathbf{v}}_1|\overline{\mathbf{v}}_2|\mathbf{u}_1|\dots|\mathbf{u}_\ell|\mathbf{u}'_1|\dots|\mathbf{u}'_\ell|\mathbf{w}|\overline{\mathbf{r}}|\mathbf{m}_1|\dots|\mathbf{m}_N] \in \mathbb{Z}^{L_\mathbf{x}}$, where $L_\mathbf{x} = \ell + 2mk_\alpha + 2\ell n + m + 2mk_{\alpha_1} + 2mN$. We then define

$$ \overline{\mathbf{A}} = \begin{bmatrix} 0 & \mathbf{A}\mathbf{G}_\alpha & \mathbf{A}_0\mathbf{G}_\alpha & 0 & \dots & 0 & \mathbf{I}_n & \dots & \mathbf{I}_n & -\mathbf{D} & 0 & \dots & 0 \\ & & & & & & & & & & & & \\ & & \mathbf{A}_1\mathbf{G}_\alpha & -\mathbf{I}_n & & & & & & & & & \\ & & & \vdots & & \ddots & & & & & & & & \\ & & & & \mathbf{A}_\ell\mathbf{G}_\alpha & & & & & -\mathbf{I}_n & & & & \end{bmatrix}, $$

<footnote>$^{12}$ Each bit of the tag not only represents a witness in itself but also entails two full intermediate witnesses $\mathbf{u}_i, \mathbf{u}'_i$ due to $\tau[i]\mathbf{v}_2$. It leads to a much larger witness vector, which is a source of inefficiencies.</footnote>
and

$$ y = \begin{bmatrix} \mathbf{u} + (\mathbf{A} + \mathbf{A}_0)\mathbf{a} \\ \mathbf{D}_0\mathbf{a}_1 \\ \mathbf{A}_1\mathbf{a} \\ \vdots \\ \mathbf{A}_\ell\mathbf{a} \end{bmatrix}. $$

Finally, we define $M_1 = \{(i, i, i); i \in [\ell+2mk_\alpha] \cup [\ell+2mk_\alpha+2\ell n+1, L]\}$, which corresponds to having all the coefficients of $\mathbf{x}$ to be binary, except for the $\mathbf{u}_i, \mathbf{u}_i'$. We then need to add the relations $\mathbf{u}_i' = \tau[i]\mathbf{u}_i$ for $i \in [\ell]$. For that, we define

$M_2 = \{(\ell+2mk_\alpha+\ell n+n(i-1)+j, i, \ell+2mk_\alpha+n(i-1)+j); (i, j) \in [\ell] \times [n]\}$, and construct $M = M_1 \cup M_2$. The witness has length $L_x$, and $M$ is of size $L_x - \ell n$ as well. The fast mode of Section 4.2 reduces the witness and relation set sizes to

$$ \left\{ \begin{array}{l} L_x = \ell(2n+1) + m(5+2N) + k(2\lfloor\log_2(2\sigma\sqrt{m}\log_2\lambda)\rfloor \\ \qquad + \lfloor\log_2(2\sigma_1\sqrt{2m}\log_2\lambda)\rfloor + 3) \\ L_M = L_x - \ell n - 4m, \end{array} \right. $$

where $k = \lambda/\log_2(9/5)$ according to Lemma 4.1.

## G A Stateless Variant

We now describe how to obtain a stateless version of our signature scheme of Section 3. We describe it for the module version at a high level only. To obtain a stateless variant, one need to find a way to generate tags without encountering collisions to only emit one signature per tag, and without enduring an exponential loss in the security proof due to guesses. The first constraint imposes an exponentially large tag space, which at first glance seems incompatible with the second constraint. To meet the second constraint, we use the prefix guessing method used in [LLM+16] which we refine to avoid a blowup in the key size and subsequent zero-knowledge proofs. At a high level, when guessing a tag $\tau \in \{0, 1\}^\ell$ in [LLM+16], the authors guess the longest prefix among the emitted tags $\tau^{(i)}$ that will match with the prefix of the tag $\tau^*$ used in the type I forgery. In our case, our tag is a single element of $S_{bin}$ which voids this method as each bit would need to be multiplied to a different matrix $\mathbf{A}_i$ to cancel the gagdet $\mathbf{G}$ when $\tau = \tau^*$ in order to obtain a M-SIS solution.

To mimic the prefix guessing, we remove the Hamming weight condition on the tag $\tau \in S_{bin}$ and instead decompose it into $k$ parts, say $k = 4$, as follows. Sample $\tau_1, \dots, \tau_4$ uniformly at random in $\sum_{i=0}^{n/4-1} \{0, 1\} \cdot X^i$. To construct the trapdoor matrix $\mathbf{A}_\tau$, compute $\mathbf{A}_\tau = [\mathbf{A} | \sum_{i \in [4]} \tau_i \mathbf{B}_i - \mathbf{B}]$ where $\mathbf{B}_i = X^{(i-1)n/4} \mathbf{G} - \mathbf{A} \mathbf{R}_i \bmod qR$. The $\mathbf{B}_i$ are added to the public key, and the $\mathbf{R}_i$ to the secret key. We then have

$$ \mathbf{A}_{\tau} = [\mathbf{A} | \tau \mathbf{G} - \mathbf{A}(\mathbf{R} + \sum_{i \in [4]} \tau_i \mathbf{R}_i)]. $$
Since $\tau = \tau_1 + \tau_2 X^{n/4} + \tau_3 X^{n/2} + \tau_4 X^{3n/4} \in S_{bin} \subset R_q^\times$, we can indeed sample preimages using the modified trapdoor $\mathbf{R}_\tau = \mathbf{R} + \sum_i \tau_i \mathbf{R}_i$. This has the effect of requiring a slightly larger Gaussian width as a result because we must replace $\|\mathbf{R}\|_2$ by

$$ \begin{aligned} \|\mathbf{R}_\tau\|_2 &\le \|\mathbf{R}\|_2 + \sum_{i \in [4]} \|\tau_i\|_1 \|\mathbf{R}_i\|_2 \\ &\le (1+n) \cdot (\sqrt{nm_1} + \sqrt{nm_2} + t). \end{aligned} $$

It thus entails a mild increase in $\sigma$, which only affects the width of $\mathbf{v}_2$ in the signature as the width $\sigma_1$ for $\mathbf{v}_1$ smoothes out this increase by requiring $\sigma_1 \ge \|\mathbf{U}\mathbf{m}\|_2$ which is generally larger for a big enough $m_3$. Regardless, the factor $n$, typically 256, only adds $\log_2 n$ bits to each coefficient.

With this modification, we can use the prefix guessing method. Concretely, as in [LLM$^{+16}$], we simply make a guess on the length $\ell^+$ of the longest prefix common to the forgery tag and the ones from the signature queries. In our case, this guess is correct with probability $1/k$. We thus only have to guess the value of $\tau_{\ell^+ + 1}^*$ and construct the key material accordingly. We will thus hide the guessed prefix in the matrix $\mathbf{B}$, and generate the $\mathbf{B}_i$ simply as $\mathbf{B}_i = \mathbf{A}\mathbf{R}_i$ for the indices $i$ beyond the prefix length. With this method, we only have a security loss of $k2^{n/k}$ while having an exponentially large tag space of size $2^n$.

# H Parameters and Efficiency

In this section, we instantiate the two versions of our signature scheme with concrete parameters in order to reach $\lambda = 128$ bits of quantum security. All the concrete hardness estimates for the SIS, LWE, M-SIS, M-LWE problems are done with the Core-SVP methodology, using the BKZ cost model with sieving SVP oracle. In this model, the classical security is given by $\lambda_c = 0.292b$ [BDGL16] and the quantum security by $\lambda_q = 0.265b$ [Laa15], where $b$ is the BKZ blocksize. We explain our choice of parameters for both the standard and module version by encompassing the zero-knowledge arguments of message-signature possession. We however note that for a standard use of the signature schemes, one could choose different parameters. We choose to instantiate it for $Q = 2^{30}$ signature queries, representing the number of signature issuance. We believe this choice is reasonable for most applications.

## H.1 Instantiating the Standard Signature

We provide in Table H.2 an example parameter set along with the size of the keys, signature, and proof of possession for the signature of Section 3. It makes use of the zero-knowledge framework of [YAZ$^{+19}$] improved with the enhanced fast mode from Section 4.2 and the optimizations of Appendix E (except the compacted commitments, as explained below) that we have introduced.
As explained in Remark F.1, in order to have as few iterations of the proof system as possible, we need to choose large enough challenges, which in turns require to take a sufficiently large modulus. We then start by choosing the number of iterations $N$ and the challenge size $p$, which imply we must take $q \ge \text{poly}(\lambda) \cdot p^2$. To avoid an exponential reduction loss, we set $q' \approx Q$. We then fix $n$ so that when the other parameters are set using Algorithm 3.1, we obtain a quantum security of $\lambda$. Since the proofs of Lemma 3.2 and 3.3 both have a reduction loss between the advantage of a signature forger ($\delta = 2^{-\lambda}$) and the advantage against SIS (Adv[$\mathcal{B}$]) which can be substantial, we need to take it into account. More precisely, we compute the required SIS security $\lambda_I, \lambda_{II}$ so that the SIS problem stays hard even with the relations of Lemma 3.2 and 3.3. For our parameter, we need $\lambda_I = 189$ and $\lambda_{II} = 181$ for the respective SIS problems which only slightly differ by their bounds. Hence, we must reach for a root Hermite factor of $\delta_0 = 1.0026$. We also account for key recovery attacks, consisting of recovering $\mathbf{R}$ from $\mathbf{A}, \mathbf{B}$. This attack is however much more costly than forgeries as $\mathbf{R}$ is statistically hidden in $(\mathbf{A}, \mathbf{B})$ by the leftover hash lemma. We then set the other parameters of the zero-knowledge argument as described in our optimized framework in Appendix E and taking $\ell_1, \ell_2$ to reach 128 bits of quantum security for the HNF-SIS and HNF-LWE problems. The security estimates of HNF-LWE are performed using the estimator of Albrecht et al. [APS15]. We note that although we take the secret and error ternary from distribution $\psi_1$, we are never in the regime of polynomial algebraic attacks [AG11]. Such attacks for ternary error would require roughly $\ell_2^3$ samples. In our cases, we have $\ell_1 + \max(L_X, L_M) \ll \ell_2^2$.

We also instantiate the scheme of [LLM$^{+16}$]. For a fair comparison, we aim for the same security and make use of the same improvements of the zero-knowledge argument. The relation of [LLM$^{+16}$] is instantiated in the framework of [YAZ$^{+19}$] in Appendix F.3.

For both our scheme and the one from [LLM$^{+16}$], the ZKAoK are instantiated to be run twice, and thus do not include the compacted commitments discussed in Appendix E. Table 1.1 shows the construction of [LLM$^{+16}$] leads to intractable parameters and key sizes. We note that one could reduce the value of $q$ at the expense of increasing the number of proof iterations to achieve negligible soundness. However, not only does this approach still leads to intractable key sizes, but it also yields substantially larger proofs. Our results also summarized in Table 1.1 shows the feasibility of signature with efficient protocols based on lattice assumptions, as we gain several orders of magnitude in the size of key materials and proof size, while maintaining the same security. The complete parameter sets used to obtained these results can be found in Tables H.1 and H.2.

<footnote>*Remark H.1.* We recall that, although the fast mode reduces the size of the witness vector, it also introduces a soundness gap, which is the object of Lemma 4.1. As a result, the bounds on $v_1^*, v_2^*$ used in Lemma 3.2 and 3.3 are larger as discussed in Remark 4.1. We thus take this increase of the SIS bounds into account when estimating the SIS security, which entails an increase of the dimension $n$.</footnote>
## H.2 Instantiating the Module Signature

We now rely on the framework of [LNP22] for the zero-knowledge argument. The module construction no longer suffers from the requirement of a large modulus. Indeed, in the module case, we can choose an exponentially large challenge space while keeping the size of the challenges constant. The same thing occurs for our tag space. Before, we needed to take $q \ge q'$ where $q'$ was both the bound on the tags and the size of the tag space. In the module case, we can take binary tags while adjusting the value of $w$ in order to have a sufficiently large tag space, i.e., $|\mathcal{T}_w| \ge Q$. Additionally, because the modulus of the signature $q$ is different from the modulus of the proof system $q_\pi = q_1q$, we can first adjust the parameters of our signature before setting the parameters of the proof system. We proceed as in the previous section, accounting for the reduction loss of Lemma 3.5 and 3.6. To choose the parameters of the proof system, we proceed as prescribed in [LNP22, Sec. 6.1], with the challenge space of [LNP22, Fig. 3]. For simplicity, we choose parameters close to those provided in their group signature instantiation. We give the detailed parameter set in Table H.3 with security and efficiency estimates. To avoid collision between our notations and the proof system parameters, we specify the notations used in [LNP22] in the description column.

This construction based on structured lattices leads to drastic efficiency gains in both key and proof sizes as summarized in Table 1.1, which further reinforce the concrete feasibility of efficient privacy-enhancing post-quantum signatures. In particular, it shows that a proof of knowledge of a signature issued on a committed (secret value), one of the main building blocks of privacy-preserving primitives, can represent less than 700 KB, which is a considerable improvement over [LLM+16] and may have many applications.

**Instantiating the Anonymous Credentials.** The anonymous credentials follows exactly the same process as for the module signature. The only difference is that we in addition require the hardness of M-ISIS$_{d,2d,q,\sqrt{2nd}}$. The parameters of our signature already overshot the hardness of the latter. We give an example for a vector of 10 attributes of 128 bits each, and the proof size corresponds to the non-interactive transcript size when $|\mathcal{I}| = 4$ attributes are revealed. The message $\tilde{m}$ thus has dimension $m_3 = 2d + 10$. All the parameters and efficiency estimates of the anonymous credentials are given in Table H.4. We achieve satisfactory sizes of less than 750 KB. Improving our SEP scheme would directly result in similar improvements to the anonymous credentials system.

## H.3 Parameter Sets
<table><caption>**Table H.1.** Selected parameters, security and efficiency estimates of the signature scheme of [LLM$^{+}$16].</caption><thead><tr><th>Parameters</th><th>Description</th><th>Exact Proof</th><th>Fast Mode</th></tr></thead><tbody><tr><td colspan="4" style="text-align:center; font-weight:bold;">Signature</td></tr><tr><td>λ</td><td>Security parameter</td><td>128</td><td>128</td></tr><tr><td>n</td><td>SIS dimension</td><td>1650</td><td>2550</td></tr><tr><td>q</td><td>Modulus</td><td>2<sup>155</sup> - 31</td><td>2<sup>155</sup> - 31</td></tr><tr><td>ℓ</td><td>Tag bit-size (λ + 2 log<sub>2</sub> Q)</td><td>188</td><td>188</td></tr><tr><td>m</td><td>Trapdoor dimension</td><td>511500</td><td>790500</td></tr><tr><td>N<sub>msg</sub></td><td>Number of message blocks</td><td>1</td><td>1</td></tr><tr><td>σ</td><td>Pre-image sampling width</td><td>24324</td><td>32014</td></tr><tr><td>σ<sub>1</sub></td><td>Commitment randomness width</td><td>50335037584951</td><td>127285811917979</td></tr><tr><td>λ<sub>I</sub>/λ<sub>I</sub><sup>*</sup></td><td>Required/Reached SIS security (I)</td><td>166/167</td><td>166/167</td></tr><tr><td>λ<sub>II</sub>/λ<sub>II</sub><sup>*</sup></td><td>Required/Reached SIS security (II)</td><td>158/163</td><td>158/170</td></tr><tr><td>λ<sub>III</sub>/λ<sub>III</sub><sup>*</sup></td><td>Required/Reached SIS security (III)</td><td>128/506</td><td>128/629</td></tr><tr><td>|pk|</td><td>Public key size (MB)</td><td>2963 · 10<sup>3</sup> MB</td><td>7076 · 10<sup>3</sup> MB</td></tr><tr><td>|sk|</td><td>Secret key size (MB)</td><td>1559 · 10<sup>1</sup> MB</td><td>3725 · 10<sup>1</sup> MB</td></tr><tr><td>|sig|</td><td>Signature size (KB)</td><td>8617 KB</td><td>13895 KB</td></tr><tr><td>|pp|</td><td>Public parameters size (MB)</td><td>1640 · 10<sup>1</sup> MB</td><td>3917 · 10<sup>1</sup> MB</td></tr><tr><td colspan="4" style="text-align:center; font-weight:bold;">Proof</td></tr><tr><td>ℓ<sub>1</sub></td><td>HNF-SIS dimension</td><td>8350</td><td>8000</td></tr><tr><td>ℓ<sub>2</sub></td><td>HNF-LWE dimension</td><td>7900</td><td>7900</td></tr><tr><td>p</td><td>Size of challenges</td><td>2<sup>λ/2</sup></td><td>2<sup>λ/2</sup></td></tr><tr><td>N</td><td>Number of proof iterations</td><td>2</td><td>2</td></tr><tr><td>M</td><td>Rejection sampling repetition rate</td><td>27</td><td>27</td></tr><tr><td>L<sub>x</sub></td><td>Witness length</td><td>74788088</td><td>6510457</td></tr><tr><td>L<sub>M</sub></td><td>Relation set length</td><td>74477888</td><td>2869057</td></tr><tr><td>δ<sub>s</sub></td><td>Soundness error</td><td>2<sup>-λ</sup></td><td>2<sup>-λ</sup></td></tr><tr><td>λ<sub>SIS,π</sub><sup>*</sup></td><td>Reached HNF-SIS security</td><td>128</td><td>129</td></tr><tr><td>λ<sub>LWE,π</sub><sup>*</sup></td><td>Reached HNF-LWE security</td><td>130</td><td>130</td></tr><tr><td>|π|</td><td>Proof size (KB)</td><td>10198709 KB</td><td>671581 KB</td></tr></tbody></table>
<table><caption>**Table H.2.** Selected parameters, security and efficiency estimates of the signature scheme of Section 3.</caption><thead><tr><th>Parameters</th><th>Description</th><th>Exact Proof</th><th>Fast Mode</th></tr></thead><tbody><tr><td colspan="4" style="text-align: center; font-weight: bold;">Signature</td></tr><tr><td>λ</td><td>Security parameter</td><td>128</td><td>128</td></tr><tr><td>n</td><td>SIS dimension</td><td>495</td><td>795</td></tr><tr><td>q</td><td>Modulus</td><td>2<sup>155</sup> - 31</td><td>2<sup>155</sup> - 31</td></tr><tr><td>q'</td><td>Tag bound</td><td>2<sup>31</sup></td><td>2<sup>31</sup></td></tr><tr><td>m<sub>1</sub></td><td>First trapdoor dimension</td><td>48732</td><td>78070</td></tr><tr><td>m<sub>2</sub></td><td>Second trapdoor dimension</td><td>76725</td><td>123225</td></tr><tr><td>m<sub>3</sub></td><td>Message bit-size</td><td>128</td><td>128</td></tr><tr><td>t</td><td>Spectral norm slack</td><td>7.5</td><td>7.5</td></tr><tr><td>σ</td><td>Pre-image sampling width</td><td>6015.41</td><td>7595.30</td></tr><tr><td>σ<sub>1</sub></td><td>√σ<sup>2</sup> + σ<sub>2</sub><sup>2</sup></td><td>6015.42</td><td>7595.31</td></tr><tr><td>σ<sub>2</sub></td><td>Commitment randomness width</td><td>12.73</td><td>12.73</td></tr><tr><td>λ<sub>I</sub>/λ<sub>I</sub><sup>*</sup></td><td>Required/Reached SIS security (I)</td><td>158/190</td><td>158/189</td></tr><tr><td>λ<sub>II</sub>/λ<sub>II</sub><sup>*</sup></td><td>Required/Reached SIS security (II)</td><td>182/190</td><td>182/189</td></tr><tr><td>|pk|</td><td>Public key size (MB)</td><td>1148 MB</td><td>2956 MB</td></tr><tr><td>|sk|</td><td>Secret Key size (MB)</td><td>892 MB</td><td>2293 MB</td></tr><tr><td>|sig|</td><td>Signature size (KB)</td><td>261 KB</td><td>418 KB</td></tr><tr><td>|pp|</td><td>Public parameters size (MB)</td><td>1.2 MB</td><td>1.9 MB</td></tr><tr><td colspan="4" style="text-align: center; font-weight: bold;">Proof</td></tr><tr><td>l<sub>1</sub></td><td>HNF-SIS dimension</td><td>7850</td><td>7500</td></tr><tr><td>l<sub>2</sub></td><td>HNF-LWE dimension</td><td>7850</td><td>7850</td></tr><tr><td>p</td><td>Size of challenges</td><td>2<sup>λ/2</sup></td><td>2<sup>λ/2</sup></td></tr><tr><td>N</td><td>Number of proof iterations</td><td>2</td><td>2</td></tr><tr><td>M</td><td>Rejection sampling repetition rate</td><td>27</td><td>27</td></tr><tr><td>L<sub>x</sub></td><td>Witness length</td><td>2259407</td><td>210777</td></tr><tr><td>L<sub>M</sub></td><td>Relation set length</td><td>2258911</td><td>8686</td></tr><tr><td>δ<sub>s</sub></td><td>Soundness error</td><td>2<sup>-λ</sup></td><td>2<sup>-λ</sup></td></tr><tr><td>λ<sub>SIS,π</sub><sup>*</sup></td><td>Reached HNF-SIS security</td><td>128</td><td>129</td></tr><tr><td>λ<sub>LWE,π</sub><sup>*</sup></td><td>Reached HNF-LWE security</td><td>129</td><td>129</td></tr><tr><td>|π|</td><td>Proof size (KB)</td><td>306367 KB</td><td>17662 KB</td></tr></tbody></table>
<table><caption>**Table H.3.** Selected parameters, security and efficiency estimates of the signature scheme of Section 3.3.</caption><thead><tr><th>Parameters</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td colspan="3" style="text-align:center; font-weight:bold;">Signature</td></tr><tr><td>λ</td><td>Security parameter</td><td>128</td></tr><tr><td>n</td><td>Ring degree</td><td>128</td></tr><tr><td>d</td><td>M-SIS module rank</td><td>10</td></tr><tr><td>q</td><td>Modulus</td><td>2<sup>47</sup> - 279</td></tr><tr><td>k</td><td>Number of splitting factors</td><td>4</td></tr><tr><td>w</td><td>Tag norm bound</td><td>6</td></tr><tr><td>(n/w)</td><td>Size of tag space</td><td>≈ 2<sup>32.3</sup></td></tr><tr><td>κ</td><td>Gadget matrix term</td><td>[log<sub>2</sub> q]</td></tr><tr><td>m<sub>1</sub></td><td>First trapdoor rank</td><td>620</td></tr><tr><td>m<sub>2</sub></td><td>Second trapdoor rank</td><td>470</td></tr><tr><td>m<sub>3</sub></td><td>Number of message polynomials</td><td>1</td></tr><tr><td>t</td><td>Spectral norm slack</td><td>7.5</td></tr><tr><td>σ</td><td>Pre-image sampling width</td><td>5379</td></tr><tr><td>σ<sub>1</sub></td><td>√σ<sup>2</sup> + σ<sub>2</sub><sup>2</sup></td><td>5935</td></tr><tr><td>σ<sub>2</sub></td><td>Commitment randomness width</td><td>2510</td></tr><tr><td>λ<sub>I</sub>/λ<sub>I</sub><sup>*</sup></td><td>Required/Reached M-SIS security (I)</td><td>161/192</td></tr><tr><td>λ<sub>II</sub>/λ<sub>II</sub><sup>*</sup></td><td>Required/Reached M-SIS security (II)</td><td>182/184</td></tr><tr><td>|pk|</td><td>Public key size (MB)</td><td>7.82 MB</td></tr><tr><td>|sk|</td><td>Secret Key size (MB)</td><td>8.89 MB</td></tr><tr><td>|sig|</td><td>Signature size (KB)</td><td>273 KB</td></tr><tr><td>|pp|</td><td>Public parameters size (MB)</td><td>0.007 MB</td></tr><tr><td colspan="3" style="text-align:center; font-weight:bold;">Proof</td></tr><tr><td>d'</td><td>Height of commitment matrices A<sub>1</sub>, A<sub>2</sub> (n)</td><td>17</td></tr><tr><td>q<sub>1</sub></td><td>Slack Modulus (q<sub>1</sub>)</td><td>2<sup>28</sup> - 119</td></tr><tr><td>q<sub>π</sub></td><td>Proof modulus (q)</td><td>≈ 2<sup>75</sup></td></tr><tr><td>-</td><td>Bound on challenges (κ)</td><td>2</td></tr><tr><td>|C|</td><td>Size of challenge space (|C|)</td><td>≈ 2<sup>147</sup></td></tr><tr><td>σ<sub>-1</sub></td><td>Proof automorphism (σ)</td><td>σ<sub>-1</sub></td></tr><tr><td>η</td><td>Second bound on challenges (η)</td><td>72</td></tr><tr><td>ν</td><td>Randomness s<sub>2</sub> bound (ν)</td><td>1</td></tr><tr><td>-</td><td>Number of garbage terms (λ)</td><td>5</td></tr><tr><td>-</td><td>Length of s<sub>1</sub> (m<sub>1</sub>)</td><td>1092</td></tr><tr><td>-</td><td>Length of m (l)</td><td>0</td></tr><tr><td>-</td><td>Length of s<sub>2</sub> (m<sub>2</sub>)</td><td>41</td></tr><tr><td>γ<sub>1</sub></td><td>Rejection sampling constant for cs<sub>1</sub> (γ<sub>1</sub>)</td><td>5</td></tr><tr><td>γ<sub>2</sub></td><td>Rejection sampling constant for cs<sub>2</sub> (γ<sub>2</sub>)</td><td>3</td></tr><tr><td>γ<sup>(e)</sup></td><td>Rejection sampling constant for exact ARP (γ<sup>(e)</sup>)</td><td>2</td></tr><tr><td>δ<sub>s</sub></td><td>Soundness error</td><td>≈ 2<sup>-140</sup></td></tr><tr><td>λ<sub>M-SIS,π</sub><sup>*</sup></td><td>Reached M-SIS security</td><td>212</td></tr><tr><td>λ<sub>M-LWE,π</sub><sup>*</sup></td><td>Reached ext-M-LWE security</td><td>141</td></tr><tr><td>|π|</td><td>Proof size (KB)</td><td>639 KB</td></tr></tbody></table>
<table><caption>**Table H.4.** Selected parameters, security and efficiency estimates for the anonymous credentials of Section 5.3.</caption><thead><tr><th>Parameters</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td colspan="3" style="text-align:center; font-weight:bold;">Signature</td></tr><tr><td>λ</td><td>Security parameter</td><td>128</td></tr><tr><td>n</td><td>Ring degree</td><td>128</td></tr><tr><td>d</td><td>M-SIS module rank</td><td>12</td></tr><tr><td>q</td><td>Modulus</td><td>2<sup>44</sup> - 119</td></tr><tr><td>k</td><td>Number of splitting factors</td><td>4</td></tr><tr><td>w</td><td>Tag norm bound</td><td>6</td></tr><tr><td>(<sup>n</sup><sub>w</sub>)</td><td>Size of tag space</td><td>≈ 2<sup>32.3</sup></td></tr><tr><td>κ</td><td>Gadget matrix term</td><td>[log<sub>2</sub> q]</td></tr><tr><td>m<sub>1</sub></td><td>First trapdoor rank</td><td>657</td></tr><tr><td>m<sub>2</sub></td><td>Second trapdoor rank</td><td>528</td></tr><tr><td>m<sub>s</sub></td><td>Dimension of user secret key</td><td>24</td></tr><tr><td>m'<sub>3</sub></td><td>Number of attribute polynomials</td><td>10</td></tr><tr><td>t</td><td>Spectral norm slack</td><td>7.5</td></tr><tr><td>σ</td><td>Pre-image sampling width</td><td>5609</td></tr><tr><td>σ<sub>1</sub></td><td>√σ<sup>2</sup> + σ<sub>2</sub><sup>2</sup></td><td>26587</td></tr><tr><td>σ<sub>2</sub></td><td>Commitment randomness width</td><td>25989</td></tr><tr><td>λ<sub>I</sub>/λ<sub>I</sub><sup>*</sup></td><td>Required/Reached M-SIS security (I)</td><td>161/191</td></tr><tr><td>λ<sub>II</sub>/λ<sub>II</sub><sup>*</sup></td><td>Required/Reached M-SIS security (II)</td><td>182/183</td></tr><tr><td>|pk|</td><td>Public key size (MB)</td><td>9.56 MB</td></tr><tr><td>|sk|</td><td>Secret Key size (MB)</td><td>10.59 MB</td></tr><tr><td>|sig|</td><td>Signature size (KB)</td><td>317 KB</td></tr><tr><td>|pp|</td><td>Public parameters size (MB)</td><td>0.27 MB</td></tr><tr><td colspan="3" style="text-align:center; font-weight:bold;">Proof</td></tr><tr><td>d'</td><td>Height of commitment matrices A<sub>1</sub>, A<sub>2</sub> (n)</td><td>17</td></tr><tr><td>q<sub>1</sub></td><td>Slack Modulus (q<sub>1</sub>)</td><td>2<sup>28</sup> - 119</td></tr><tr><td>q<sub>π</sub></td><td>Proof modulus (q)</td><td>≈ 2<sup>72</sup></td></tr><tr><td>-</td><td>Bound on challenges (κ)</td><td>2</td></tr><tr><td>|C|</td><td>Size of challenge space (|C|)</td><td>≈ 2<sup>147</sup></td></tr><tr><td>σ<sub>-1</sub></td><td>Proof automorphism (σ)</td><td>σ<sub>-1</sub></td></tr><tr><td>η</td><td>Second bound on challenges (η)</td><td>72</td></tr><tr><td>ν</td><td>Randomness s<sub>2</sub> bound (ν)</td><td>1</td></tr><tr><td>-</td><td>Number of garbage terms (λ)</td><td>5</td></tr><tr><td>|I|</td><td>Number of disclosed attributes</td><td>4</td></tr><tr><td>-</td><td>Length of s<sub>1</sub> (m<sub>1</sub>)</td><td>1216</td></tr><tr><td>-</td><td>Length of m (l)</td><td>0</td></tr><tr><td>-</td><td>Length of s<sub>2</sub> (m<sub>2</sub>)</td><td>41</td></tr><tr><td>γ<sub>1</sub></td><td>Rejection sampling constant for cs<sub>1</sub> (γ<sub>1</sub>)</td><td>5</td></tr><tr><td>γ<sub>2</sub></td><td>Rejection sampling constant for cs<sub>2</sub> (γ<sub>2</sub>)</td><td>3</td></tr><tr><td>γ<sub>(e)</sub></td><td>Rejection sampling constant for exact ARP (γ<sub>(e)</sub>)</td><td>2</td></tr><tr><td>δ<sub>s</sub></td><td>Soundness error</td><td>≈ 2<sup>-140</sup></td></tr><tr><td>λ<sub>M-SIS,π</sub><sup>*</sup></td><td>Reached M-SIS security</td><td>180</td></tr><tr><td>λ<sub>M-LWE,π</sub><sup>*</sup></td><td>Reached ext-M-LWE security</td><td>149</td></tr><tr><td>|π|</td><td>Proof size (KB)</td><td>724 KB</td></tr></tbody></table>