$\mathcal{H}_7$. It proceeds exactly as in $\mathcal{H}_6$ except that it samples $\mathbf{z}_3^\mathbb{Z}$ directly from $D_{\mathbb{Z}^{256}, \sigma_3}$ instead of $\mathbf{y}_3$, and sets $\text{keep}_3 = 1$ with probability $1/M_3$ and 0 otherwise. By Lemma 2.8 and the data processing inequality of the statistical distance, it holds that $\Delta(\mathcal{H}_6, \mathcal{H}_7) \le \frac{\varepsilon_1}{M_3}$.

**Simulator S.** We now describe for completeness the simulator $\mathcal{S}$ which produces samples from $\mathcal{H}_7$ without resorting to the secret $\mathbf{s}_1$.

<figure><img src="image_11.png" /></figure>

The simulator $\mathcal{S}$ follows the construction of a transcript described in $\mathcal{H}_7$ in the honest-verifier setting. From the hybrids above, it holds that for any PPT adversary $\mathcal{A}$,

$$|\mathbb{P}[\mathcal{A}(\mathcal{H}_0) = 1] - \mathbb{P}[\mathcal{A}(\mathcal{S}) = 1]| \le \frac{\varepsilon_1}{M_1} + \frac{\varepsilon_2}{M_2} + \frac{\varepsilon_3}{M_3} + \varepsilon_{\text{Knap-M-LWE}}$$

as desired.

<figure><img src="image_12.png" /></figure>

## 7.2 Proof of Valid Credential

Algorithm 6.4 solely relies on a zero-knowledge argument for the signature verification of Algorithm 5.4. The user needs to hide its secret key, the desired attributes and the credential, while convincing the verifier that it holds such
elements. We use the same techniques as in Section 7.1, although this relation is slightly more complex as it directly involves quadratic equations. Although we use the same notations, all the parameters of the proof system in this section (e.g. $m_1, m_2, q_1, \hat{d}, \ell, \rho, \eta, \epsilon_i, M_i$) are most likely different from those of the previous protocol unless specified otherwise.

**Relation.** The prover starts by reconstructing $\mathbf{v}_1$ as in Algorithm 5.4. For clarity, we denote by $\mathbf{m}_I$ the sub-vector of attributes that are revealed and $\mathbf{m}_{sm}$ the sub-vector of concealed attributes concatenated with the secret key $\mathbf{s}$. We similarly define $\mathbf{D}_I$ and $\mathbf{D}_{sm}$ such that $\mathbf{D}_s\mathbf{s} + \mathbf{D}\mathbf{m} = \mathbf{D}_{sm}\mathbf{m}_{sm} + \mathbf{D}_I\mathbf{m}_I$. In particular, we let $m_{sm}$ be the dimension of $\mathbf{m}_{sm}$, namely $m_{sm} = m_s + (m - |I|)$. We use the same process to lift the relation modulo $\hat{q} = q_1q$ and to select the soundness amplification parameter $\ell$, and the challenge space parameters $k', \rho, \eta$. The user proves knowledge of $(\mathbf{v}_1, \mathbf{v}_2, \mathbf{v}_3, \mathbf{t}, \mathbf{m}_{sm}) \in \mathbb{R}^{2d+kd+k+1+m_{sm}}$ such that

$$ q_1 (\mathbf{A}\mathbf{v}_1 - \mathbf{B}\mathbf{v}_2 + \mathbf{A}_3\mathbf{v}_3 + \mathbf{G}(\mathbf{t}\mathbf{v}_2) - \mathbf{D}_{sm}\mathbf{m}_{sm}) = q_1 (\mathbf{u} + \mathbf{D}_I\mathbf{m}_I) \mod \hat{q}R \\ \|\mathbf{v}_1\|_2 \le B'_1, \|\mathbf{v}_2\|_2 \le B_2, \|\mathbf{v}_3\|_2 \le B_3 \\ \|\mathbf{t}\|_2 = \sqrt{w}, \mathbf{t} \in T_1, \mathbf{m}_{sm} \in T_1^{m_{sm}} $$

where $\mathbf{A} \in R_q^{d \times 2d}$, $\mathbf{B}, \mathbf{A}_3 \in R_q^{d \times k}$, $\mathbf{G} \in R_q^{d \times kd}$, $\mathbf{D}_{sm} \in R_q^{d \times m_{sm}}$, $\mathbf{D}_I \in R_q^{d \times |I|}$, $\mathbf{u} \in R_q^d$, $\mathbf{m}_I \in T_1^{|I|}$, $w, B'_1, B_2$ and $B_3$ are public elements part of the statement. We then embed everything using $\theta$ and $M_\theta$. For clarity, we define $\mathbf{A}' = q_1 M_\theta(\mathbf{A})$, $\mathbf{B}' = q_1 M_\theta(\mathbf{B})$, $\mathbf{G}' = q_1 M_\theta(\mathbf{G})$, $\mathbf{A}'_3 = q_1 M_\theta(\mathbf{A}_3)$, $\mathbf{D}'_{sm} = q_1 M_\theta(\mathbf{D}_{sm})$, and $\mathbf{u}' = q_1 \theta(\mathbf{u} + \mathbf{D}_I\mathbf{m}_I)$.

As it is needed later in the protocol, we detail how to tackle the quadratic term $\mathbf{G}'\theta(\mathbf{t}\mathbf{v}_2)$, in particular how to express its $i$-th coefficient in terms of $\theta(\mathbf{t})$ and $\theta(\mathbf{v}_2)$. Let $i \in [0, d\hat{k}-1]$. We decompose it as $i = i_1\hat{k}+i_2$ for $i_1 \in [0, d-1]$ and $i_2 \in [0, \hat{k}-1]$. We call $\mathbf{e}_i$ the vector $\hat{R}^{d\hat{k}}$ that is 1 at position $i$ and 0 elsewhere. We also call $\mathbf{e}_{i_2}$ the vector of $\hat{R}^{\hat{k}}$ that is 1 at position $i_2$ and 0 elsewhere. It holds that

$$ [\theta(\mathbf{t}\mathbf{G}\mathbf{v}_2)]_i = \mathbf{e}_i^T \theta((\mathbf{I}_d \otimes \mathbf{t})\mathbf{G}\mathbf{v}_2) = \mathbf{e}_i^T (\mathbf{I}_d \otimes M_\theta(\mathbf{t})) M_\theta(\mathbf{G}) \theta(\mathbf{v}_2). $$

We have that $\mathbf{e}_i^T (\mathbf{I}_d \otimes M_\theta(\mathbf{t})) = [\mathbf{0}_{1 \times i_1 \hat{k}} | \mathbf{e}_{i_2}^T M_\theta(\mathbf{t}) | \mathbf{0}_{1 \times (d-i_1-1)\hat{k}}]$, where the non-zero block is at the block position $i_1$. We can now express

$$ \mathbf{e}_{i_2}^T M_\theta(\mathbf{t}) = \mathrm{Row}_{i_2}(M_\theta(\mathbf{t})) = \theta(x^{\hat{k}-1-i_2} \otimes_R \mathbf{t})^T \cdot \mathbf{P} = \theta(\mathbf{t})^T M_\theta(x^{\hat{k}-1-i_2})^T \mathbf{P}, $$

where $\mathbf{P}$ is the permutation of $[0, \hat{k}-1]$ having 1 only on the anti-diagonal, i.e.,

$$ \mathbf{P} = \begin{bmatrix} 1 \\ \vdots \\ 1 \end{bmatrix}. $$

As a result, we have that $[\theta(\mathbf{t}\mathbf{G}\mathbf{v}_2)]_i$ is equal to

$$ \theta(\mathbf{t})^T \cdot [\mathbf{0}_{\hat{k} \times i_1 \hat{k}} | M_\theta(x^{\hat{k}-1-i_2})^T \mathbf{P} | \mathbf{0}_{\hat{k} \times (d-i_1-1)\hat{k}}] M_\theta(\mathbf{G}) \cdot \theta(\mathbf{v}_2), $$
which means the i-th coefficient of $\theta(q_1 \mathbf{t}\mathbf{G}\mathbf{v}_2)$ can be expressed as $\theta(t)^T \mathbf{G}'_i \theta(\mathbf{v}_2)$, where

$$ \mathbf{G}'_i = [\mathbf{0}_{\hat{k} \times i_1 \hat{k}} | M_{\theta}(x^{\hat{k}-1-i_2})^T \mathbf{P} | \mathbf{0}_{\hat{k} \times (d-i_1-1)\hat{k}}] \mathbf{G}', $$

where the non-zero block is at position $i_1$, where $i = i_1 \hat{k} + i_2$ for $i_1 \in [0, d-1]$ and $i_2 \in [0, \hat{k}-1]$. In the remainder of the protocol description, we define $\mathbf{v}'_j = \theta(\mathbf{v}_j)$ for $j \in [3]$, $t' = \theta(t)$, $\mathbf{m}'_{sm} = \theta(\mathbf{m}_{sm})$.

**The Protocol.** We start by expressing $B_1'^2 - \|\mathbf{v}'_1\|_2^2$ as the sum of four square integer $a_{1,0}^2 + a_{1,1}^2 + a_{1,2}^2 + a_{1,3}^2$. Then, define $a_1 = a_{1,0} + a_{1,1}x + a_{1,2}x^2 + a_{1,3}x^3$ and $\mathbf{v}''_1 = [\mathbf{v}''_1]^T |a_1|^T$ so that $\|\mathbf{v}''_1\|_2 = B_1'$. We perform the same decomposition and define $a_2, a_3, \mathbf{v}''_2, \mathbf{v}''_3$. We also define $\mathbf{A}'' = [\mathbf{A}' | \mathbf{0}_d]$, $\mathbf{B}'' = [\mathbf{B}' | \mathbf{0}_d]$, $\mathbf{G}''_i = [\mathbf{G}'_i | \mathbf{0}_{\hat{k}}]$ and $\mathbf{A}''_3 = [\mathbf{A}'_3 | \mathbf{0}_d]$. Later, we also pack the witnesses into the vector $\mathbf{s}_1 = (\mathbf{v}''_1, \mathbf{v}''_2, \mathbf{v}''_3, t', \mathbf{m}'_{sm}) \in \hat{\mathbb{R}}^{m_1}$ for $m_1 = (2d\hat{k}+1)+(kd\hat{k}+1)+(k\hat{k}+1)+\hat{k}+m_{sm}\hat{k}$. **First Round.** We start by the main commitment phase which consists in committing to the witness, masks and randomness needed in subsequent rounds. We start by sampling $\mathbf{s}_2$ from $\chi^{m_2}$ where $\text{Supp}(\chi) \subseteq \hat{S}_1$ and compute an Ajtai commitment of $\mathbf{s}_1$ with randomness $\mathbf{s}_2$ as $\mathbf{t}_A = \mathbf{A}_1\mathbf{s}_1 + \mathbf{A}_2\mathbf{s}_2 \bmod \hat{q}\hat{\mathbb{R}}$, where $\mathbf{A}_1 \leftarrow U(\hat{R}^{\hat{d}\times m_1})$ and $\mathbf{A}_2 \leftarrow U(\hat{R}^{\hat{d}\times m_2})$ are part of the common reference string crs. Then, we sample the Gaussian masks for what will later be $\mathbf{c}\mathbf{s}_1$ and $\mathbf{c}\mathbf{s}_2$. More precisely, we sample $\mathbf{y}_1$ from $\mathcal{D}_{\hat{R}^{m_1}, \sigma_1}$ and $\mathbf{y}_2$ from $\mathcal{D}_{\hat{R}^{m_2}, \sigma_2}$, and compute the commitment $\mathbf{w} = \mathbf{A}_1\mathbf{y}_1 + \mathbf{A}_2\mathbf{y}_2 \bmod \hat{q}\hat{\mathbb{R}}$.

We then sample a mask $\mathbf{y}_3$ from $\mathcal{D}_{\hat{R}^{256/\hat{n}}, \sigma_3}$ and a vector for soundness amplification by $\mathbf{g} \leftarrow U(\{x \in \hat{R}_{\hat{q}} : \tau_0(x) = 0\}^\ell)$ where all the entries are polynomials with a constant coefficient equal to zero. We later use $\hat{\mathbf{m}}$ to denote the vector $\hat{\mathbf{m}} = [\mathbf{y}_3^T | \mathbf{g}^T]^T \in \hat{\mathbb{R}}^{256/\hat{n}+\ell}$. We commit to it via $\mathbf{t}_B = \mathbf{B}_{y,g}\mathbf{s}_2 + \hat{\mathbf{m}} \bmod \hat{q}\hat{\mathbb{R}}$, where $\mathbf{B}_{y,g} \leftarrow U(\hat{R}_{\hat{q}}^{(256/\hat{n}+\ell)\times m_2})$ is part of crs.

The prover sends $\mathbf{msg}_1$ as the first message and receives $\mathbf{chal}_1$ as the first challenge, where they are both defined as

$$ \mathbf{msg}_1 = (\mathbf{t}_A, \mathbf{t}_B, \mathbf{w}) \in \hat{R}_{\hat{q}}^{2d+256/\hat{n}+\ell} $$

$$ \mathbf{chal}_1 = \mathcal{H}(1, \text{crs}, x, \mathbf{msg}_1) = (R_0, R_1) \in (\{0, 1\}^{256 \times m_1 \hat{n}})^2 $$

with $(R_0, R_1)$ conditioned on $\|R_0 - R_1\|_2 \le \sqrt{337}$.

**Second Round.** We conclude the approximate range proof part. We define $R = R_0 - R_1$. The challenge $R$ is used to project the witness onto a smaller dimensional space and prove that the coefficients of $\mathbf{s}_1$ are small relative to $\hat{q}$. In the second round, we respond to the challenge by masking $R\tau(\mathbf{s}_1)$ with $\tau(\mathbf{y}_3)$. So we compute $\mathbf{z}_3^Z = \tau(\mathbf{y}_3) + R\tau(\mathbf{s}_1) \in \mathbb{Z}^{256}$. Then, we perform rejection by sampling $u_3 \leftarrow U([0, 1])$ and rejecting if

$$ u_3 > \frac{1}{M_3} \exp \left( \pi \frac{-2 \langle \mathbf{z}_3^Z, R \tau(\mathbf{s}_1) \rangle + \|R \tau(\mathbf{s}_1)\|_2^2}{\sigma_3^2} \right). $$
If the $u_3$ is smaller, then the prover accepts, sends $msg_2$ as the second message and receives $chal_2$ as the second challenge where they are defined by

$$msg_2 = \mathbf{z}_3^Z \in \mathbb{Z}^{256}$$

$$chal_2 = \mathcal{H}(2, \text{crs}, \mathbf{x}, msg_1, msg_2) = (\gamma_{i,j})_{\substack{i \in [\ell] \\ j \in [262]}} \in \mathbb{Z}_{\hat{q}}^{\ell \times 262}.$$

**_Third Round._** We now need to prove the equations over $\mathbb{Z}_{\hat{q}}$, namely the ones related to norm constraints or binary vectors, as well as the well-formedness of $\mathbf{z}_3^Z$.

$$\tau(\mathbf{y}_3) + R\tau(\mathbf{s}_1) = \mathbf{z}_3^Z, \qquad (3.1b)$$

$$\langle \tau(\mathbf{v}_1''), \tau(\mathbf{v}_1'') \rangle = B_1'^2, \qquad (3.2b)$$

$$\langle \tau(\mathbf{v}_2''), \tau(\mathbf{v}_2'') \rangle = B_2^2, \qquad (3.3b)$$

$$\langle \tau(\mathbf{v}_3''), \tau(\mathbf{v}_3'') \rangle = B_3^2, \qquad (3.4b)$$

$$\langle \tau(\mathbf{t}'), \tau(\mathbf{t}') \rangle = w, \qquad (3.5b)$$

$$\langle \tau(\mathbf{t}'), \tau(\mathbf{t}') - \mathbf{1}_{\hat{n}\hat{k}} \rangle = 0. \qquad (3.6b)$$

$$\langle \tau(\mathbf{m}'_{sm}), \tau(\mathbf{m}'_{sm}) - \mathbf{1}_{\hat{n}\hat{k}m_{sm}} \rangle = 0. \qquad (3.7b)$$

Using the same method and notations as in Section 7.1, we combine the quadratic equations with automorphisms over $\hat{R}_{\hat{q}}$ and define for all $i \in [\ell]$

$$\begin{aligned} h_i = g_i + & \sum_{j \in [256]} \gamma_{i,j} (\mathbf{e}_j^* \mathbf{y}_3 + \mathbf{r}_j^* \mathbf{s}_1 - z_{3,j}^Z) + \gamma_{i,257} (\mathbf{v}_1''^* \mathbf{v}_1'' - B_1'^2) \\ & + \gamma_{i,258} (\mathbf{v}_2''^* \mathbf{v}_2'' - B_2^2) + \gamma_{i,259} (\mathbf{v}_3''^* \mathbf{v}_3'' - B_3^2) + \gamma_{i,260} (\mathbf{t}'^* \mathbf{t}' - w) \quad (15) \\ & + \gamma_{i,261} (\mathbf{t}'^* (\mathbf{t}' - \mathbf{1}_{\hat{R}\hat{k}})) + \gamma_{i,262} (\mathbf{m}'_{sm}^* (\mathbf{m}'_{sm} - \mathbf{1}_{\hat{R}\hat{k}m_{sm}})). \end{aligned}$$

The prover then sends $msg_3$ as the third message and receives $chal_3$ as the third challenge, where they are both defined as

$$msg_3 = (h_1, \dots, h_\ell) \in \hat{R}_{\hat{q}}^\ell$$

$$chal_3 = \mathcal{H}(3, \text{crs}, \mathbf{x}, msg_1, msg_2, msg_3) = (\mu_i)_{i \in [\ell + d\hat{k}]} \in \hat{R}_{\hat{q}}^{\ell + d\hat{k}}.$$

**_Fourth Round._** All the quadratic equations, including the equations for the well-formedness of the $h_i$ for the quadratic evaluations from the previous round, are then proven in round 4 directly over $\hat{R}_{\hat{q}}$. We need to prove that the $h_i$ are well-formed and equal their expressions above, and we also need to prove the main quadratic relation $A''\mathbf{v}_1'' - B''\mathbf{v}_2'' + A_3''\mathbf{v}_3'' - D_{sm}''\mathbf{m}_{sm} + \mathbf{t}'G''\mathbf{v}_2'' = \mathbf{u}'$. The latter represents $d\hat{k}$ equations. We prove them all at once by combining them linearly
with the challenges $\mu_i$ and prove that

$$
\begin{align}
0 = \sum_{i \in [\ell]} \mu_i & \left( g_i + \sum_{j \in [256]} \gamma_{i,j} (\mathbf{e}_j^* \mathbf{y}_3 + \mathbf{r}_j^* \mathbf{s}_1 - z_{3,j}^Z) + \gamma_{i,257} (\mathbf{v}_1^{\prime\prime *} \mathbf{v}_1^{\prime\prime} - B_1^{\prime 2}) \right. \nonumber \\
& \left. \qquad + \gamma_{i,258} (\mathbf{v}_2^{\prime\prime *} \mathbf{v}_2^{\prime\prime} - B_2^2) + \gamma_{i,259} (\mathbf{v}_3^{\prime\prime *} \mathbf{v}_3^{\prime} - B_3^2) + \gamma_{i,260} (\mathbf{t}^{\prime *} \mathbf{t}^{\prime} - w) \right. \tag{16} \\
& \qquad \left. + \gamma_{i,261} (\mathbf{t}^{\prime *} (\mathbf{t}^{\prime} - \mathbf{1}_{\hat{R}^k})) + \gamma_{i,262} (\mathbf{m}_{sm}^{\prime *} (\mathbf{m}_{sm}^{\prime} - \mathbf{1}_{\hat{R}^{k_{sm}}})) - h_i \right) \nonumber \\
& + \sum_{i \in [d\hat{k}]} \mu_{\ell+i} (\mathbf{t}^{\prime T} \mathbf{G}_i^{\prime\prime} \mathbf{v}_2^{\prime\prime} + \mathbf{e}_i^{\hat{R}^T} (\mathbf{A}^{\prime\prime} \mathbf{v}_1^{\prime\prime} - \mathbf{B}^{\prime\prime} \mathbf{v}_2^{\prime\prime} + \mathbf{A}_3^{\prime\prime} \mathbf{v}_3^{\prime\prime} - \mathbf{D}_{sm}^{\prime} \mathbf{m}_{sm}^{\prime} - \mathbf{u}^{\prime})). \nonumber
\end{align}
$$

For that let us define $\hat{s} = [\mathbf{s}_1^T | \mathbf{s}_1^* | \hat{\mathbf{m}}^T | \hat{\mathbf{m}}^*]^T$. We also define $\mathbf{r}_{1,j}$, $\mathbf{r}_{2,j}$, $\mathbf{r}_{3,j}$, $\mathbf{r}_{t,j}$, and $\mathbf{r}_{sm,j}$ such that

$$
\mathbf{r}_j^* \mathbf{s}_1 = \mathbf{r}_{1,j}^* \mathbf{v}_1'' + \mathbf{r}_{2,j}^* \mathbf{v}_2'' + \mathbf{r}_{3,j}^* \mathbf{v}_3'' + \mathbf{r}_{t,j}^* \mathbf{t}' + \mathbf{r}_{sm,j}^* \mathbf{m}_{sm}''
$$

Then, the equation to be proven is equivalent to $\hat{s}^T F \hat{s} + f^T \hat{s} + f = 0 \mod \hat{q}\hat{R}$, where

$$
f = - \sum_{i \in [\ell]} \mu_i \left( \sum_{j \in [256]} \gamma_{i,j} z_{3,j}^Z + \gamma_{i,257} B_1^{\prime 2} + \gamma_{i,258} B_2^2 + \gamma_{i,259} B_3^2 + \gamma_{i,260} w + h_i \right) \\
- \sum_{i \in [d\hat{k}]} \mu_{\ell+i} u_i' \\
\mathbf{f} = \begin{bmatrix}
\sum_{i \in [\ell]} \sum_{j \in [256]} \mu_i \gamma_{i,j} \mathbf{r}_{1,j}^{*T} + \sum_{i \in [d\hat{k}]} \mu_{\ell+i} \mathbf{A}^{\prime\prime T} \mathbf{e}_i^{\hat{R}} \\
\sum_{i \in [\ell]} \sum_{j \in [256]} \mu_i \gamma_{i,j} \mathbf{r}_{2,j}^{*T} - \sum_{i \in [d\hat{k}]} \mu_{\ell+i} \mathbf{B}^{\prime\prime T} \mathbf{e}_i^{\hat{R}} \\
\sum_{i \in [\ell]} \sum_{j \in [256]} \mu_i \gamma_{i,j} \mathbf{r}_{3,j}^{*T} + \sum_{i \in [d\hat{k}]} \mu_{\ell+i} \mathbf{A}_3^{\prime\prime T} \mathbf{e}_i^{\hat{R}} \\
\sum_{i \in [\ell]} \sum_{j \in [256]} \mu_i \gamma_{i,j} \mathbf{r}_{t,j}^{*T} \\
\sum_{i \in [\ell]} \sum_{j \in [256]} \mu_i \gamma_{i,j} \mathbf{r}_{sm,j}^{*T} + \sum_{i \in [d\hat{k}]} \mu_{\ell+i} \mathbf{D}_{sm}^{\prime T} \mathbf{e}_i^{\hat{R}} \\
\mathbf{0}_{2d\hat{k}+1} \\
\mathbf{0}_{kd\hat{k}+1} \\
\mathbf{0}_{k\hat{k}+1} \\
- \sum_{i \in [\ell]} \mu_i \gamma_{i,261} \mathbf{1}_{\hat{R}^{k}} \\
- \sum_{i \in [\ell]} \mu_i \gamma_{i,262} \mathbf{1}_{\hat{R}^{k_{sm}}} \\
\sum_{i \in [\ell]} \mu_i \sum_{j \in [256]} \gamma_{i,j} \mathbf{e}_j^{*T} \\
[\mu_1] \dots [\mu_\ell]^T \\
\mathbf{0}_{256/\hat{n}} \\
\mathbf{0}_\ell
\end{bmatrix} \tag{17}
$$

$$
\mathbf{F} = \begin{bmatrix} \mathbf{F}' & \mathbf{F}'' & \mathbf{0}_{m_1 \times 2(256/\hat{n}+\ell)} \\ \mathbf{0}_{m_1+2(256/\hat{n}+\ell) \times 2(m_1+256/\hat{n}+\ell)} & \end{bmatrix},
$$
where

$$ \mathbf{F}' = \left[ \mathbf{0}_{\hat{k} \times 2d\hat{k}+1} \sum_{i \in [d]} \mu_{\ell+i} \mathbf{G}_i'' \mathbf{0}_{\hat{k} \times (m_1-d\hat{k}(2+k)-2)} \mathbf{0}_{\hat{k}m_{sm} \times m_1} \right], $$

and

$$ \mathbf{F}'' = \sum_{i \in [\ell]} \mu_i \cdot \operatorname{diag}(\gamma_{i,257}\mathbf{I}_{2d\hat{k}+1}, \gamma_{i,258}\mathbf{I}_{kd\hat{k}+1}, \gamma_{i,259}\mathbf{I}_{k\hat{k}+1}, \\ (\gamma_{i,260} + \gamma_{i,261})\mathbf{I}_{\hat{k}}, \gamma_{i,262}\mathbf{I}_{km_{sm}}). $$

Once we have defined these (public) matrices, we can compute the garbage terms and commit to them. More precisely, we define

$$ \mathbf{y} = \begin{bmatrix} \mathbf{y}_1 \\ \mathbf{y}_1^{*T} \\ -(\mathbf{B}_{y,g}\mathbf{y}_2)^{*T} \\ -(\mathbf{B}_{y,g}\mathbf{y}_2)^{*T} \end{bmatrix} \in \hat{R}_{\hat{q}}^{2(m_1+256/\hat{n}+\ell)}, \qquad (18) $$

and compute $e_0 = \mathbf{y}^T \mathbf{F} \mathbf{y} \bmod \hat{q} \hat{R}$, $e_1 = \hat{\mathbf{s}}^T \mathbf{F} \mathbf{y} + \mathbf{y}^T \mathbf{F} \hat{\mathbf{s}} + \mathbf{f}^T \mathbf{y} \bmod \hat{q} \hat{R}$, and the commitments $t_0 = \mathbf{b}^T \mathbf{y}_2 + e_0 \bmod \hat{q} \hat{R}$ and $t_1 = \mathbf{b}^T \mathbf{s}_2 + e_1 \bmod \hat{q} \hat{R}$, where $\mathbf{b} \leftarrow U(\hat{R}_{\hat{q}}^{m_2})$ is part of $\mathbf{crs}$. The prover then sends $\mathbf{msg}_4$ as the fourth message and receives $\mathbf{chal}_4$ as the fourth challenge, where they are both defined as

$$ \mathbf{msg}_4 = (t_0, t_1) \in \hat{R}_{\hat{q}}^2 \\ \mathbf{chal}_4 = \mathcal{H}(4, \mathbf{crs}, \mathbf{x}, \mathbf{msg}_1, \mathbf{msg}_2, \mathbf{msg}_3, \mathbf{msg}_4) = c \in \mathcal{C}. $$

**Fifth Round.** The final round consists in the final response that is typical of Schnorr-like proofs, i.e., outputting $z = y + c \cdot s$ without it leaking information. More precisely, the prover responds to the challenge by masking $\mathbf{cs}_1$ and $\mathbf{cs}_2$ with $\mathbf{y}_1$ and $\mathbf{y}_2$ respectively. So we compute $\mathbf{z}_1 = \mathbf{y}_1 + \mathbf{cs}_1$ and $\mathbf{z}_2 = \mathbf{y}_2 + \mathbf{cs}_2$. Then, we perform rejection by sampling $u_1, u_2 \leftarrow U([0, 1))$ and rejecting if

$$ u_1 > \frac{1}{M_1} \exp \left( \pi \frac{-2 \langle \tau(\mathbf{z}_1), \tau(\mathbf{cs}_1) \rangle + \|\tau(\mathbf{cs}_1)\|_2^2}{\sigma_1^2} \right) \\ \text{or } u_2 > \frac{1}{M_2} \exp \left( \pi \frac{-2 \langle \tau(\mathbf{z}_2), \tau(\mathbf{cs}_2) \rangle + \|\tau(\mathbf{cs}_2)\|_2^2}{\sigma_2^2} \right). $$

If the $u_1, u_2$ are both smaller than these respective bounds, then the prover accepts, sends $\mathbf{msg}_5$ as the final message defined by

$$ \mathbf{msg}_5 = (\mathbf{z}_1, \mathbf{z}_2) \in \hat{R}^{m_1+m_2}. $$

**Non-Interactive Proof.** We summarize the proof and verification in Figure 7.2. The proof is $\pi = (\mathbf{t}_A, \mathbf{t}_B, \mathbf{z}_3^z, h_1, \dots, h_\ell, t_1, c, \mathbf{z}_1, \mathbf{z}_2)$ as the elements $\mathbf{w}$ and $t_0$ and the challenges can be re-computed from the rest. The elements
$t_A, t_B, h_1, \dots, h_\ell, t_1$ cannot be compressed as they all look uniformly random modulo $q_\pi$. We again use the entropy bound to evaluate the bit-size of discrete Gaussian vectors. It means the total bit-size can be bounded by

$$|\pi| \le \left( \hat{d} + \frac{256}{\hat{n}} + 2\ell + 1 \right) \hat{n}[\log_2 \hat{q}] + \hat{n}m_1(1/2 + \log_2 \sigma_1) \\ + \hat{n}m_2(1/2 + \log_2 \sigma_2) + 256(1/2 + \log_2 \sigma_3) + \hat{n}[\log_2(2\rho + 1)].$$

### Proof

keep $\leftarrow 0$

while keep $= 0$ do

$s_2 \leftarrow \chi^{m_2}$

$t_A \leftarrow A_1s_1 + A_2s_2 \mod \hat{q}\hat{R}$

$y_i \leftarrow D_{\hat{R}^{m_1}, \sigma_1}$ for $i \in \{1, 2\}$

$w \leftarrow A_1y_1 + A_2y_2 \mod \hat{q}\hat{R}$

$y_3 \leftarrow D_{\hat{R}^{256/\hat{n}}, \sigma_3}$

$g \leftarrow U(\{x \in \hat{R}_q : \tau_0(x) = 0\}^\ell)$

$t_B \leftarrow B_{y,g}s_2 + [y_1^T g^T]^T \mod \hat{q}\hat{R}$

$\text{msg}_1 \leftarrow (t_A, t_B, w)$

$(R_0, R_1) \leftarrow \mathcal{H}(1, \text{crs}, x, \text{msg}_1) \in (\{0, 1\}^{256 \times m_1} \hat{n})^2$

$R \leftarrow R_0 - R_1$

$z_3^T \leftarrow \tau(y_3) - R\tau(s_1)$

$\text{keep}_3 \leftarrow \text{Rej}_1(z_3^T, R\tau(s_1), \sigma_3, M_3)$

$\text{msg}_2 \leftarrow z_3^T$

$(\gamma_{i,j}, i, j) \leftarrow \mathcal{H}(2, \text{crs}, x, \text{msg}_1, \text{msg}_2) \in \mathbb{Z}_q^{\ell \times 262}$

Compute all $h_i$ as in Equation (16)

$\text{msg}_3 \leftarrow (h_1, \dots, h_\ell)$

$(\mu_i)_{i \in [\ell + d\hat{k}]} \leftarrow \mathcal{H}(3, \text{crs}, x, \text{msg}_1, \text{msg}_2, \text{msg}_3) \in \hat{R}_q^{\ell + d\hat{k}}$

Compute $\hat{s}, y, F, f$ as in Equations (18) and (17)

$e_0 \leftarrow y^T F y \mod \hat{q}\hat{R}$

$e_1 \leftarrow \hat{s}^T F y + y^T F \hat{s} + f^T y \mod \hat{q}\hat{R}$

$t_0 \leftarrow b^T y_2 + e_0 \mod \hat{q}\hat{R}$

$t_1 \leftarrow b^T s_2 + e_1 \mod \hat{q}\hat{R}$

$\text{msg}_4 \leftarrow (t_0, t_1)$

$c \leftarrow \mathcal{H}(4, \text{crs}, x, \text{msg}_1, \text{msg}_2, \text{msg}_3, \text{msg}_4) \in C$

$z_1 \leftarrow y_1 + cs_1$

$\text{keep}_1 \leftarrow \text{Rej}_1(z_1, cs_1, \sigma_1, M_1)$

$z_2 \leftarrow y_2 + cs_2$

$\text{keep}_2 \leftarrow \text{Rej}_1(z_2, cs_2, \sigma_2, M_2)$

keep $\leftarrow \text{keep}_1 \wedge \text{keep}_2 \wedge \text{keep}_3$

$\pi \leftarrow (t_A, t_B, z_3^T, h_1, \dots, h_\ell, t_1, c, z_1, z_2)$

return $\pi$

### Verification

$w \leftarrow A_1z_1 + A_2z_2 - ct_A \mod \hat{q}\hat{R}$

$\text{msg}_1 \leftarrow (t_A, t_B, w)$

$(R_0, R_1) \leftarrow \mathcal{H}(1, \text{crs}, x, \text{msg}_1)$

$\text{msg}_2 \leftarrow z_3^T$

$(\gamma_{i,j})_{i,j} \leftarrow \mathcal{H}(2, \text{crs}, x, \text{msg}_1, \text{msg}_2)$

$\text{msg}_3 \leftarrow (h_1, \dots, h_\ell)$

$(\mu_i)_{i \in [\ell + d\hat{k}]} \leftarrow \mathcal{H}(3, \text{crs}, x, \text{msg}_1, \text{msg}_2, \text{msg}_3)$

Compute $F, f, f$ as in Equation (17)

$$z \leftarrow \begin{bmatrix} z_1 \\ z_1^T \\ ct_B - B_{y,g}z_2 \\ (ct_B - B_{y,g}z_2)^T \end{bmatrix}$$

$t_0 \leftarrow z^T F z + c^T z + c^2 f - (ct_1 - b^T z_2) \mod \hat{q}\hat{R}$

$\text{msg}_4 = (t_0, t_1)$

$b_1 \leftarrow \|z_1\|_2 \le c_{\hat{n}m_1} \sigma_1 \sqrt{\hat{n}m_1}$

$b_2 \leftarrow \|z_2\|_2 \le c_{\hat{n}m_2} \sigma_2 \sqrt{\hat{n}m_2}$

$b_3 \leftarrow \|z_3^T\|_2 \le c_{256} \sigma_3 \sqrt{256}$

$b_4 \leftarrow \forall i \in [\ell], \tau_0(h_i) = 0$

$b_5 \leftarrow \mathcal{H}(4, \text{crs}, x, \text{msg}_1, \text{msg}_2, \text{msg}_3, \text{msg}_4) = c$

return $b_1 \wedge b_2 \wedge b_3 \wedge b_4 \wedge b_5$

<caption>**Fig. 7.2.** Non-interactive zero-knowledge argument for credential showing</caption>
**Security Analysis.** The proofs of Lemmas 7.4, 7.5 and 7.6 follow the same reasoning as that of Section 7.1. As the proof is presented to be non-interactive, there are a few modifications. In the completeness, the equations that would need to be satisfied on w and t₀ are automatically verified as these elements are recovered from c in the verification. Instead, one simply need to check that c indeed corresponds to the correct hash output. For knowledge soundness and zero-knowledge, the proof in the non-interactive case follows the same arguments as e.g. [BLNS23], which only slightly differs from the proofs of Section 7.1.

**Lemma 7.4.** Let $\varepsilon_1, \varepsilon_2, \varepsilon_3$ be in $(0, 1/2]$ and $M_1, M_2, M_3$ in $(1, \infty)$. For $i \in [3]$, we define $\alpha_i = \sqrt{\pi}/\ln(M_i) \cdot (\sqrt{\ln(\varepsilon_i^{-1})} + \ln(M_i) + \sqrt{\ln(\varepsilon_i^{-1})})$. We let $B = \sqrt{B_1'^2 + B_2^2 + B_3^2 + w + nm_{sm}}$ be a bound on $\|s_1\|_2$. Let $\chi$ be a distribution over $\hat{S}_1$, and let $\sigma_1 = \alpha_1\eta B$, $\sigma_2 = \alpha_2\eta\sqrt{nm_2}$ and $\sigma_3 = \alpha_3\sqrt{337}B$. Then, the zero-knowledge argument in Figure 7.2 is complete.

**Lemma 7.5.** Let $\varepsilon_1, \varepsilon_2, \varepsilon_3$ be in $(0, 1/2]$ and $M_1, M_2, M_3$ in $(1, \infty)$. For $i \in [3]$, we define $\alpha_i = \sqrt{\pi}/\ln(M_i) \cdot (\sqrt{\ln(\varepsilon_i^{-1})} + \ln(M_i) + \sqrt{\ln(\varepsilon_i^{-1})})$. We let $B = \sqrt{B_1'^2 + B_2^2 + B_3^2 + w + nm_{sm}}$ be a bound on $\|s_1\|_2$. Then, let $\chi$ be a distribution over $\hat{S}_1$, and let $\sigma_1 = \alpha_1\eta B$, $\sigma_2 = \alpha_2\eta\sqrt{nm_2}$ and $\sigma_3 = \alpha_3\sqrt{337}B$, and define $B_{256} = c_{256}\sigma_3\sqrt{256}$. Assume that $\hat{q} > \max(B^2, 82/\sqrt{26} \cdot \hat{nm}_1 B_{256}, 2B_{256}^2/13 - B_{256})$.

Then, the zero-knowledge argument in Figure 7.2 is knowledge sound with an extractor running in expected polynomial time, and soundness error

$$ \delta = \frac{2}{|C|} + q_{\min}^{-\hat{n}/\kappa} + q_{\min}^{-\ell} + 2^{-128} + \varepsilon_{\text{M-SIS}} $$

where $\varepsilon_{\text{M-SIS}}$ is the hardness bound for M-SIS$_{\hat{n},\hat{d},m_1+m_2,\hat{q},\beta}$ for

$$ \beta = 8\eta\sqrt{(c_{\hat{n}m_1}\sigma_1\sqrt{\hat{nm}_1})^2 + (c_{\hat{n}m_2}\sigma_2\sqrt{\hat{nm}_2})^2} $$

**Lemma 7.6.** Let $\varepsilon_1, \varepsilon_2, \varepsilon_3$ be in $(0, 1/2]$ and $M_1, M_2, M_3$ in $(1, \infty)$. For $i \in [3]$, we define $\alpha_i = \sqrt{\pi}/\ln(M_i) \cdot (\sqrt{\ln(\varepsilon_i^{-1})} + \ln(M_i) + \sqrt{\ln(\varepsilon_i^{-1})})$. We let $B = \sqrt{B_1'^2 + B_2^2 + B_3^2 + w + nm_{sm}}$ be a bound on $\|s_1\|_2$. Let $\chi$ be a distribution over $S_1$, and let $\sigma_1 = \alpha_1\eta B$, $\sigma_2 = \alpha_2\eta\sqrt{nm_2}$ and $\sigma_3 = \alpha_3\sqrt{337}B$. We define $m_2' = \hat{d}+256/\hat{n}+\ell+1$ and assume that $m_2' > m_2'$. Then, the zero-knowledge argument in Figure 7.1 is zero-knowledge. More precisely, there exists a simulator S that outputs a distribution that is $\varepsilon$-indistinguishable from that of an honest proof, where

$$ \varepsilon = \frac{\varepsilon_1}{M_1} + \frac{\varepsilon_2}{M_2} + \frac{\varepsilon_3}{M_3} + 2\delta_{q_{\min}}(m_2, m_2') + \frac{\varepsilon_{\text{M-LWE}}}{1 - \delta_{q_{\min}}(m_2, m_2 - m_2')} $$

where $\varepsilon_{\text{M-LWE}}$ is the hardness bound of M-LWE$_{\hat{n},m_2-(\hat{d}+256/\hat{n}+\ell+1),m_2,\hat{q},\chi}$, and $\delta_{q_{\min}}(a, b) = \mathbb{P}_{M \sim U(\hat{R}_{q_{\min}}^{b \times a})}[\mathbf{M} \cdot \hat{R}_{q_{\min}}^{a} \neq \hat{R}_{q_{\min}}^{b}]$ is the singularity probability.
# 8 Implementation and Performance

## 8.1 Parameter Selection and Estimated Performance

We now detail the parameter selection and evaluate the performance in terms of sizes that we expect for the signature and the proof systems. Our construction aims for a security target of $\lambda = 128$ bits of classical security. The security of the different algorithms and protocols rely on the structured lattice assumptions M-LWE and M-SIS. We estimate their hardness as described in Appendix A thus lower-bounding the security of our constructions. The security of our signature scheme however is set by a reduction from M-SIS with a loss described in Theorem 5.1 and 5.2. For a target of 128 bits, the security reduction entails a loss of around 38 bits for type ① forgeries and 41 bits for type ② forgeries for our parameters<fnref n="17" />. Concretely, this means we need to aim for 166 bits for the first M-SIS assumption and 169 bits for the second one. To meet this security requirement, we adjust the values of $n, d, q$ and $b$, and set the rest according to Algorithm 5.1. For the proof systems, the parameters are set so as to minimize the proof sizes while providing sufficient security according to Lemmas 7.1 to 7.6. We also choose the rejection sampling parameters to achieve fewer rejections for a better computational efficiency at the expense of a slightly larger proof size. We suggest parameter sets for the signature scheme Table 8.4, and for the issuance and verification proof systems in Table 8.5 and 8.6 respectively, and summarize the estimated performance in Table 8.1. They correspond to a credential over 10 hidden attributes for comparison purposes with prior works, while also being the same order of magnitude as for the typical use case of identification documents, e.g., passport, national ID.

<table><caption>**Table 8.1.** Size and security estimates of our anonymous credentials. All sizes are expressed in KB. *opk*, *osk* represent the organization keys, *upk*, *usk* the user keys, *sig* the emitted signature, and *cred* the credential proof.</caption><thead><tr><th>Security</th><th>Assumptions</th><th>|opk|</th><th>|osk|</th><th>|upk|</th><th>|usk|</th><th>|sig|</th><th>|cred|</th></tr></thead><tbody><tr><td>128</td><td>M-SIS/M-LWE</td><td>47.53 KB</td><td>10 KB</td><td>2.38 KB</td><td>0.25 KB</td><td>6.81 KB</td><td>79.58 KB</td></tr></tbody></table>

We compare our scheme to the existing lattice-based anonymous credentials [JRS23,BLNS23,LLLW23] on their compromise between security and credential size, i.e., the size of a non-interactive proof in Algorithm 6.4, which represents the main metric we want to optimize over. First, in comparison to the figures reported in [JRS23], our construction drastically improves upon their performances on all metrics and with a tighter security proof. In particular, compared to their efficiency estimates in [JRS23, Tab. H.4], we gain factors of 200, 1080, 45, 9 on the organization public key, organization secret key, emitted

<footnote n="17">¹⁷ Although we evaluate the composition $h^{\circ d}$ for our parameter selection, we explain in Appendix A how to bound $h^{\circ d}$ to support this loss.</footnote>
signature, and credential proof respectively. We also achieve more compact sizes
than [LLLW23]. In the latter, the authors propose parameter sets for three dif-
ferent security reductions. The first achieves credential proofs or around 190 KB
but for selective unforgeability. The second builds upon the selective parameter
set and achieves adaptive security via complexity leveraging for a credential of
370 KB, but it results in a reduction loss of $2^{128}$. The third achieves adaptive
security directly but results in much larger credentials of around 24.7 MB. Fi-
nally, in [BLNS23], the authors relaxed the hardness assumption by introducing
the NTRU-ISIS$_f$ (and its interactive version) to reach smaller credentials. We
reach credential proofs around 3 times smaller than their construction based
on NTRU-ISIS$_f$, and get close to the performance of their construction based
on the interactive assumption Int-NTRU-ISIS$_f$, but by relying on standard non-
interactive assumptions (M-SIS, M-LWE). We summarize this comparison in Ta-
ble 1.1. In particular, we are the only scheme achieving credentials smaller than
100 KB without relying on interactive and non-standard assumptions.

## 8.2 Implementation Details

To showcase the feasibility of our proposed construction, and to facilitate future
research in this direction, we have implemented a proof of concept in $C^{18}$. Apart
from the complexity of the protocols themselves, the first notable challenge we
faced was implementing polynomial arithmetic in five different rings, each pre-
senting unique characteristics. Among these rings, three operate with coefficients
modulo single-precision primes or single-precision products of two primes, posing
challenges for efficient multiplication as they inherently lack native support for
NTT. Another ring operates over multi-precision integers in order to estimate
the spectral norm during the key generation whose methodology is described in
Appendix B. The fifth ring is over $\mathbb{R}$ for the SEP perturbation sampling. We
carried a precision analysis of the different Gaussian samplers in order to deter-
mine the necessary floating-point precision needed in the implementation of our
scheme. It can be found in Section 9. Overall, we show that a precision of 53
bits is sufficient and leads to no noticeable security loss.

Faced with the intricacies of polynomial arithmetic across multiple rings, and
considering that the actual construction is highly complex already<fnref n="19" />, we chose
FLINT [tea23] as our arithmetic backend. However, it is important to acknowl-
edge several downsides of this choice: Firstly, FLINT implements arithmetic
operations usually in a very generic way which may be non-optimal given that
our parameters are static at compile time. Moreover, this generic arithmetic also
includes the usage of branches for trivial cases, which breaks the constant-time
paradigm for cryptographic implementations. Secondly, FLINT heavily relies on
dynamic memory allocations, both internally and when handling passed data.
In contrast to stack allocations, which are usually used in cryptographic imple-

<footnote n="18">18 https://github.com/Chair-for-Security-Engineering/lattice-anonymous-credentials</footnote>

<footnote n="19">¹⁹ Excluding any arithmetic, our implementation has about 4700 lines of code compared to, e.g., 890 lines for the official Kyber code without arithmetic.</footnote>
mentations, these dynamic ones are significantly slower. To mitigate this performance drop to a certain extent, we employ static, pre-allocated variables within the wrapper.

For these reasons, our implementation prioritizes accessibility and clarity for future research. We have abstracted calls to FLINT functions with a wrapper which offers the flexibility to replace the FLINT-based arithmetic with custom constant-time, parameter-specific code without the necessity of touching the protocol layer. Importantly, it requires no other dependencies beyond FLINT, and the code is thoroughly documented to enhance comprehension.

We want to emphasize that, apart from an parameter-specific, optimized arithmetic backend, our code could be further optimized by deploying AVX2-vectorized hashing. Through profiling, however, we have confirmed that for our code hashing is not the main bottleneck for both proof generation procedures as well as the verifications.

## 8.3 Implementation Performance

We benchmark our implementation on a laptop featuring an Intel Core i7 12800H CPU running at 4.6 GHz and the scaling governor set to performance. Both our code and the FLINT library have been compiled with gcc 11.4.0 with the options -O3 -march=native. For building FLINT, we explicitly enabled AVX2 and disabled the pthread option to ensure that no thread pools are used and the program runs on a single core.

<table><caption>**Table 8.2.** Benchmark results. Statistics over 100 executions. Where applicable, the key and message were randomized (e.g., the SEP signing is benchmarked over random keys and random messages). High variance timings are due to rejection sampling. Note that we omitted the benchmark result for the oblivious signing user signature completion, which takes on average 1.2 µs.</caption><thead><tr><th rowspan="2">Protocol</th><th rowspan="2">Procedure</th><th colspan="4">Time (ms)</th></tr><tr><th>min</th><th>mean</th><th>med</th><th>max</th></tr></thead><tbody><tr><td rowspan="3">SEP</td><td>key gen.</td><td>241.01</td><td>414.21</td><td>270.33</td><td>1086.56</td></tr><tr><td>sign</td><td>57.36</td><td>58.83</td><td>58.51</td><td>61.73</td></tr><tr><td>verify</td><td>1.68</td><td>1.69</td><td>1.69</td><td>1.70</td></tr><tr><td rowspan="8"> Credential Issuance</td><td>user commit</td><td>0.79</td><td>0.81</td><td>0.81</td><td>0.88</td></tr><tr><td>signer sign cmt.</td><td>56.42</td><td>56.84</td><td>56.75</td><td>62.49</td></tr><tr><td>user verify</td><td>1.68</td><td>1.69</td><td>1.69</td><td>1.76</td></tr><tr><td>user key gen.</td><td>0.46</td><td>0.47</td><td>0.47</td><td>0.53</td></tr><tr><td>user embed</td><td>0.74</td><td>0.78</td><td>0.78</td><td>0.86</td></tr><tr><td>user prove</td><td>126.57</td><td>221.33</td><td>167.20</td><td>644.58</td></tr><tr><td>signer verify</td><td>100.01</td><td>100.94</td><td>100.78</td><td>103.98</td></tr><tr><td rowspan="3"> Credential Showing</td><td>user embed</td><td>2.35</td><td>2.39</td><td>2.38</td><td>2.52</td></tr><tr><td>user prove</td><td>197.42</td><td>354.59</td><td>280.29</td><td>1019.18</td></tr><tr><td>user verify</td><td>145.96</td><td>147.14</td><td>147.10</td><td>152.21</td></tr></tbody></table>
<table><caption>**Table 8.3.** Benchmark results. Statistics over 100 executions. Where applicable, the key and message were randomized (e.g., the SEP signing is benchmarked over random keys and random messages). High variance timings are due to rejection sampling. Note that we omitted the benchmark result for the oblivious signing user signature completion, which takes on average 1611 cycles.</caption><thead><tr><th rowspan="2">Protocol</th><th rowspan="2">Procedure</th><th colspan="4">Time (million cycles)</th></tr><tr><th>min</th><th>mean</th><th>med</th><th>max</th></tr></thead><tbody><tr><td rowspan="3">SEP</td><td>key gen.</td><td>675.60</td><td>1161.12</td><td>757.79</td><td>3045.88</td></tr><tr><td>sign</td><td>160.78</td><td>164.90</td><td>164.00</td><td>173.03</td></tr><tr><td>verify</td><td>4.68</td><td>4.71</td><td>4.71</td><td>4.75</td></tr><tr><td rowspan="6">Credential Issuance</td><td>user commit</td><td>2.20</td><td>2.25</td><td>2.25</td><td>2.44</td></tr><tr><td>signer sign cmt.</td><td>158.15</td><td>159.30</td><td>159.06</td><td>175.15</td></tr><tr><td>user verify</td><td>4.69</td><td>4.72</td><td>4.71</td><td>4.91</td></tr><tr><td>user key gen.</td><td>1.27</td><td>1.30</td><td>1.29</td><td>1.48</td></tr><tr><td>user embed</td><td>2.07</td><td>2.17</td><td>2.17</td><td>2.40</td></tr><tr><td>user prove</td><td>354.80</td><td>620.44</td><td>468.68</td><td>1806.93</td></tr><tr><td rowspan="3">Credential Showing</td><td>signer verify</td><td>280.32</td><td>282.93</td><td>282.50</td><td>291.48</td></tr><tr><td>user embed</td><td>6.56</td><td>6.67</td><td>6.65</td><td>7.05</td></tr><tr><td>user prove</td><td>553.41</td><td>993.99</td><td>785.72</td><td>2856.98</td></tr><tr><td></td><td>user verify</td><td>409.15</td><td>412.46</td><td>412.32</td><td>426.67</td></tr></tbody></table>

The timing results are shown in Table 8.2 in milliseconds, while the cycle counts are given in Table 8.3. As expected, there are notable variations in the timings due to rejection sampling, but also for procedures that do not involve rejection steps, which stems from the use of FLINT. Note, however, that we clear all FLINT-internal caches after each iteration of the benchmarked function.

The most important steps for anonymous credentials are Issuance and Credential Showing as they directly impact the user experience. Regarding Issuance, the full protocol takes about 400 ms (on average) which we deem very reasonable. Credential Showing is slightly slower as it takes about 500 ms (including Verification) on average, which should be imperceptible in most cases.

We also recall that the point of our implementation was to provide a better understanding of the performance of privacy-preserving solutions, not to provide the most optimized code for a specific setting. In particular, we did not implement our own arithmetic backend tailored to our moduli, nor did we leverage the multiple cores of modern CPUs (our timings were obtained without any parallelisation) or precomputations. In other words, there are many ways one could improve performance without changing the cryptographic protocol itself and, given the already appealing benchmarks as shown in Table 8.2, we are confident that our solution should be sufficiently practical for most use-cases.

# 9 Samplers' Precision Analysis

In this section, we detail the precision analysis of the different samplers that we require to determine the minimal floating-point precision for our implementation.
The systematic analysis of floating-point arithmetic (FPA) precision in Gaussian samplers has been bootstrapped by Prest and Lyubashevsky [LP15,Pre15,Pre17]. In these works, they provide a detailed floating-point precision analysis of Klein's sampler [Kle00,GPV08] and Peikert's sampler [Pei10].

Our construction uses three kinds of Gaussian samplers. The first is a spherical Gaussian sampler over $\mathbb{Z}$ (or $\mathbb{Z}^N$ or $R$), and is used as a base sampler for the others as well as for the masks in the zero-knowledge arguments. The second is the one presented in Algorithm 3.1 which samples a non-spherical perturbation over $R$. Finally, the third is the gadget sampler to sample points on $\mathcal{L}_q^\perp(\mathbf{G})$ where we use Klein's sampler on the basis (and its gram-Schmidt) of $\mathcal{L}_q^\perp(\mathbf{G})$. The base sampler is well understood and well studied which is why we only focus on the remaining two by assuming a perfect base sampler over $\mathbb{Z}$.

## 9.1 Klein's Sampler on the Gadget Lattice

The analysis of Klein's sampler has been thoroughly done in the general case by Prest [Pre15,Pre17]. We state the result in the case of integer bases and integer centers, and also specify how it changes when the (scaled) Gram-Schmidt is known exactly. Indeed, if the basis is integral, its Gram-Schmidt is rational and can be represented exactly if the denominators are not too large. The proof follows the blueprint of [Pre17] but we include it for completeness. We give the version of Klein's sampler that we use, which is rigorously equivalent to the standard formulation. In particular, it takes the basis $\mathbf{B} \in \mathbb{Z}^{N \times N}$, the scaled Gram-Schmidt $\tilde{\mathbf{B}}'$ whose columns are the $\tilde{\mathbf{b}}_i/\|\tilde{\mathbf{b}}_i\|_2^2$, the widths $s_i = s/\|\tilde{\mathbf{b}}_i\|_2$ and a center $\mathbf{t} \in \mathbb{Z}^N$.

**Algorithm 9.1: Klein($\mathbf{B}, \tilde{\mathbf{B}}', (s_i)_{i \in [N]}$)**

**Input:** Basis $\mathbf{B} \in \mathbb{Z}^{N \times N}$, Scaled Gram-Schmidt $\tilde{\mathbf{B}}' \in \mathbb{Q}^{N \times N}$, Widths $(s_i)_{i \in [N]} \in (\mathbb{R}^{+*})^N$, center $\mathbf{t} \in \mathbb{Z}^N$.

1. $\mathbf{v}_N \leftarrow \mathbf{0}$.

2. **for** $i = N, \dots, 1$ **do**

3. $d_i \leftarrow \langle \mathbf{t} - \mathbf{v}_i, \tilde{\mathbf{b}}'_i \rangle$.

4. $z_i \leftarrow \mathcal{D}_{\mathbb{Z},s_i,d_i}$.

5. $\mathbf{v}_{i-1} \leftarrow \mathbf{v}_i + z_i \mathbf{b}_i$.

**Output:** $\mathbf{v}_0$

▷ Statistically close to $\mathcal{D}_{\mathbb{B}^N, s, \mathbf{t}}$.

**Lemma 9.1 ([Pre15, Lem. 3.12] adapted).** Let $N$ be a positive integer, $\mathbf{B} \in \mathbb{Z}^{N \times N}$, $\mathbf{t} \in \mathbb{Z}^N$, $\varepsilon \in (0,1)$ and $s \ge 2\eta_\varepsilon(\mathbb{Z})\|\tilde{\mathbf{B}}\|$. We let $\mathcal{P}$ be the output distribution of Klein($\mathbf{B}, \tilde{\mathbf{B}}', (s_i)_{i \in [N]}$, $\mathbf{t}$) with $\tilde{\mathbf{B}}', (s_i)_{i \in [N]}$ precomputed with infinite precision. Similarly, let $\bar{\mathcal{P}}$ be the output distribution of Klein($\mathbf{B}, \tilde{\mathbf{B}}', (\bar{s}_i)_{i \in [N]}$, $\mathbf{t}$) with $\tilde{\mathbf{B}}', (\bar{s}_i)_{i \in [N]}$ precomputed with finite precision. Let $\delta \in [0,1)$ be such that

$$ - \forall i \in [N], \|\tilde{\mathbf{b}}'_i - \tilde{\mathbf{b}}_i\|_{\infty} \le \delta $$

$$ - \forall i \in [N], |s_i - \bar{s}_i| \le \delta s_i $$
We then define

$$
\begin{align*}
C &= \frac{\pi \delta N}{(1-\delta)^2} \left( 2c_N N \|\tilde{\mathbf{B}}\| \left( c_N + \frac{(1+\delta)^2 \varepsilon}{1-\varepsilon} \right) \right. \\
  &\qquad \left. + (2+\delta) \left( c_N^2 + \frac{1}{2\pi} + \frac{\varepsilon}{1-\varepsilon} \right) \right) + \frac{\pi \delta^2 (1+(1+\delta)^2) c_N^2 N^3 \|\tilde{\mathbf{B}}\|^2}{(1-\delta)^2} \\
  &\sim_{\delta, \varepsilon \to 0} \delta N (2\pi c_N^2 N \|\tilde{\mathbf{B}}\| + 2\pi c_N^2 + 1).
\end{align*}
$$

Then, it holds that for all $\mathbf{v} \in \mathbf{B}\mathbb{Z}^N$, $\overline{\mathcal{P}}(\mathbf{v}) \in [e^{-C}, e^C]\mathcal{P}(\mathbf{v})$. When $\tilde{\mathbf{B}}'$ can be computed exactly, the expression of $C$ is improved to

$$
C = \delta N \frac{2\pi(1 + \delta/2)}{(1 - \delta)^2} \left( c_N^2 + \frac{1}{2\pi} + \frac{\varepsilon}{1 - \varepsilon} \right) \underset{\delta, \varepsilon \to 0}{\sim} \delta N (2\pi c_N^2 + 1).
$$

Proof. Let $\mathbf{v} \in \mathbf{B}\mathbb{Z}^N$ be a possible outcome of $\mathcal{P}$ and $\overline{\mathcal{P}}$. There exists a unique $\mathbf{z} \in \mathbb{Z}^N$ such that $\mathbf{v} = \mathbf{B}\mathbf{z}$ whose entries are the outputs of the base sampler in the loop. In particular, there exists a unique $(d_i)_i$ (resp. $(\bar{d}_i)_i$) such that the infinite (resp. finite) precision sampler computes those centers in the loop.

We first bound the differences $|d_i - \bar{d}_i|$. Let $i \in [N]$. We can rewrite $d_i$ in
terms of $\mathbf{v}$ rather than $\mathbf{v}_i$ as $d_i = \langle \mathbf{t} - \mathbf{v}, \tilde{\mathbf{b}}'_i \rangle + z_i$. Hence, $\bar{d}_i = \langle \mathbf{t} - \mathbf{v}, \tilde{\mathbf{b}}'_i + \boldsymbol{\delta}_i \rangle + z_i =$
$d_i + \langle \mathbf{t} - \mathbf{v}, \boldsymbol{\delta}_i \rangle$, where by assumption $\|\boldsymbol{\delta}_i\|_{\infty} \le \delta$. This gives

$$
|d_i - \bar{d}_i| \le \|\mathbf{t} - \mathbf{v}\|_2 \|\boldsymbol{\delta}_i\|_2 \le c_N s \sqrt{N} \cdot \delta \sqrt{N} = c_N s \delta N,
$$

where the last inequality comes from Lemma 2.7. Note that $d_i = \bar{d}_i$ if $\tilde{\mathbf{B}}'$ can be
computed exactly.

Now, we bound the ratio $\mathcal{P}(\mathbf{v})/\overline{\mathcal{P}}(\mathbf{v})$. Since both sampler output $\mathbf{v}$ only if the
base samplers output the $z_i$, we have

$$
\frac{\mathcal{P}(\mathbf{v})}{\overline{\mathcal{P}}(\mathbf{v})} = \prod_{i \in [N]} \frac{\rho_{s_i, d_i}(z_i) \rho_{\bar{s}_i, \bar{d}_i}(\mathbb{Z})}{\rho_{\bar{s}_i, \bar{d}_i}(z_i) \rho_{s_i, d_i}(\mathbb{Z})} = \prod_{i=1}^{N} e^{u_i(z_i)} \frac{\rho_{\bar{s}_i, \bar{d}_i}(\mathbb{Z})}{\rho_{s_i, d_i}(\mathbb{Z})},
$$

where $u_i(z) = \pi(z - \bar{d}_i)^2 / \bar{s}_i^2 - \pi(z - d_i)^2 / s_i^2$. By [Pre15, Lem. 3.10], we can bound
the ratio of Gaussian sums and get

$$
A := \sum_{i \in [N]} u_i(z_i) - \mathbb{E}_{z \sim \mathcal{D}_i} [u_i(z)] \le \ln \frac{\mathcal{P}(\mathbf{v})}{\overline{\mathcal{P}}(\mathbf{v})} \le \sum_{i \in [N]} u_i(z_i) - \mathbb{E}_{z \sim \overline{\mathcal{D}}_i} [u_i(z)] =: B,
$$

where $\mathcal{D}_i = \mathcal{D}_{\mathbb{Z},s_i,d_i}$ and $\overline{\mathcal{D}}_i = \mathcal{D}_{\mathbb{Z},\bar{s}_i,\bar{d}_i}$. We now have to show that $-C \le A$ and $B \le C$.

First, we rewrite $u_i(z)$ in two different ways as in [Pre15]. We have

$$
u_i(z) = \frac{\pi}{s_i^2} \left( (d_i - \bar{d}_i)^2 + 2(d_i - \bar{d}_i)(z - d_i) - \delta_i(2 + \delta_i)(z - d_i)^2 \right)
$$

$$
u_i(z) = \frac{\pi}{s_i^2} \left( -(1 + \delta_i)^2 (d_i - \bar{d}_i)^2 + 2(1 + \delta_i)^2 (d_i - \bar{d}_i)(z - \bar{d}_i) - \delta_i(2 + \delta_i)(z - \bar{d}_i)^2 \right),
$$
where $\bar{s}_i = (1 + \delta_i)s_i$ with $|\delta_i| \le \delta$ by assumption. We use the first expression and have the following inequalities

$$
\begin{aligned}
|A| & \le \sum_{i \in [N]} \frac{\pi}{\bar{s}_i^2} (2|d_i - \bar{d}_i|(|z_i - d_i| + |\mathbb{E}_{z \sim \mathcal{D}_i}[z - d_i]|) \\
& \qquad + \delta_i(2 + \delta_i)((z_i - d_i)^2 + \mathbb{E}_{z \sim \mathcal{D}_i}[(z - d_i)^2]) \\
& \le \frac{\pi}{(1 - \delta)^2 s^2} \sum_{i \in [N]} 2c_N s \delta N \|\tilde{\mathbf{b}}_i\|_2^2 (|z_i - d_i| + |\mathbb{E}_{z \sim \mathcal{D}_i}[z - d_i]|) \\
& \qquad + \delta(2 + \delta) \|\tilde{\mathbf{b}}_i\|_2^2 ((z_i - d_i)^2 + \mathbb{E}_{z \sim \mathcal{D}_i}[(z - d_i)^2]) \\
& \le \frac{2\pi c_N s N \delta \|\tilde{\mathbf{B}}\|}{(1 - \delta)^2 s^2} \left( \|\mathbf{v} - \mathbf{t}\|_1 + Ns \frac{\varepsilon}{1 - \varepsilon} \right) \\
& \qquad + \frac{\pi \delta(2 + \delta)}{(1 - \delta)^2 s^2} \left( \|\mathbf{v} - \mathbf{t}\|_2^2 + Ns^2 \left( \frac{1}{2\pi} + \frac{\varepsilon}{1 - \varepsilon} \right) \right) \\
& \le \frac{2\pi c_N N^2 \delta \|\tilde{\mathbf{B}}\|}{(1 - \delta)^2} \left( c_N + \frac{\varepsilon}{1 - \varepsilon} \right) + \frac{\pi \delta N(2 + \delta)}{(1 - \delta)^2} \left( c_N^2 + \frac{1}{2\pi} + \frac{\varepsilon}{1 - \varepsilon} \right) \\
& \le C,
\end{aligned}
$$

where the second inequality comes from the bound on $|d_i - \bar{d}_i|$ and the fact that $\bar{s}_i = (1 + \delta_i)s/\|\tilde{\mathbf{b}}_i\|_2 \ge (1 - \delta)s/\|\tilde{\mathbf{b}}_i\|_2$. The third inequality comes by bounding $\|\tilde{\mathbf{b}}_i\|_2$ by $\|\tilde{\mathbf{B}}\|$, by the fact that $\sum_i \|\tilde{\mathbf{b}}_i\|_2|z_i - d_i| = \|\mathbf{v} - \mathbf{t}\|_1$, $\sum_i \|\tilde{\mathbf{b}}_i^2\|_2(z_i - d_i)^2 = \|\mathbf{v} - \mathbf{t}\|_2^2$ and by bounding the expectations using [MR07, Lem. 4.2] as we have $s_i \ge 2\eta_\varepsilon(\mathbb{Z})$. The fourth inequality comes from the Gaussian tail bound of Lemma 2.7.

Following the method of [Pre15], we use the first expression of $u_i$ for the $u_i(z_i)$ and the second expression for the expectations. Using the same arguments as before, we obtain

$$
\begin{aligned}
|B| & \le \frac{\pi \delta N}{(1 - \delta)^2} \left( 2c_N N \|\tilde{\mathbf{B}}\| \left( c_N + \frac{(1 + \delta)^2 \varepsilon}{1 - \varepsilon} \right) + (2 + \delta) \left( c_N^2 + \frac{1}{2\pi} + \frac{\varepsilon}{1 - \varepsilon} \right) \right) \\
& \qquad + \frac{\pi \delta^2 (1 + (1 + \delta)^2) c_N^2 N^3 \|\tilde{\mathbf{B}}\|^2}{(1 - \delta)^2} \\
& = C
\end{aligned}
$$

The equivalence is taken at the first order in $\delta$ and $\varepsilon$ which indeed simplifies to $\delta N(2\pi c_N^2 N \|\tilde{\mathbf{B}}\| + 2\pi c_N^2 + 1)$.

Finally, the expression of $C$ when $\tilde{\mathbf{B}}'$ can be represented exactly comes from the exact same process. The only difference is that $d_i = \bar{d}_i$ which simplifies the two expressions of $u_i(z)$ to $u_i(z) = -\pi\delta_i(2 + \delta_i)(z - d_i)^2/\bar{s}_i^2$. $\square$

In our case, we apply Klein's sampler on the gadget lattice for centers which have integer coefficients. Since the gadget lattice has a specific structure, we can
derive a closed-form expression of the scaled Gram-Schmidt which is why we may decide to store it exactly. More precisely in our case, $N = nkd$, $||\tilde{\mathbf{B}}|| = \sqrt{b^2 + 1}$. For typical parameters as those from Table 8.4 where $n = 256$, $k = 5$, $d = 4$, $b = 14$, we have $c_N \approx 0.453$ and therefore $C \approx 2^{28.82}\delta$ in the general case and $C \approx 2^{15.19}\delta$ in the exact scaled Gram-Schmidt case. Plugging this in our security proof gives a requirement of 50 bits and 36 bits of precision respectively aiming for $C = 1/2\sqrt{\lambda Q}$. The standard precision of 53 bits for floating points is therefore enough to incur almost no security loss.

## 9.2 Perturbation Sampler

The perturbation sampler is very similar to the Fast Fourier Sampler of [DP16] which is used in the Falcon signature scheme [PFH$^{+20}$]. The algorithm is recursive in the subroutine that samples from $D_{R, \sqrt{M_{\tau}(f_i), d_i}}$. In particular, it makes an overall number of $2d \cdot n$ calls to integer samplers $D_{\mathbb{Z}, s_j, e_j}$. We can, as is done for the Fast Fourier Sampler, analyze the precision needed for Algorithm 3.1 using an adapted version of the analysis of Klein's sampler. More precisely, we assume a relative error of at most $\delta_s$ on the $s_j$ and an absolute error of at most $\delta_e$ on the centers $e_j$. We thus bound the quantities $|\bar{e}_j - e_j|$ by $\delta_e$ in the above proof, and the $|z_j - e_j|$ by $s_j t$ using [Lyu12, Lem. 4.4] for a slack $t \approx 6$. Using those upper bounds, and the fact that $s_j \ge \eta_{\epsilon}(\mathbb{Z})$, we obtain that the relative error between the infinite and finite precision versions of the sampler is of $e^C - 1$, for

$$ 
\begin{aligned}
C &= \frac{2\pi N}{(1 - \delta_s)^2} \left( \frac{\delta_e}{\eta_{\epsilon}(\mathbb{Z})} \left( t + (1 + \delta_s)^2 \frac{\epsilon}{1 - \epsilon} \right) \right. \\
  &\qquad \left. + \delta_s(1 + \delta_s/2) \left( t^2 + \frac{1}{2\pi} + \frac{\epsilon}{1 - \epsilon} \right) + \frac{\delta_e^2}{\eta_{\epsilon}(\mathbb{Z})^2} \frac{1 + (1 + \delta_s)^2}{2} \right) \\
  &\le N(2\pi t^2 + 2\pi\sqrt{\epsilon} + 1)(\delta_s + \delta_e),
\end{aligned}
$$

where $N = 2nd$, and where the inequality holds for all $\epsilon, \delta_s, \delta_e \le 2^{-10}$. In our context, this gives $C \le 2^{18.83}(\delta_s + \delta_e)$, which when plugged into our security proof gives a precision requirement of $\delta_s + \delta_e \le 2^{-39.4}$.

We use the same methodology than [PFH$^{+20}$] to verify this bound. More precisely, we ran the signature process in both standard precision of 53 bits and high precision of 200 bits using the same random tape$^{20}$. By comparing the values of the $s_j$ and $e_j$ between the two versions, we observe that we have $\delta_s + \delta_e \le 2^{-36.9}$. Although this is slightly higher than $2^{-39.4}$, choosing the standard precision of 53 bits gives a sufficient margin so that it incurs no noticeable loss of security.

<footnote>$^{20}$ Sampling can easily be made deterministic by generating the needed randomness via an extendable output function such as SHAKE256.</footnote>
Conclusion

Practical signatures for privacy [CL04,PS16,San21] have been successfully im-
plemented and even standardized [ISO13a,ISO13b], resulting in very efficient
systems. Up until a few years ago, only theoretical alternatives existed in the
post-quantum setting. Several recent works [JRS23,BLNS23,LLLW23] have im-
proved the state-of-the-art by reducing the bandwidth, sometimes at the cost of
a weaker security. We continue this line of works by showcasing promising sizes
without compromising security but also extend it by demonstrating practical-
ity of such mechanisms. Although we use anonymous credentials as a common
benchmark with previous works, we stress that our SEP and its implementation
are very versatile and could easily be adapted to other cryptographic primitives.
Our work thus fosters practical post-quantum privacy and makes a significant
step towards it.

Acknowledgments

Sven Argo, Tim Güneysu and Georg Land have been supported by the Deutsche
Forschungsgemeinschaft (DFG, German Research Foundation) under Germany’s
Excellence Strategy - EXC 2092 CASA - 390781972, and by the German Federal
Ministry of Education and Research BMBF through the projects QuantumRISC
(16KIS1038), PQC4Med (16KIS1044), and 6GEM (16KISK038). Corentin Jeudy
and Adeline Roux-Langlois were supported by the French National Research
Agency in the ASTRID program, under the national project AMIRAL with
reference ANR-21-ASTR-0016, and Olivier Sanders through the MobiS5 project
with reference ANR-18-CE-39-0019-02 MobiS5.

References

APS15. M. R. Albrecht, R. Player, and S. Scott. On the Concrete Hardness of
Learning With Errors. J. Math. Cryptol., 2015.

Ban93. W. Banaszczyk. New Bounds in Some Transference Theorems in the Geometry of Numbers. Math. Ann., 1993.

BB08. D. Boneh and X. Boyen. Short Signatures Without Random Oracles and the SDH Assumption in Bilinear Groups. J. Cryptol., 2008.

BCC04. E. F. Brickell, J. Camenisch, and L. Chen. Direct Anonymous Attestation. In CCS, 2004.

BCR<sup>+</sup>23. O. Blazy, C. Chevalier, G. Renaut, T. Ricosset, E. Sageloli, and H. Senet. Efficient Implementation of a Post-Quantum Anonymous Credential Protocol. In ARES, 2023.

BDGT17. A. Barki, N. Desmoulins, S. Gharout, and J. Traoré. Anonymous attestations made practical. In *WISEC*, 2017.

BEF19. D. Boneh, S. Eskandarian, and B. Fisch. Post-quantum EPID Signatures from Symmetric Primitives. In *CT-RSA*, 2019.

BEP<sup>+</sup>21. P. Bert, G. Eberhart, L. Prabel, A. Roux-Langlois, and M. Sabt. Implementation of Lattice Trapdoors on Modules and Applications. In *PQCrypto*, 2021.
BJRW23. K. Boudgoust, C. Jeudy, A. Roux-Langlois, and W. Wen. On the Hardness of Module Learning with Errors with Short Distributions. *J. Cryptol.*, 2023.

BL07. E. Brickell and J. Li. Enhanced Privacy ID: a Direct Anonymous Attestation Scheme with Enhanced Revocation Capabilities. In *WPES*, 2007.

BLNS23. J. Bootle, V. Lyubashevsky, N. K. Nguyen, and A. Sorniotti. A Framework for Practical Anonymous Credentials from Lattices. In *CRYPTO*, 2023.

BLR<sup>+18</sup>. S. Bai, T. Lepoint, A. Roux-Langlois, A. Sakzad, D. Stehlé, and R. Steinfeld. Improved Security Proofs in Lattice-Based Cryptography: Using the Rényi Divergence Rather than the Statistical Distance. *J. Cryptol.*, 2018.

BSZ05. M. Bellare, H. Shi, and C. Zhang. Foundations of Group Signatures: The Case of Dynamic Groups. In *CT-RSA*, 2005.

Can20. R. Canetti. Universally Composable Security. *J. ACM*, 67(5):28:1–28:94, 2020.

CBC<sup>+24</sup>. M. Christ, F. Baldimtsi, K. K. Chalkias, D. Maram, A. Roy, and J. Wang. SoK: Zero-Knowledge Range Proofs. *IACR Cryptol. ePrint Arch.*, page 430, 2024.

CDL16. J. Camenisch, M. Drijvers, and A. Lehmann. Anonymous Attestation Using the Strong Diffie Hellman Assumption Revisited. In *TRUST*, 2016.

CGM19. Y. Chen, N. Genise, and P. Mukherjee. Approximate Trapdoors for Lattices and Smaller Hash-and-Sign Signatures. In *ASIACRYPT*, 2019.

Cha82. D. Chaum. Blind Signatures for Untraceable Payments. In *CRYPTO*, 1982.

Che13. Y. Chen. Réduction de Réseau et Sécurité Concrète du Chiffrement Complètement Homomorphe. PhD thesis, Paris 7, 2013.

CKLL19. L. Chen, N. El Kassem, A. Lehmann, and V. Lyubashevsky. A Framework for Efficient Lattice-Based DAA. In *CYSARM@CCS*, 2019.

CL04. J. Camenisch and A. Lysyanskaya. Signature Schemes and Anonymous Credentials from Bilinear Maps. In *CRYPTO*, 2004.

CvH91. D. Chaum and E. van Heyst. Group Signatures. In *EUROCRYPT*, 1991.

DFPS22. J. Devevey, O. Fawzi, A. Passelègue, and D. Stehlé. On Rejection Sampling in Lyubashevsky’s Signature Scheme. In *ASIACRYPT*, 2022.

DP06. C. Delerablée and D. Pointcheval. Dynamic Fully Anonymous Short Group Signatures. In *VIETCRYPT*, 2006.

DP16. L. Ducas and T. Prest. Fast Fourier Orthogonalization. In *ISSAC*, 2016.

dPLS18. R. del Pino, V. Lyubashevsky, and G. Seiler. Lattice-Based Group Signatures and Zero-Knowledge Proofs of Automorphism Stability. In *CCS*, 2018.

EFG<sup>+22</sup>. T. Espitau, P.-A. Fouque, F. Gérard, M. Rossi, A. Takahashi, M. Tibouchi, A. Wallet, and Y. Yu. Mitaka: A Simpler, Parallelizable, Maskable Variant of Falcon. In *EUROCRYPT*, 2022.

ETWY22. T. Espitau, M. Tibouchi, A. Wallet, and Y. Yu. Shorter Hash-and-Sign Lattice-Based Signatures. In *CRYPTO*, 2022.

FHS19. G. Fuchsbauer, C. Hanser, and D. Slamanig. Structure-Preserving Signatures on Equivalence Classes and Constant-Size Anonymous Credentials. *J. Cryptol.*, 2019.

Fis06. M. Fischlin. Round-Optimal Composable Blind Signatures in the Common Reference String Model. In *CRYPTO*, 2006.

GHL22. C. Gentry, S. Halevi, and V. Lyubashevsky. Practical Non-interactive Publicly Verifiable Secret Sharing with Thousands of Parties. In *EUROCRYPT*, 2022.
GM18. Nicholas Genise and Daniele Micciancio. Faster Gaussian Sampling for Trapdoor Lattices with Arbitrary Modulus. In *EUROCRYPT*, 2018.

GMPW20. N. Genise, D. Micciancio, C. Peikert, and M. Walter. Improved Discrete Gaussian and Subgaussian Analysis for Lattice Cryptography. In *PKC*, 2020.

GMR85. S. Goldwasser, S. Micali, and C. Rackoff. The Knowledge Complexity of Interactive Proof-Systems (Extended Abstract). In *STOC*, 1985.

GPV08. C. Gentry, C. Peikert, and V. Vaikuntanathan. Trapdoors for Hard Lattices and New Cryptographic Constructions. In *STOC*, 2008.

Int16. Intel. A Cost-Effective Foundation for End-to-End IoT Security, White Paper. https://www.intel.com/content/dam/www/public/us/en/documents/white-papers/intel-epid-iot-security-white-paper.pdf, 2016.

ISO13a. ISO/IEC. ISO/IEC 18370-2:2016 Information Technology — Security Techniques — Blind Digital Signatures — Part 2: Discrete Logarithm Based Mechanisms. https://www.iso.org/standard/62544.html, 2013.

ISO13b. ISO/IEC. ISO/IEC 20008-2:2013 Information Technology — Security Techniques — Anonymous Digital Signatures — Part 2: Mechanisms using a Group Public Key. https://www.iso.org/standard/56916.html, 2013.

JHT22. H. Jia, Y. Hu, and C. Tang. Lattice-Based Hash-and-Sign Signatures using Approximate Trapdoor, Revisited. *IET Inf. Secur.*, 2022.

JRS23. C. Jeudy, A. Roux-Langlois, and O. Sanders. Lattice Signature with Efficient Protocols, Application to Anonymous Credentials. In *CRYPTO*, 2023.

Kle00. P. N. Klein. Finding the closest lattice vector when it's unusually close. In *SODA*, 2000.

LLLW23. Q. Lai, F.-H. Liu, A. Lysyanskaya, and Z. Wang. Lattice-based Commit-Transferrable Signatures and Applications to Anonymous Credentials. *IACR Cryptol. ePrint Arch.*, page 766, 2023.

LLM$^+16$. B. Libert, S. Ling, F. Mouhartem, K. Nguyen, and H. Wang. Signature Schemes with Efficient Protocols and Dynamic Group Signatures from Lattice Assumptions. In *ASIACRYPT*, 2016.

LNP22. V. Lyubashevsky, N. K. Nguyen, and M. Plançon. Lattice-Based Zero-Knowledge Proofs and Applications: Shorter, Simpler, and More General. *CRYPTO*, 2022.

LNPS21. V. Lyubashevsky, N. K. Nguyen, M. Plançon, and G. Seiler. Shorter Lattice-Based Group Signatures via "Almost Free" Encryption and Other Optimizations. In *ASIACRYPT*, 2021.

LNS21. V. Lyubashevsky, N. K. Nguyen, and G. Seiler. Shorter Lattice-Based Zero-Knowledge Proofs via One-Time Commitments. In *PKC*, 2021.

LP15. V. Lyubashevsky and T. Prest. Quadratic Time, Linear Space Algorithms for Gram-Schmidt Orthogonalization and Gaussian Sampling in Structured Lattices. In *EUROCRYPT*, 2015.

LS15. A. Langlois and D. Stehlé. Worst-case to Average-case Reductions for Module Lattices. *DCC*, 2015.

LS18. V. Lyubashevsky and G. Seiler. Short, Invertible Elements in Partially Splitting Cyclotomic Rings and Applications to Lattice-Based Zero-Knowledge Proofs. In *EUROCRYPT*, 2018.

LW15. V. Lyubashevsky and D. Wichs. Simple Lattice Trapdoor Sampling from a Broad Class of Distributions. In *PKC*, 2015.
Lyu12. V. Lyubashevsky. Lattice Signatures without Trapdoors. In *EUROCRYPT*, 2012.

MP12. D. Micciancio and C. Peikert. Trapdoors for Lattices: Simpler, Tighter, Faster, Smaller. In *EUROCRYPT*, 2012.

MR07. D. Micciancio and O. Regev. Worst-Case to Average-Case Reductions Based on Gaussian Measures. *SIAM J. Comput.*, 2007.

Pei10. C. Peikert. An Efficient and Parallel Gaussian Sampler for Lattices. In *CRYPTO*, 2010.

PFH$^{+}$20. T. Prest, P.-A. Fouque, J. Hoffstein, P. Kirchner, V. Lyubashevsky, T. Pornin, T. Ricosset, G. Seiler, W. Whyte, and Z. Zhang. *FALCON*. Tech. rep., 2020. Available at https://csrc.nist.gov/Projects/post-quantum-cryptography/selected-algorithms-2022.

Pre15. T. Prest. *Gaussian Sampling in Lattice-Based Cryptography*. PhD thesis, École Normale Supérieure, Paris, France, 2015.

Pre17. T. Prest. sharper Bounds in Lattice-Based Cryptography Using the Rényi Divergence. In *ASIACRYPT*, 2017.

PS15. D. Pointcheval and O. Sanders. Short Randomizable Signatures. *IACR Cryptol. ePrint Arch.*, page 525, 2015.

PS16. D. Pointcheval and O. Sanders. Short Randomizable Signatures. In *CT-RSA*, 2016.

San21. O. Sanders. Improving Revocation for Group Signature with Redactable Signature. In *PKC*, 2021.

ST21. O. Sanders and J. Traoré. EPID with Malicious Revocation. In *CT-RSA*, 2021.

TCG15. TCG. https://trustedcomputinggroup.org/authentication/, 2015.

tea23. The FLINT team. *FLINT: Fast Library for Number Theory*, 2023. Version 3.0.0, https://flintlib.org.

Ver12. R. Vershynin. Introduction to the Non-Asymptotic Analysis of Random Matrices. In *Compressed Sensing*. 2012.
# A Concrete Security Analysis

In this section we recall the methodology we use to estimate the hardness of the M-LWE and M-SIS assumptions. The best attacks use lattice reduction and rely on the BKZ algorithm as a subroutine. In our security estimates, we evaluate the cost of running the sieving SVP oracle with blocksize $B$ by $2^{0.292B+16.4}$ for the classical security and $2^{0.257B+16.4}$ for the quantum security.

Under the Gaussian Heuristic and the Geometric Series Assumption, the BKZ algorithm with blocksize $B$ would find a vector $\mathbf{v}$ in a $N$-dimensional lattice $\mathcal{L}$ with $\|\mathbf{v}\|_2 \le \delta_B^N \mathrm{Vol}(\mathcal{L})^{1/N}$, where by [Che13] we have

$$ \delta_B \approx \left( \frac{(\pi B)^{\frac{1}{B}} B}{2\pi e} \right)^{\frac{1}{2(B-1)}}. \qquad (19) $$

## A.1 Key Recovery and Zero-Knowledge: M-LWE

In the signature scheme of Section 5, the public key is given by $\mathbf{A}' \in R_q^{d \times d}$ and $\mathbf{B} = [\mathbf{I}_d | \mathbf{A}']\mathbf{R}$ mod $qR$ and the secret key by $\mathbf{R} \sim B_1^{2d \times kd}$. Key recovery thus corresponds to an instance of search M-LWE$_{n,d,d,q,B_1}$ with $kd$ binomial ternary secrets. We use the lattice estimator [APS15] on the instance LWE$_{nd,nd,q,B_1}$ to determine the minimal BKZ block size $B$ among all the evaluated attacks. We discard the structure of the underlying ring and simply extend the dimensions by the ring degree $n$ by considering the matrix $M_\tau(\mathbf{A}')$. To account for the $kd$ secrets, we consider the final cost to be that of running $kd$ times BKZ which gives a cost of $kd2^{\nu B+16.4}$ for $\nu \in \{0.292, 0.257\}$.

For the zero-knowledge property of the proof system, we evaluate the hardness of M-LWE$_{\tilde{n},m_2-(\tilde{d}+256/\tilde{n}+\ell+1),m_2,\tilde{q},B_1}$ using the same method.

## A.2 Forgery and Soundness: M-SIS

The complexity of the forgery and soundness are estimated either by the M-SIS assumption. To estimate the security of M-SIS$_{n,d,m,q,\beta}$, we find the cost of finding $\mathbf{v} \in \mathcal{L}_q^{\perp}([\mathbf{I}_d | \mathbf{A}])$ such that $\|\mathbf{v}\|_2 \le \beta$ given $\mathbf{A} \sim U(R_q^{d \times m-d})$. We again look at the unstructured problem SIS$_{nd,nm,q,\beta}$. A standard optimization consists in finding a solution in a lattice of smaller dimension $nd \le m^* \le nm$ and completing the solution with zeros. We then use BKZ in block size $B$ such that

$$ \beta \ge \min_{nd \le m^* \le nm} \delta_B^{m^*} q^{nd/m^*}. $$

More precisely, for a fixed $\beta$, we find $m^*$ that maximizes $\delta_B = \beta^{1/m^*} q^{-nd/m^*}$ and then use Equation (19) to determine the corresponding block size $B$.

## A.3 Bounding the Forgery Reduction Loss

The forgery reduction loss from Theorems 5.1 and 5.2 involves the $d$-th functional power of the function $f$, which stacks up the exponents $1 - 1/2\lambda$. It makes it
slightly less intuitive to see why these d compositions do not deteriorate the reduction loss too much. For the sole sake of simplifying this intuition, we give the following bound on $h^{\circ d}$. We insist that this bound is used only to justify that the reduction is controlled despite the hybrid argument, but in the parameter selection we directly compute $h^{\circ d}$ and do not use this bound.

**Lemma A.1.** Let $a, b, c, \mu$ be positive reals, and let $\alpha$ be in $(0, 1)$. We define the function $h$ over $\mathbb{R}^+$ as

$$h: x \in \mathbb{R}^+ \mapsto a + \mu(b + \mu(c + x)^\alpha)^\alpha.$$

Then, for all positive integer $d$, it holds that for all $x \ge 0$

$$h^{\circ d}(x) \le \mu^{\frac{1}{1-\alpha}} \sum_{j \in [d]} \left( \left( \mu^{\frac{-1}{1-\alpha}} a \right)^{\alpha 2j-2} + \left( \mu^{\frac{-1}{1-\alpha}} b \right)^{\alpha 2j-1} + \left( \mu^{\frac{-1}{1-\alpha}} c \right)^{\alpha 2j} \right) \\ + \mu^{\frac{1-\alpha^2 d}{1-\alpha}} x^{\alpha 2d}$$

*Proof.* We proceed by induction on $d$. For $d=1$, we need to prove that $h(x) \le \mu^{1/(1-\alpha)} \cdot ((\mu^{-1/(1-\alpha)}a) + (\mu^{-1/(1-\alpha)}b)^\alpha + (\mu^{-1/(1-\alpha)}c)^\alpha) + \mu^{(1-\alpha^2)/(1-\alpha)}x^{\alpha^2}$ which can be re-written as $h(x) \le a + \mu b^\alpha + \mu^{1+\alpha}(c^{\alpha^2} + x^{\alpha^2})$. The inequality follows by the non-increasing property of $p$-norms for $p > 0$, that is $0 < p \le q$ implies $\|\cdot\|_q \le \|\cdot\|_p$. Here, we thus have $\|\cdot\|_1 \le \|\cdot\|_\alpha$ as $\alpha < 1$, and thus $(\sum x_i)^\alpha \le \sum x_i^\alpha$ for non-negative $x_i$. Hence, we get that for all $x \ge 0$

$$\begin{aligned} h(x) &\le a + \mu(b^\alpha + (\mu(c+x)^\alpha)^\alpha) \\ &\le a + \mu(b^\alpha + \mu^\alpha(c+x)^{\alpha^2}) \\ &\le a + \mu b^\alpha + \mu^{1+\alpha}(c^{\alpha^2} + x^{\alpha^2}). \end{aligned}$$

Now let us look at the induction step. Assume the inequality is verified at rank $d \ge 1$. Let $x \ge 0$. We have $h^{\circ(d+1)}(x) = h(h^{\circ d}(x))$. From the above, we get

$$h^{\circ(d+1)}(x) \le a + \mu b^\alpha + \mu^{1+\alpha} c^{\alpha^2} + \mu^{1+\alpha} (h^{\circ d}(x))^{\alpha^2}.$$

Then, the induction hypothesis and the inequality $\|\cdot\|_1^{\alpha^2} \le \|\cdot\|_\alpha^{\alpha^2}$ yields

$$h^{\circ d}(x)^{\alpha^2} \le \mu^{\frac{\alpha^2}{1-\alpha}} \sum_{j \in [d]} \left( \left( \mu^{\frac{-1}{1-\alpha}} a \right)^{\alpha 2j} + \left( \mu^{\frac{-1}{1-\alpha}} b \right)^{\alpha 2j+1} + \left( \mu^{\frac{-1}{1-\alpha}} c \right)^{\alpha 2j+2} \right) \\ + \mu^{\frac{\alpha^2 - \alpha^2 2d + 2}{1-\alpha}} x^{\alpha 2d + 2}.$$

Then, because $1 + \alpha + \alpha^2/(1-\alpha) = 1/(1-\alpha)$, and by reindexing the sum, we obtain

$$\mu^{1+\alpha} h^{\circ d}(x)^{\alpha^2} \le \mu^{\frac{1}{1-\alpha}} \sum_{j \in [2, d+1]} \left( \left( \mu^{\frac{-1}{1-\alpha}} a \right)^{\alpha 2j-2} + \left( \mu^{\frac{-1}{1-\alpha}} b \right)^{\alpha 2j-1} + \left( \mu^{\frac{-1}{1-\alpha}} c \right)^{\alpha 2j} \right) \\ + \mu^{\frac{1-\alpha^2 2d+2}{1-\alpha}} x^{\alpha 2d+2}.$$
Finally, we observe that $a+\mu b^\alpha+\mu^{1+\alpha}c^\alpha$ is equal to the missing term $\mu^{1/(1-\alpha)}$. $((\mu^{-1/(1-\alpha)}a)+(\mu^{-1/(1-\alpha)}b)^\alpha+(\mu^{-1/(1-\alpha)}c)^\alpha)$ which concludes the proof. $\square$

Applying the above lemma for $\alpha = 1 - 1/2\lambda$, $a = c = k\varepsilon_{\text{M-LWE}}$, $b = 2a = 2k\varepsilon_{\text{M-LWE}}$ and $\mu = 5/4$, we can bound the corresponding loss terms from Theorems 5.1 and 5.2. The additive term depending can be bounded by $\varepsilon_+ = d\mu^{1/(1-\alpha)}((a/\mu^{1/(1-\alpha)})^{\alpha^{2d-1}} + (b/\mu^{1/(1-\alpha)})^{\alpha^{2d-2}} + (c/\mu^{1/(1-\alpha)})^{\alpha^{2d}})$ which in our case yields about a 12 bit loss compared to $\varepsilon_{\text{M-LWE}}$. We then have that $h^{\circ d}(C(|T_w|-Q)\varepsilon_{\text{M-SIS}}) \le \varepsilon_+ + 6(C(|T_w|-Q)\varepsilon_{\text{M-SIS}})^{\alpha^{2d}}$. We can then plug this bound and obtain the required M-SIS hardness to achieve an advantage of $2^{-\lambda}$. In particular, for the parameters given in Table 8.4, we get that $\varepsilon_{\text{M-SIS}}$ should be smaller than $2^{-167.8}$ to ensure an advantage of at most $2^{-128}$ against type ① forgeries using the bounds we provide in this section. This is not far from the thorough parameter selection which gives a value of $2^{-166}$. Doing the same for type ② forgeries would give $2^{-171.5}$ instead of $2^{-169}$.

## B Spectral Norm Estimation

During the key generation of the signature, we need to enforce a bound on the secret key, i.e., $\|M_\tau(\mathbf{R})\|_2 \le \frac{7}{10}(\sqrt{2nd} + \sqrt{nkd} + 6)$, which requires the computation of $\|M_\tau(\mathbf{R})\|_2$. To avoid performing a singular value decomposition, we only approximate the value of $\|M_\tau(\mathbf{R})\|_2$. For that, we use the iterated power method, which we tweak to our specific use case. The iterated power method estimates the largest eigenvalue of a matrix $\mathbf{M}$ over $\mathbb{C}$ by selecting a random $\mathbf{u}$ over $\mathbb{C}$ and iterating $\ell$ times the update $\mathbf{u} \leftarrow \mathbf{M}\mathbf{u}/\|\mathbf{M}\mathbf{u}\|_2$ before returning $\mathbf{u}^H\mathbf{M}\mathbf{u}$ as the estimate of $\lambda_{\max}(\mathbf{M})$. The method is rather simple, but usually converges faster when $\mathbf{M}$ has separated eigenvalues, which is not the case of $M_\tau(\mathbf{R})M_\tau(\mathbf{R})^T$ where each eigenvalue is doubled by conjugation symmetry.

We thus change the approach to optimize this computation. First, we observe that $\|M_\tau(\mathbf{R})\|_2 = \max_{i \in [n]} \|\sigma_i(\mathbf{R})\|_2$ by [BJRW23, Lem. 2.3], where the $\sigma_i$ are the complex embeddings of the field. As we work in cyclotomic fields, the conjugation symmetry allows to only look at $n/2$ embeddings. Hence, we have

$$ \|M_{\tau}(\mathbf{R})\|_2 = \max_{i \in [n/2]} \|\sigma_i(\mathbf{R})\|_2 = \max_{i \in [n/2]} \sqrt{\lambda_{\max}(\sigma_i(\mathbf{R}\mathbf{R}^*))} $$

We thus only have to estimate $n/2$ maximal eigenvalues of complex matrices with small dimensions ($\mathbb{C}^{2d \times 2d}$). For that we can update the iterated power method as follows. First, the updated vector $\mathbf{u}$ does not have to be re-normalize at each step, meaning that the estimate computes $\tilde{\mathbf{u}} = \mathbf{M}^\ell \mathbf{u}$ and returns $\tilde{\mathbf{u}}^H \tilde{\mathbf{u}}/\|\tilde{\mathbf{u}}\|_2^2 = \mathbf{u}^H \mathbf{M}^{2\ell+1} \mathbf{u}/\mathbf{u}^H \mathbf{M}^{2\ell} \mathbf{u}$. Second, the starting vector $\mathbf{u}$ does not need to be random. In our experiments, choosing $\mathbf{u}$ to be the first column of $\mathbf{M}$ actually converges faster. In this case, the output value is

$$ \frac{\mathbf{e}_1^T \mathbf{M}^{2\ell+3} \mathbf{e}_1}{\mathbf{e}_1^T \mathbf{M}^{2\ell+2} \mathbf{e}_1} = \frac{[\mathbf{M}^{2\ell+3}]_{1,1}}{[\mathbf{M}^{2\ell+2}]_{1,1}} $$
Since $\mathbf{M}$ is some $\sigma_i(\mathbf{RR}^*)$, we have that

$$ \|M_{\tau}(\mathbf{R})\|_2^2 \approx \max_{i \in [n/2]} \frac{\sigma_i((\mathbf{RR}^*)^{2\ell+3})_{1,1}}{\sigma_i((\mathbf{RR}^*)^{2\ell+2})_{1,1}}. $$

To minimize the number of matrix multiplications, we choose $\ell = 2^{\ell'} - 1$. As we need to compute $\mathbf{RR}^*$ to generate the perturbation sampling material, the spectral norm estimation thus requires $\ell' + 1$ matrix multiplication over $\mathbb{R}^{2d \times 2d}$ to get $(\mathbf{RR}^*)^{2\ell+2}$, 1 extra multiplication to get $(\mathbf{RR}^*)^{2\ell+3}$ and then the computation of $2 \cdot n/2$ complex embeddings, i.e., two half FFT. In our implementation, we choose $\ell' = 4$ which gives the estimate

$$ \|M_{\tau}(\mathbf{R})\|_2^2 \approx \max_{i \in [n/2]} \frac{\sigma_i((\mathbf{RR}^*)^{33})_{1,1}}{\sigma_i((\mathbf{RR}^*)^{32})_{1,1}}. $$

It approximates the actual norm with at least $10^{-5}$ precision, which is more than sufficient for our purposes. We note that although this estimate is rather fast, it requires computing $(\mathbf{RR}^*)^{33}$ in $\mathbb{R}$ and not $R_q$. As a result, the coefficients of $(\mathbf{RR}^*)^{33}$ become extremely large (around 420 bits) which calls for multi-precision integers. The renormalization in the iterated power method may mitigate this blow-up of coefficients but would require working over the complex embedded matrices directly. It in turn leads to more FFT computations (for all the matrix embeddings) and operations over floating-point complex numbers.
<table><caption>Table 8.4. Example parameter set for Anonymous Credentials (Signature Scheme).</caption><thead><tr><th>Symbol</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td colspan="3"><strong>Signature Parameters</strong></td></tr><tr><td>λ</td><td>Security target</td><td>128</td></tr><tr><td>n</td><td>Signature ring degree</td><td>256</td></tr><tr><td>d</td><td>Module rank</td><td>4</td></tr><tr><td>m</td><td>Number of attributes</td><td>10</td></tr><tr><td>m<sub>s</sub></td><td>Secret dimension (2d)</td><td>8</td></tr><tr><td>q</td><td>Modulus</td><td>425801 ≈ 2<sup>18.7</sup></td></tr><tr><td>k</td><td>Gadget length</td><td>5</td></tr><tr><td>b</td><td>Gadget base</td><td>14</td></tr><tr><td>ε</td><td>Smoothing loss for samplers</td><td>2<sup>-40</sup></td></tr><tr><td>s<sub>1</sub></td><td>Top preimage sampling width</td><td>5854.109</td></tr><tr><td>s<sub>2</sub></td><td>Bottom preimage sampling width</td><td>68.170</td></tr><tr><td>w</td><td>Hamming weight of tags</td><td>5</td></tr><tr><td>κ</td><td>Number of splitting factors of q</td><td>4</td></tr><tr><td>Q</td><td>Maximal number of signature queries</td><td>2<sup>32</sup></td></tr><tr><td>α</td><td>Rejection sampling slack (type ②)</td><td>2.63997</td></tr><tr><td>M</td><td>Rejection sampling repetition rate (type ②)</td><td>1.569</td></tr><tr><td>B'<sub>1</sub></td><td>First verification bound</td><td>128719.006</td></tr><tr><td>B<sub>2</sub></td><td>Second verification bound</td><td>2210.639</td></tr><tr><td>B<sub>3</sub></td><td>Third verification bound</td><td>1242.685</td></tr><tr><td colspan="3"><strong>Security Estimates</strong></td></tr><tr><td>λ<sub>●</sub></td><td>Security target for M-SIS (type ①)</td><td>166</td></tr><tr><td>λ<sub>●</sub></td><td>Security target for M-SIS (type ②)</td><td>169</td></tr><tr><td>λ<sub>KR</sub></td><td>Security target for M-LWE (key recovery)</td><td>152</td></tr><tr><td>β<sub>●</sub></td><td>Euclidean bound for M-SIS (type ①)</td><td>199463</td></tr><tr><td>β<sub>●</sub></td><td>Euclidean bound for M-SIS (type ②)</td><td>401099</td></tr><tr><td>BKZ<sub>●</sub></td><td>Required BKZ blocksize for M-SIS (type ①)</td><td>653</td></tr><tr><td>BKZ<sub>●</sub></td><td>Required BKZ blocksize for M-SIS (type ②)</td><td>560</td></tr><tr><td>BKZ<sub>KR</sub></td><td>Required BKZ blocksize for M-LWE (key recovery)</td><td>486</td></tr><tr><td>λ<sup>*</sup><sub>●</sub></td><td>Reached M-SIS (classical) security (type ①)</td><td>207</td></tr><tr><td>λ<sup>*</sup><sub>●</sub></td><td>Reached M-SIS (classical) security (type ②)</td><td>179</td></tr><tr><td>λ<sup>*</sup><sub>KR</sub></td><td>Reached M-LWE (classical) security (key recovery)</td><td>158</td></tr><tr><td colspan="3"><strong>Efficiency Estimates</strong></td></tr><tr><td>|pk|</td><td>Size of public key (B, rest generated from seeds)</td><td>47.5 KB</td></tr><tr><td>|sk|</td><td>Size of secret key (R)</td><td>10 KB</td></tr><tr><td>|sig|</td><td>Size of signature (t, v<sub>1,2</sub>, v<sub>2</sub>, v<sub>3</sub>)</td><td>6.81 KB</td></tr></tbody></table>
<table><caption>**Table 8.5.** Example parameter set for Anonymous Credentials (Proof System) for the issuance proof.</caption><thead><tr><th>Symbol</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td colspan="3"><strong>Proof System Parameters</strong></td></tr><tr><td>λ</td><td>Security target</td><td>130</td></tr><tr><td>⟨n</td><td>Proof system ring degree</td><td>64</td></tr><tr><td>⟨k</td><td>Subring embedding dimension</td><td>4</td></tr><tr><td>⟨d</td><td>Module rank</td><td>20</td></tr><tr><td>q<sub>1</sub></td><td>Modulus factor</td><td>524201 ≈ 2<sup>19</sup></td></tr><tr><td>q<sub>min</sub></td><td>Smallest modulus factor</td><td>425801</td></tr><tr><td>⟨q</td><td>Proof system modulus (qq<sub>1</sub>)</td><td>223205310001</td></tr><tr><td>ℓ</td><td>Soundness amplification dimension</td><td>7</td></tr><tr><td>|I|</td><td>Number of disclosed attributes</td><td>0</td></tr><tr><td>m<sub>1</sub></td><td>Witness dimension</td><td>104</td></tr><tr><td>m<sub>2</sub></td><td>Dimension of ABDROP randomness</td><td>58</td></tr><tr><td>χ</td><td>Distribution of ABDROP randomness</td><td>B<sub>1</sub></td></tr><tr><td>ρ</td><td>Infinity norm of challenges</td><td>8</td></tr><tr><td>η</td><td>Manhattan-like norm of challenges</td><td>93</td></tr><tr><td>(α<sub>1</sub>, α<sub>2</sub>, α<sub>3</sub>)</td><td>Rejection sampling slacks</td><td>(48.64, 48.64, 48.64)</td></tr><tr><td>(M<sub>1</sub>, M<sub>2</sub>, M<sub>3</sub>)</td><td>Rejection sampling repetition rates</td><td>(2, 2, 2)</td></tr><tr><td>σ<sub>1</sub></td><td>First rejection sampling width</td><td>369050.897</td></tr><tr><td>σ<sub>2</sub></td><td>Second rejection sampling width</td><td>275602.779</td></tr><tr><td>σ<sub>3</sub></td><td>Third rejection sampling width</td><td>72848.106</td></tr><tr><td colspan="3"><strong>Security Estimates</strong></td></tr><tr><td>β</td><td>Euclidean bound for M-SIS</td><td>11551631225.350</td></tr><tr><td>BKZ<sub>M-SIS</sub></td><td>Required BKZ blocksize for M-SIS</td><td>395</td></tr><tr><td>BKZ<sub>M-LWE</sub></td><td>Required BKZ blocksize for M-LWE</td><td>386</td></tr><tr><td>λ<sup>*</sup><sub>M-SIS</sub></td><td>Reached M-SIS (classical) security</td><td>131</td></tr><tr><td>λ<sup>*</sup><sub>M-LWE</sub></td><td>Reached M-LWE (classical) security</td><td>129</td></tr><tr><td>δ</td><td>Soundness error</td><td>2<sup>-128.26</sup></td></tr><tr><td colspan="3"><strong>Efficiency Estimates</strong></td></tr><tr><td>|π|</td><td>Verification proof size</td><td>35.99 KB</td></tr></tbody></table>
<table><caption>**Table 8.6.** Example parameter set for Anonymous Credentials (Proof System) for the verification proof.</caption><thead><tr><th>Symbol</th><th>Description</th><th>Value</th></tr></thead><tbody><tr><td colspan="3"><strong>Proof System Parameters</strong></td></tr><tr><td>λ</td><td>Security target</td><td>128</td></tr><tr><td>⟨n</td><td>Proof system ring degree</td><td>64</td></tr><tr><td>⟨k</td><td>Subring embedding dimension</td><td>4</td></tr><tr><td>⟨d</td><td>Module rank</td><td>23</td></tr><tr><td>q<sub>1</sub></td><td>Modulus factor</td><td>549755813881 ≈ 2<sup>39</sup></td></tr><tr><td>q<sub>min</sub></td><td>Smallest modulus factor</td><td>425801</td></tr><tr><td>⟨q</td><td>Proof system modulus (qq<sub>1</sub>)</td><td>234086575306343681</td></tr><tr><td>ℓ</td><td>Soundness amplification dimension</td><td>7</td></tr><tr><td>|I|</td><td>Number of disclosed attributes</td><td>0</td></tr><tr><td>m<sub>1</sub></td><td>Witness dimension</td><td>211</td></tr><tr><td>m<sub>2</sub></td><td>Dimension of ABDROP randomness</td><td>74</td></tr><tr><td>χ</td><td>Distribution of ABDROP randomness</td><td>B<sub>1</sub></td></tr><tr><td>ρ</td><td>Infinity norm of challenges</td><td>8</td></tr><tr><td>η</td><td>Manhattan-like norm of challenges</td><td>93</td></tr><tr><td>(α<sub>1</sub>, α<sub>2</sub>, α<sub>3</sub>)</td><td>Rejection sampling slacks</td><td>(48.64, 48.64, 48.64)</td></tr><tr><td>(M<sub>1</sub>, M<sub>2</sub>, M<sub>3</sub>)</td><td>Rejection sampling repetition rates</td><td>(2, 2, 2)</td></tr><tr><td>σ<sub>1</sub></td><td>First rejection sampling width</td><td>582380223.293</td></tr><tr><td>σ<sub>2</sub></td><td>Second rejection sampling width</td><td>311304.541</td></tr><tr><td>σ<sub>3</sub></td><td>Third rejection sampling width</td><td>114957846.739</td></tr><tr><td colspan="3"><strong>Security Estimates</strong></td></tr><tr><td>β</td><td>Euclidean bound for M-SIS</td><td>21756342921843.957</td></tr><tr><td>BKZ<sub>M-SIS</sub></td><td>Required BKZ blocksize for M-SIS</td><td>396</td></tr><tr><td>BKZ<sub>M-LWE</sub></td><td>Required BKZ blocksize for M-LWE</td><td>382</td></tr><tr><td>λ<sup>*</sup><sub>M-SIS</sub></td><td>Reached M-SIS (classical) security</td><td>132</td></tr><tr><td>λ<sup>*</sup><sub>M-LWE</sub></td><td>Reached M-LWE (classical) security</td><td>127</td></tr><tr><td>δ</td><td>Soundness error</td><td>2<sup>-128.37</sup></td></tr><tr><td colspan="3"><strong>Efficiency Estimates</strong></td></tr><tr><td>|π|</td><td>Verification proof size</td><td>79.58 KB</td></tr></tbody></table>