- The blindness game for $\mathcal{A}$ is simulated by $\mathcal{B}_3$: computes then sends $(c, c_Z, \pi_{\text{ped}})$ to $\mathcal{A}$, simulates $H_{\text{fis}}$ and queries the RO for other $H_{\text{ped}}$ queries, receives $(z, a)$ from $\mathcal{A}$. At the step of derived signature, $\mathcal{B}_3$ queries its S-ZK challenger on

$$x_{\text{fis}} = (\text{pp}_I, N, h_1, h_2, h, \bar{m}, c_I), w_{\text{fis}} = (e, a, y, r_I, d_I)$$

to get $\pi_{\text{fis}}$. We note that $\mathcal{B}_3$ possesses the witness $w_{\text{fis}}$ throughout the signing session that is simulated to $\mathcal{A}$ (see Fig. 1). Then $\mathcal{B}_3$ outputs $(\pi_{\text{fis}}, c_I)$ as the derived signature.

- $\mathcal{B}_3$ outputs what $\mathcal{A}$ outputs.

We argue that $\mathcal{B}_3$ is breaking S-ZK of $\Pi_{\text{fis}}$:

- Following Definition 23, Game 2 corresponds to the simulated case in the S-ZK game for $\Pi_{\text{fis}}$, where $\mathcal{B}_3$ receives $\text{urs}_{\text{fis}}$ and outputs a possibly subverted $\text{srs}_{\text{fis}}$, then interacts with $\text{Sim}_{\text{H,fis}}$. The proofs in the derived signatures by $\mathcal{B}_3$ during signing sessions with $\mathcal{A}$ are simulated by $\pi_{\text{fis}} \leftarrow \text{Sim}_{\pi, \text{fis}}(\text{crs}_{\text{fis}}, x_{\text{fis}})$, where $\text{crs}_{\text{fis}} = (\text{srs}_{\text{fis}}, \text{urs}_{\text{fis}})$.

- On the other hand Game 1 correspond to the real case in Definition 23, where the adversary receives $\text{urs}_{\text{fis}}$ and output a possibly subverted $\text{srs}_{\text{fis}}$, then interacts with $H$. The proofs in the derived signatures by $\mathcal{B}_3$ during signing sessions with $\mathcal{A}$ are computed by $\text{Prove}^H(\text{crs}, x, w)$ where $\text{crs}_{\text{fis}} = (\text{srs}_{\text{fis}}, \text{urs}_{\text{fis}})$.

Conditioned on the foregoing case, the advantage that $\mathcal{A}$ can distinguish Game 2 from Game 1 is bounded by $\text{Adv}_{\mathcal{B}_3, \Pi_{\text{fis}}}^{\text{sub-zk}}(\lambda)$ against the subversion zero-knowledge property of $\Pi_{\text{fis}}$.

Totally, the probability that $\mathcal{A}$ can distinguish Game 2 from Game 1 is bounded by

$$\text{Adv}_{\mathcal{B}_2, \Pi_{\text{gen}}}^{\text{snd}}(\lambda) + \text{Adv}_{\mathcal{B}_3, \Pi_{\text{fis}}}^{\text{sub-zk}}(\lambda) + \text{negl}(\lambda)$$

for PPT adversaries $\mathcal{B}_2, \mathcal{B}_3$ as described above. Assuming the subversion zero-knowledge of $\Pi_{\text{fis}}$ as well as the subversion adaptive soundness of $\Pi_{\text{gen}}$ against all such PPT $\mathcal{B}_2, \mathcal{B}_3$, Game 2 are indistinguishable from Game 1. $\square$

**Game 3:** This hybrid is the same as Game 2, except that we make $c_I$ independent of the blindness adversary's response $(z, a, \pi_{\text{sub}})$. More specifically, we change the computation $(c_I, d_I) \leftarrow C_{\text{RInt}}.\text{Commit}(\text{pp}_I, (0, 0), r_I)$ for $r_I \leftarrow C_{\text{RInt}}.C_{\text{rnd}}$. We argue that this change is indistinguishable using the fact that $r_I$ is information theoretically hidden thanks to the simulation of $\pi_{\text{fis}}$ from Game 2 as well as the hiding property of $C_{\text{RInt}}$. Indeed, we construct a simulator $\mathcal{B}$ against the hiding game of $C_{\text{RInt}}$ that simulates Game 3. At the time of computing $c_I$, $\mathcal{B}$ outputs two messages $(a, e - \bar{E})$ and $(0, 0)$ when interacting with the hiding game's challenger, to receive $c_I$. Finally, $\mathcal{B}$ uses $c_I$ in the derived signature $\sigma = (\pi_{\text{fis}}, c_I)$ to the blindness adversary $\mathcal{A}$ and outputs what $\mathcal{A}$ outputs. We have

$$|\text{Adv}_{\mathcal{A}, \text{Game 3}}^{\text{blind}}(\lambda) - \text{Adv}_{\mathcal{A}, \text{Game 2}}^{\text{blind}}(\lambda)| \le \text{Adv}_{\mathcal{B}, C_{\text{RInt}}}^{\text{hide}}(\lambda)$$

and is negligible in $\lambda$.

**Game 4:** This hybrid is the same as Game 3, except that we use the subversion zero-knowledge simulator $\text{Sim}_{\text{ped}} = (\text{Sim}_{\text{H,ped}}, \text{Sim}_{\pi, \text{ped}})$ of $\Pi_{\text{ped}}$ to simulate $\pi_{\text{ped}}$ in the first message $(c, c_Z, \pi_{\text{ped}})$. Game 4 differs from Game 3 in the following details. We program the unstructured reference string $\text{urs}_{\text{ped}}$ in $(\text{urs}_{\text{ped}}, \text{urs}_{\text{fis}}, \text{urs}_{\text{gen}}) \leftarrow H_{\text{urs}}(0)$ together with honest $\text{urs}_{\text{fis}}, \text{urs}_{\text{gen}} \in \mathcal{URS}$. The blindness adversary $\mathcal{A}$ also sets up $\text{srs}_{\text{zkp}}$ for $\text{zkp} \in \{\text{ped}, \text{fis}, \text{gen}\}$. The common reference strings are defined, in particular $\text{crs}_{\text{ped}} = (\text{srs}_{\text{ped}}, \text{urs}_{\text{ped}})$ along with $\text{crs}_{\text{fis}}, \text{crs}_{\text{gen}}$ in $\text{bvk}$. We also program $H_{\text{ped}}$ by $\text{Sim}_{\text{H,ped}}$ for further RO queries. We afterwards run $\pi_{\text{ped}} \leftarrow \text{Sim}_{\pi, \text{ped}}(\text{crs}_{\text{ped}}, x_{\text{ped}})$. The following lemma 8 argues that this simulation of $\pi_{\text{ped}}$ is indistinguishable from the real proofs. The following lemma 8 argues that Game 4 and Game 3 are indistinguishable. In particular, for any blindness adversary $\mathcal{A}$, there exist PPT $\mathcal{B}_1, \mathcal{B}_2$ so that

$$|\text{Adv}_{\mathcal{A}, \text{Game 4}}^{\text{blind}}(\lambda) - \text{Adv}_{\mathcal{A}, \text{Game 3}}^{\text{blind}}(\lambda)| \le \text{Adv}_{\mathcal{B}_1, \Pi_{\text{gen}}}^{\text{snd}}(\lambda) + \text{Adv}_{\mathcal{B}_2, \Pi_{\text{ped}}}^{\text{sub-zk}}(\lambda)$$

and is negligible in $\lambda$.
**Lemma 8.** Under the subversion zero-knowledge of $\Pi_{\text{ped}}$ as well as the subversion adaptive soundness of $\Pi_{\text{gen}}$, the games Game 4 and Game 3 are indistinguishable. For any blindness adversary $\mathcal{A}$, there exist PPT $\mathcal{B}_1, \mathcal{B}_2$ so that

$$|\text{Adv}_{\mathcal{A}, \text{Game } 4}^{\text{blind}}(\lambda) - \text{Adv}_{\mathcal{A}, \text{Game } 3}^{\text{blind}}(\lambda)| \le \text{Adv}_{\mathcal{B}_1, \Pi_{\text{gen}}}^{\text{snd}}(\lambda) + \text{Adv}_{\mathcal{B}_2, \Pi_{\text{ped}}}^{\text{sub-zk}}(\lambda).$$

*Proof.* By construction, with respect to the relation $R_{\text{ped}}$, the values $\bar{m}, r, (c_Z, d_Z)$ determined by the user satisfy:

$$\left\{ \begin{array}{l} \text{CZ. Verify}(\text{pp}, c_Z, (\bar{m}, r), d_Z) = 1 \\ \bar{m} \in [0, 2^\lambda - 1] \\ r \in [0, S] \end{array} \right. .$$

We recall that $c = h_2^{\bar{m}} \cdot g^{re} \bmod N$ is computed by the user in this Game 4, as part of the first message that is sent to the adversarial signer. Now, using the simulation as described in Game 2, there are three cases to treat as follows:

**Case 1** Suppose $x_{\text{ped}} \notin \mathcal{L}_{R_{\text{ped}}}$ and $c \notin \langle g \rangle$. This implies $\langle g \rangle \neq \langle h_2 \rangle$. As we are supposing $\Pi_{\text{gen}}$. Verify$^{\text{H}_{\text{gen}}}$($crs_{\text{gen}}$, $x_{\text{gen}}$, $\pi_{\text{gen}}$) = 1$, without loss of generality so that all **check** pass, the instance $(N, 3, g, (h, h_1, h_2))$ breaks the subversion soundness of $\Pi_{\text{gen}}$. We provide a PPT adversary $\mathcal{B}_1$ breaking the subversion soundness of $\Pi_{\text{gen}}$ as follows:

- $\mathcal{B}_1$ simulates Game 4 by programming the unstructured reference string $urs_{\text{ped}}$ in $H_{\text{urs}}(0)$ together with honest $urs_{\text{fis}} \in \text{URS}$. Then $\mathcal{B}_1$ receives $urs_{\text{gen}}$ from its subversion soundness challenger.

- The blindness adversary $\mathcal{A}$ sets up $\text{srs}_{\text{zkp}}$ for $\text{zkp} \in \{\text{ped}, \text{fis}, \text{gen}\}$. The common reference strings are defined, in particular $crs_{\text{ped}} = (\text{srs}_{\text{ped}}, \text{urs}_{\text{ped}})$ along with $crs_{\text{ped}}, crs_{\text{gen}}$ in **bvk**.

- Specifically, as soon as $\mathcal{A}$ outputs

$$\text{bvk} = (\text{crs}_{\text{fis}}, \text{crs}_{\text{ped}}, \text{crs}_{\text{gen}}, N, h, h_1, h_2, g, \pi_{\text{gen}})$$

$\mathcal{B}_1$ outputs the instance $(N, 3, g, (h, h_1, h_2))$ to its challenger against the subversion soundness of $\Pi_{\text{gen}}$.

Hence, the probability of this case is bounded by $\text{Adv}_{\mathcal{B}_1, \Pi_{\text{gen}}}^{\text{snd}}(\lambda)$ for some PPT $\mathcal{B}_1$ against the subversion soundness of $\Pi_{\text{gen}}$.

**Case 2** Suppose $x_{\text{ped}} \in \mathcal{L}_{R_{\text{ped}}}$ The adversary $\mathcal{A}$ can be used to construct a PPT $\mathcal{B}_2$ against the subversion zero-knowledge (S-ZK) game of $\Pi_{\text{ped}}$ as follows:

- $\mathcal{B}_2$ receives $urs_{\text{ped}}$ from the S-ZK challenger and program $urs_{\text{ped}}$ into the output of $H_{\text{urs}}(0)$, together with honest $urs_{\text{fis}}, urs_{\text{gen}} \in \text{URS}$.

- The blindness adversary $\mathcal{A}$ sets up $crs_{\text{ped}}$ as part of **bvk**. $\mathcal{B}_2$ parses $crs_{\text{ped}} = (\text{srs}_{\text{ped}}, \text{urs}_{\text{ped}})$ and outputs $\text{srs}_{\text{ped}}$ to the S-ZK challenger for $\Pi_{\text{ped}}$.

- The blindness game for $\mathcal{A}$ is simulated by $\mathcal{B}_2$. First of all $\mathcal{B}_2$ queries its S-ZK challenger on

$$x_{\text{ped}} = (\text{pp}, N, e, h_2, g, c, c_Z), w_{\text{ped}} = (\bar{m}_0, r, d_Z)$$

to get $\pi_{\text{ped}}$. We note that $\mathcal{B}_2$ possesses the witness $w_{\text{ped}}$, where $\bar{m}_0 := H(m_0)$, throughout the signing session that is simulated to $\mathcal{A}$ (see Fig. 1). Then $\mathcal{B}_2$ sends $(c, c_Z, \pi_{\text{ped}})$ to $\mathcal{A}$, queries the RO for other $H_{\text{sub}}, H_{\text{fis}}$ queries, receives $(z, a, \pi_{\text{sub}})$ from $\mathcal{A}$. Finally, $\mathcal{B}_2$ derives and outputs $(\pi_{\text{fis}}, c_I)$ as the derived signature.

- $\mathcal{B}_2$ outputs what $\mathcal{A}$ outputs.

We argue that $\mathcal{B}_2$ is breaking S-ZK of $\Pi_{\text{ped}}$:

- Following Definition 23, Game 4 corresponds to the simulated case, where the adversary receives $urs_{\text{ped}}$ and outputs a possibly subverted $\text{srs}_{\text{ped}}$, then interacts with $\text{Sim}_{H_{\text{ped}}}$ The proofs in the derived signatures by $\mathcal{B}_2$ during signing sessions with $\mathcal{A}$ are simulated by $\pi_{\text{ped}} \leftarrow \text{Sim}_{\pi_{\text{ped}}}(\text{crs}_{\text{ped}}, x_{\text{ped}})$, where $\text{crs}_{\text{ped}} = (\text{srs}_{\text{ped}}, \text{urs}_{\text{ped}})$.

- On the other hand Game 3 correspond to the real case in Definition 23, where the adversary receives $urs_{\text{ped}}$ and output a possibly subverted $\text{srs}_{\text{ped}}$, then interacts with $\mathcal{H}$. The proofs in the derived signatures by $\mathcal{B}_2$ during signing sessions with $\mathcal{A}$ are computed by $\text{Prove}^{\text{H}}(\text{crs}, x, w)$ where $\text{crs}_{\text{ped}} = (\text{srs}_{\text{ped}}, \text{urs}_{\text{ped}})$.
Conditioned on the foregoing case, the advantage that $\mathcal{A}$ can distinguish Game 4 from Game 3 is bounded by $\text{Adv}_{B_2, \Pi_{\text{ped}}}^{\text{sub-zk}}(\lambda)$ against the subversion zero-knowledge property of $\Pi_{\text{ped}}$.

Totally, the probability that $\mathcal{A}$ can distinguish Game 4 from Game 3 is bounded by

$$ \text{Adv}_{B_1, \Pi_{\text{gen}}}^{\text{snd}}(\lambda) + \text{Adv}_{B_2, \Pi_{\text{ped}}}^{\text{sub-zk}}(\lambda) $$

for some PPT $B_1, B_2$. Assuming the subversion zero-knowledge of $\Pi_{\text{ped}}$ as well as the subversion adaptive soundness of $\Pi_{\text{gen}}$ against all such PPT $B_1, B_2$, Game 4 are indistinguishable from Game 3. $\square$

**Game 5:** This hybrid is the same as Game 4, except that we replace $c$ in the first user's message by $c \leftarrow \langle g \rangle$. This transition is statistical. By the union bound, the advantage of any possibly unbounded adversary $\mathcal{A}$ to distinguish between this Game 5 and the previous Game 4 can be bounded by considering two cases:

**Case 1** The replacement $c \leftarrow \langle g \rangle$ is distinguishable from the previous computation

$$ c = h_2^{\overline{m}} \cdot g^{re} \mod N $$

in Game 4 because $\langle g \rangle \neq \{h_2^x \cdot g^y \mod N | x, y \in \mathbb{N}\}$. This implies that $\langle h_2 \rangle \neq \langle g \rangle$ and under our hypothesis that $\Pi_{\text{gen}}$. Verify $\Pi_{\text{gen}}$ (crs$_{\text{gen}}$, $x_{\text{gen}}$, $\pi_{\text{gen}}$) = 1$, this implies the adversary $\mathcal{A}$ can output $(N, 3, g, (h, h_1, h_2))$ that breaks the subversion soundness of $\Pi_{\text{gen}}$. We provide a PPT adversary $B_1$ breaking the subversion soundness of $\Pi_{\text{gen}}$ in the same manner as **Case 1** in Game 4. The probability of this case is bounded by $\text{Adv}_{B_1, \Pi_{\text{gen}}}^{\text{snd}}(\lambda)$ for some PPT $B_1$ against the statistical subversion soundness of $\Pi_{\text{gen}}$.

**Case 2** Else, suppose that $\langle h_2 \rangle = \langle g \rangle$. By lemma 2 under the fact that $H_P$ is uniform over $S_e$ where $|S_e| = \Omega(2^{2\lambda})$, with overwhelming probability we have $\langle g^{re} \rangle = \langle g \rangle$. This means we can write $c = h_2^{\overline{m}} \cdot \overline{g}^r \mod N$ for some generator $\overline{g} := g^e$ of $\langle g \rangle = \langle h_2 \rangle$, thus has the form of a Pedersen commitment over $\langle g \rangle$. Therefore, because $r \leftarrow [0, S]$, where $S = N \cdot 2^{\lambda}$ is exponentially large in $\lambda$, remark 3 implies the statistical hiding of the commitment $c = h_2^{\overline{m}} \cdot \overline{g}^r \mod N$ that encures the advantage of distinguishing of $\mathcal{A}$ in this case is negl($\lambda$).

By combining the two cases, we conclude that the probability a blindness adversary $\mathcal{A}$ can distinguish Game 5 from Game 4 is bounded by $\text{Adv}_{B_1, \Pi_{\text{gen}}}^{\text{snd}}(\lambda) + \text{negl}(\lambda)$, for some PPT $B_1$, and thus negligible under the subversion soundness of $\Pi_{\text{gen}}$.

**Game 6:** This hybrid is the same as Game 5, except that we make $c_Z$ independent of the adversary's response. More specifically, we change the computation $(c_Z, d_Z) \leftarrow C_{\text{RInt}}$. Commit $(pp_Z, (0, r))$ for $r \leftarrow [0, S]$. We argue that this change is indistinguishable by constructing a simulator $\mathcal{B}$ against the hiding game of $C_{\text{RInt}}$ that simulates Game 6. At the time of computing $c_Z$, $\mathcal{B}$ outputs two messages $(\overline{m}_0, r)$ and $(0, 0)$ when interacting with the hiding game's challenger, to receive $c_Z$. We are using the fact that $r$ is information theoretically hidden thanks to the simulation of $\pi_{\text{fis}}$ from Game 2, the simulation of $\pi_{\text{ped}}$ from Game 4, and the replacement of the commitment $c \leftarrow \langle g \rangle$ from Game 5. Finally, $\mathcal{B}$ uses $c_Z$ in the first message $(c, c_Z, \pi_{\text{ped}})$ to the blindness adversary $\mathcal{A}$ and outputs what $\mathcal{A}$ outputs. We have

$$ |\text{Adv}_{\mathcal{A}, \text{Game } 6}(\lambda) - \text{Adv}_{\mathcal{A}, \text{Game } 5}(\lambda)| \leq \text{Adv}_{\mathcal{B}, C_{\text{RInt}}}(\lambda) $$

and is negligible in $\lambda$.

**Game 7:** We note that after hopping to Game 6, the first message $(c, c_Z, \pi_{\text{ped}})$ as well as the derived signature $(\pi_{\text{fis}}, c_I)$ do not depend on $\overline{m}_0$ anymore. We then apply a similar sequence of hoppings, but symmetrically in a reverse order to go to the game following Definition 3 where coin = 1, i.e. $\overline{m}_1$ is used in the first message and the derived signature. The above arguments still apply so that the transitions stay indistinguishable. In total, we have proved that

$$ 2 \cdot \text{Adv}_{\mathcal{A}, \text{BS}_{\text{fis}}}^{\text{blind}}(\lambda) = |\text{Adv}_{\mathcal{A}, \text{Game } 1}^{\text{blind}}(\lambda) - \text{Adv}_{\mathcal{A}, \text{Game } 7}^{\text{blind}}(\lambda)| $$

is negligible in $\lambda$ and the proof is completed. $\square$
**Remark 6.** We now give more details on the argument when some checks in the blindness game are not passed. Suppose there is $m_b$ among the blindness challenges $(m_0, m_1)$ such that one of the checks in User or Derive does not pass.

- If the failed check is in User : The only check therein is on bvk, independent from $(m_0, m_1)$, hence the first signing messages from User are

$$ \rho_{1,0} = \rho_{1,1} = \perp $$

independent from coin. Consequently, for whatever second signing messages $\rho_{2,0}$ and $\rho_{2,1}$ that A outputs, we have $\sigma_0 = \sigma_1 = \perp$. Therefore, its advantage to output coin correctly is 0.

- If the failed check is in Derive : this implies that the Fischlin $S_{fis}$.Verify(vk, $m_b$, $\sigma_b$) = 1 does not pass for some $b \in \{0,1\}$. Then our Derive algorithm outputs $\sigma_b = \perp$ and therefore Verify(bvk, $m_b$, $\sigma_b$) = 0. Thus the ‘if’ condition in Definition 3 is satisfied, implying both derived signatures are set

$$ \sigma_0 = \sigma_1 = \perp $$

and vacuously do not depend on $(m_0, m_1)$. Hence, by combining the aforementioned with the fact that the check in User passes in this current case, an argument similar to our game hops Game 4→ Game 5 → Game 6 in the blindness proof argue that the first signing messages $\rho_{1,0}$ and $\rho_{1,1}$ can be made independent from coin as well. This concludes that in this case A's advantage to correctly output coin stays negligible in $\lambda$ (union bound, 0 from the derived signatures and negligible from the first signing messages).

Finally, it remains to argue that whether the check(s) fail(s) or not does not depend on the blindness challenger's coin. This is clear for the check in User that is only on bvk and does not involve coin. With respect to the check in Derive, conditioned that the check in User passes, the first signing messages $\rho_{1,0}$ and $\rho_{1,1}$ of our scheme (will be given to the adversary as defined in the blindness game Definition 3) can be made independent from coin in the same vein of the game hops Game 4→ Game 5 → Game 6 in the blindness proof. Therefore, the event that “the check in Derive fails” in the adversary's view, given $\rho_{1,0}$ and $\rho_{1,1}$, happens independently from coin.

## D.4 One-More Unforgeability Proof of $BS_{fis}$

*Proof.* We prove this using a series of games to rule out some cases in which the reduction won't work.

*Game 1:* This is the one-more-unforgeability game.

*Game 2:* In this game we introduce an abort condition. Namely, the game aborts if there is a collision in the hash oracle H, i.e. if the adversary during the game makes two queries $\zeta, \zeta'$ to H such that $H(\zeta) = H(\zeta')$, but $\zeta \neq \zeta'$.

**Lemma 9.** $|\text{Adv}_{A, \text{Game } 1}(\lambda) - \text{Adv}_{A, \text{Game } 2}(\lambda)| \le Q_H^2/2 \cdot 2^{2\lambda}$

*Proof.* Birthday bound.

*Game 3:* In this game we introduce an abort condition. Namely, the game aborts if there is a collision in the hash oracle $H_P$, i.e. if the adversary during the game makes two queries $\zeta, \zeta'$ to $H_P$ such that $H_P(\zeta) = H_P(\zeta')$, but $\zeta \neq \zeta'$.

**Lemma 10.** $|\text{Adv}_{A, \text{Game } 2}(\lambda) - \text{Adv}_{A, \text{Game } 3}(\lambda)| \le \text{negl}(\lambda)$

*Proof.* This follows via a birthday bound since due to lemma 1, the image of $H_P$ is of exponential size.
**Game 4:** In this game, we alter how the parameters for $C_Z$ are set up. Namely, we use the algorithm $\Pi_{ped}.Ext_1$ to set up the parameters for $C_Z$ as $(x_0, td) \leftarrow \Pi_{ped}.Ext_1(1^\lambda)$ and we program the random oracle $H_{pp}$ so that it returns $x_0$ as $pp_Z$. Apart from this, Game 4 behaves identically to Game 3. As the parameters $pp_Z$ are chosen uniformly at random by $Ext_1$, this game is identically distributed to the previous one and we get $\text{Adv}_{A,Game4}(\lambda) = \text{Adv}_{A,Game3}(\lambda)$.

**Game 5:** In this game, we introduce another abort condition, namely the game aborts if there exists a signing session where no witness can be extracted from $\pi_{ped}$. The game now extracts the values $\bar{m}, r$ for every signing session. This game hop can be bounded by the Partial Online-Extractability of $\Pi_{ped}$. We formalize this in the following claim:

**Lemma 11.** There exists a PPT adversary $B_1$ against the online-extractability of $\Pi_{ped}$ such that $\text{Adv}_{A,Game\ 5}(\lambda) \ge \frac{\text{Adv}_{A,Game\ 4}(\lambda)-\text{negl}(\lambda)}{p_P(\lambda,Q_H)}$ where we plugged in $\text{Adv}_{A,Game4}(\lambda)$ as $\mu(\lambda)$ from Definition 25 and negl, $p_P$ are as in Definition 25.

*Proof.* We provide an adversary $B_1$ against the online-extractability of $\Pi_{ped}$ to bound the distance between the two games. The adversary receives the simulated CRS $\bar{crs}$ for $\Pi_{ped}$. It then simulates Game 4 to the adversary $A$ by sampling all the other parts of $vk$ as in Game 4 and answering the signing queries using the secret key. It outputs the proofs of $\Pi_{ped}$ that the adversary sent when opening a new signing session. The online-extractability of $\Pi_{ped}$ yields the claim.

**Remark 7.** We note that as the commitment scheme $C_Z$ is perfectly binding, and the above online extraction property guarantees the existence of a full witness, there cannot be two sessions using the same commitment $c_Z$ with different messages $\bar{m}, \bar{m}'$ and different $r, r'$. Thus, it follows that if $\bar{m} \neq \bar{m}'$, also $c_Z \neq c'_Z$ and $H_P(c_Z) \neq H_P(c'_Z)$ due to the abort condition introduced in Game 3.

**Game 6:** This game aborts if among the message-signature pair in the adversary's output there is a message for which the adversary has never queried $H(m)$.

**Lemma 12.** $|\text{Adv}_{A,Game5} - \text{Adv}_{A,Game6}(\lambda)| \le \frac{1}{2^{2\lambda}}$.

*Proof.* This boils down to the adversary having to guess the hash value $\bar{m} = H(m)$. As $H$ is a random oracle mapping into $\{0, 1\}^{2\lambda}$, the probability of guessing a uniformly random value from this space is $2^{2\lambda}$.

**Game 7:** In this game, the game samples all random choices that the signer and the random oracle make at the beginning of the game. As this change is purely conceptual, it holds that

$$ \text{Adv}_{A,Game7}(\lambda) = \text{Adv}_{A,Game6}(\lambda) $$

**Game 8:** In this game, we change how the CRS for $\Pi_{fis}$ is generated. Namely, we instead of generating $crs_{fis}$ using GenCRS, we switch to generating $crs_{fis}$ using SimCRS. This game hop can be bounded by the CRS indistinguishability property of $\Pi_{fis}$.

**Lemma 13.** There exists a reduction $B_2$ such that $|\text{Adv}_{A,Game8} - \text{Adv}_{A,Game7}| \le \text{Adv}_{B_2}^{crs}(\lambda)$

*Proof.* The reduction $A_2$ receives a CRS from the CRS indistinguishability challenger.

It samples all other parts of the verification key as in Game 7 and outputs them to the adversary. It answers signing queries as in Game 7. If the adversary wins the game it outputs that the CRS was honest, otherwise that it was simulated. It is easy to see that the claim follows.

**Game 9:** In Game 9 we change how the values $a_j$ are sampled during signature generation. In particular, the game samples bits $b, b' \leftarrow \{0, 1\}$ and $j \leftarrow \{1, \dots, Q_{H_P}\}$.

If $b = 1, b' = 0$, instead of sampling $a_j \leftarrow \{0, 1\}^{2\lambda}$, it first samples $\beta \leftarrow \{0, 1\}^{3\lambda}$ and then sets $a_j = \beta$. If $b = 1$ and $b' = 1$, it samples $\beta \leftarrow \{0, 1\}^{3\lambda}$ and sets $a_j = \beta - H(m_j)$. A simple argument shows that the distribution of $a_j$ in Game 9 has statistical distance at most $1/2^\lambda$ from the distribution of $a$ in Game 8.

$$ \text{Thus, we get that } ||\text{Pr}[\text{Game 9} = 1] - \text{Pr}[\text{Game 8} = 1]|| \le \frac{1}{2^\lambda}. $$
**Game 10:** In Game 10, we change how we set up the key vk. Namely, instead of using $S_{fis}$.KeyGen, we use the alternate algorithm $S_{fis}$.KeyGen$_{b,b'}$ using $N$ generated as before and $z \leftarrow \mathbb{Z}_N$ and it programs the random oracle $H_P$ to return primes from $e_1, \dots, e_{Q_{H_P}}$. Everything else we do as in Game 9. As the keys are distributed the same, it holds that

$$ \mathrm{Adv}_{A, \mathrm{Game}10}(\lambda) = \mathrm{Adv}_{A, \mathrm{Game}9}(\lambda). $$

**Game 11:** In Game 11, we change how signatures are created. In particular, the game uses the alternate signing algorithms $S_{fis}$.Sign$_{b,b'}$ as follows. As we introduced extraction of $\bar{m}, r$ in Game 5, the game has access to these two values. It therefore applies $S_{fis}$.Sign$_{b,b'}(\mathrm{sk}_{b,b'}, \bar{m})$ to obtain a signature $\sigma = (e, a, y)$. It then outputs $y', a$ to the adversary.

As the signatures produced by this game are identically distributed to the ones output by Game 10, we obtain that

$$ \mathrm{Adv}_{A, \mathrm{Game}11}(\lambda) = \mathrm{Adv}_{A, \mathrm{Game}10}(\lambda). $$

**Game 12:** In Game 12 we switch the setup of the CRS for $\Pi_{fis}$ to generating it using the simulator SimCRS for extraction.

**Lemma 14.**

$$ |\mathrm{Adv}_{A, \mathrm{Game}12}(\lambda) - \mathrm{Adv}_{A, \mathrm{Game}11}(\lambda)| = \mathrm{negl}(\lambda). $$

*Proof.* We construct an adversary $\mathcal{B}_3$ against CRS indistinguishability (see Definition 24). The adversary takes as input a CRS for $\Pi_{fis}$. It sets up the rest of the verification key vk as Game 12 and simulates all oracles except for $H_{fis}$ as Game 12. It simulates $H_{fis}$ by forwarding the queries of the adversary to its own hash oracle provided by the CRS indistinguishability challenger. It aborts whenever Game 12 would abort. If the adversary outputs a valid one-more forgery, the reduction $\mathcal{B}_3$ outputs 1, otherwise 0. The claim follows from the CRS indistinguishability according to Definition 24 of $\Pi_{fis}$.

*Moving Towards Breaking sRSA:* We now want to use the knowledge soundness property of the NIZK $\Pi_{fis}$ to obtain a signature that will be used by the final reduction to break sRSA.

Namely, after the adversary has submitted its signatures, we extract a witness from $\pi_{fis}$.

We describe below how this extraction procedure works.

We describe a “wrapper” $\mathcal{B}_4$ around $\mathcal{A}$ to extract from. This is necessary for formal reasons as the adversary $\mathcal{A}$ requires additional inputs and oracles compared to a knowledge soundness adversary, in particular $\mathcal{A}$ expects a verification key, several random oracles, as well as a signing oracle. The wrapper $\mathcal{B}_4$ will be our soundness adversary to extract from and it will provide all additional inputs and oracles to $\mathcal{A}$.

**Setup** The algorithm $\mathcal{B}_4$ takes as input a (simulated) CRS and has access to the random oracle $H_{fis}$. It generates all other parts of the verification key as Game 12, that is, it chooses the bits $b, b'$ and runs the corresponding alternative key generation algorithm, however it replaces the CRS for $\Pi_{fis}$ with the one from its input. Note that the CRS of $\Pi_{fis}$ is generated completely independently of the rest of the verification key in the honest setup of KeyGen, as well as in the alternative setup algorithms that use a different secret key to sign, and hence this new verification key vk using the input CRS is identically distributed to a verification key set up by Game 12.

**Online Phase.** The wrapper simulates the following oracles to the adversary. It aborts whenever Game 12 would abort.

**Signing** The wrapper answers signing queries as Game 12 using the online-extraction and the alternative signing algorithms corresponding to the bits $b, b'$.

**Hash oracle $H_{fis}$** It simulates $H_{fis}$ by forwarding queries and responses to and from its own oracle $H_{fis}$ provided by the extractor.

**Other Random Oracles** The other random oracles it provides itself and implements them in the same way as Game 12.
**Output determination** Due to the changes made in Game 6, for each message that the adversary $\mathcal{A}$ outputs a signature for, it has to have made a hash query. Further, as we introduced online-extraction of all witnesses of $\pi_{\text{ped}}$ submitted during signing queries, the wrapper can identify the hashes $\bar{m}$ that it has signed and which messages they belong to. As Game 2 aborts if there are collisions in $\mathcal{H}$, there are no collisions in $\mathcal{H}$ in Game 12, and therefore, the wrapper can efficiently identify which of the messages submitted as part of the final message-signature pairs it has not signed. Once the adversary outputs its message-signature pairs, the wrapper identifies the first message-signature pair $(m^*, (c_I^*, \pi_{\text{fis}}^*))$ where it has never signed the message $m^*$ itself. It outputs $(c_I^*, \pi_{\text{fis}}^*)$

**Lemma 15.** $\mathcal{B}_4$ is a valid adversary against adaptive knowledge soundness of $\Pi_{\text{fis}}$ and it holds that

$$ \Pr[(\overline{crs}, td) \leftarrow \text{SimCRS}(1^{\lambda}), (x, \pi) \leftarrow \mathcal{B}_4^{\text{H}_{\text{fis}}}(\overline{crs}; \rho) : \text{Verify}^{\text{H}_{\text{fis}}}(\overline{crs}, x, \pi) = 1] \geq \varepsilon_{\mathcal{B}_4}, \\ \text{where } \varepsilon_{\mathcal{B}_4} = \text{Adv}_{\mathcal{A}, \text{Game12}}(\lambda) $$

*Proof.* As the wrapper perfectly simulates Game 12 to the adversary $\mathcal{A}$, with probability $\text{Adv}_{\mathcal{A}, \text{Game12}}(\lambda)$, the adversary outputs a one-more forgery. Therefore, with the same probability, the wrapper outputs a pair $(c_I^*, \pi_{\text{fis}}^*)$ which is a statement-witness pair with a valid proof $\pi_{\text{fis}}^*$. The claim follows.

The extractor $\Pi_{\text{fis}}$.Ext is now run on the wrapper $\mathcal{B}_4$ wrapping $\mathcal{A}$.

**Lemma 16.** It holds that

$$ \Pr \left[ \begin{array}{l} \left( (\overline{crs}, td) \leftarrow \text{SimCRS}(1^{\lambda}), (c_I^*, \pi_{\text{fis}}^*) \leftarrow \mathcal{B}_4^{\text{H}_{\text{fis}}}(\overline{crs}; \rho), w \leftarrow \text{Ext}(\overline{crs}, td, c_I^*, \pi_{\text{fis}}^* \rho, \vec{h}) \right) : (c_I^*, w) \in \tilde{\mathbb{R}}_{\text{fis}} \right] \geq \frac{\varepsilon_{\mathcal{B}_4}^c - \text{negl}(\lambda)}{p_{\text{P}}(\lambda, Q_{\text{H}_{\text{fis}}})} \right] $$

*Proof.* This follows immediately from lemma 15 along with the adaptive knowledge soundness (see Definition 24) of $\Pi_{\text{fis}}$.

We now discuss how the witness is affected by the wrapper:

Information-theoretically, $c_I^*$ contains a unique opening. We define the distribution

$$ D_{\text{Game12}} := \{w | c_I^* \text{ is a commitment to } w\} $$

where $(m', c_I', \pi_{\text{fis}}')$ is the first tuple in the output of $\mathcal{A}$ Game 12 such that Game 12 has not signed $m'$ in a signing session.

Furthermore, we define the distribution

$$ D_{\text{ext}} := \left\{ w \middle| \begin{array}{l} (\overline{crs}, td) \leftarrow \text{SimCRS}(1^{\lambda}), \\ (c_I^*, \pi_{\text{fis}}^*) \leftarrow \mathcal{B}_4^{\text{H}_{\text{fis}}}(\overline{crs}; \rho), \\ w \leftarrow \text{Ext}(\overline{crs}, td, c_I^*, \pi_{\text{fis}}^* \rho, \vec{h}) \end{array} \right\} $$

**Lemma 17.** $D_{\text{Game12}} = D_{\text{ext}}$

*Proof.* The witness extracted by $\Pi_{\text{fis}}$.Ext is information-theoretically fixed already after one run of the wrapper and adversary because $c_I$ is perfectly binding. As the wrapper simulates Game 12 perfectly to the adversary, the witness contained in the commitment $c_I^*$ is therefore the unique witness the adversary would have committed to in Game 12. As there exist no other openings for the commitment, i.e., no other witnesses, this is the unique witness that the extractor can extract from $\mathcal{B}_4$ wrapping around $\mathcal{A}$.

**Remark 8.** We note that a similar argument would not go through if $c_I$ was only a computationally binding commitment. In this case, there would be no unique witness that the extractor is guaranteed to extract – any witness would mean success of the extractor, and thus the witness extracted might turn out to be dependent on the behavior of the wrapper in the same way as the witness extracted in [6, 62] can depend on the behavior of the wrapper there.
Reduction simulating Game 12 We describe a reduction $\mathcal{B}_5$ that simulates Game 12 and solves the strong RSA problem.

**Setup.** The reduction receives a strong RSA challenge $N, z$ from its challenger. The reduction samples $b, b' \leftarrow \{0, 1\}$ and then runs $S_{\text{fis}}.\text{KeyGen}_{b,b'}(1^{\lambda}, N, z)$ to generate the verification key parts of $S_{\text{fis}}$. It sets up the NIZK and commitment parameters as in Game 12.

**Online Phase.** The reduction interacts with the adversary as follows:

Simulation of $H$ This is done via lazy sampling from $\{0, 1\}^{2\lambda}$

Simulation of $H_P$ on the $i$-th fresh query to $H_P$, return $e_i$ from $\text{sk}_{b,b'}$.

Simulation of other hash oracles Lazy Sampling apart from whatever is defined through the setup of the NIZKs

Answering Signing Queries The reduction extracts the values $(\overline{m}, r)$ from the proof $\pi_{\text{ped}}$ using $\Pi_{\text{ped}}$. Ext. It then derives $e$ using $H_P$. By the programming of $H_P$, it identifies the index $k$ such that $e = e_k \in \{e_1, \dots, e_{Q_{H_P}}\}$. It then uses $S_{\text{fis}}.\text{Sign}_{b,b'}(\text{sk}_{b,b'}, k, \overline{m})$ to generate the signature $\sigma = (e, a, y)$. It then re-blinds the signature as $z = y \cdot g^r$ and outputs $z, a$.

Output Determination When the adversary $\mathcal{A}$ outputs its message-signature pairs, the reduction identifies the first message $m^*$ that it has not signed before. It then uses the extractor $\Pi_{\text{fis}}.\text{Ext}$ to obtain a signature $\sigma^* = (e^*, a^*, y^*)$ The reduction then solves for $z = e^* \cdot g^r$ using the same techniques as in Section 4.

It is easy to see that $\mathcal{B}_5$ simulates Game 12 perfectly.

We compute the probability that the reduction can use the solution output by the adversary to solve its sRSA challenge:

**Lemma 18.** *The probability that none of the following properties hold for the combined run of the reduction, extractor, wrapper, and adversary is at least $\frac{1}{4Q_{H_P}} \cdot \frac{\varepsilon_{\mathcal{B}_5}^c - \text{negl}(\lambda)}{p_P(\lambda, Q_{H_{\text{fis}}})}$:*

- extraction fails

- $b = 0$ and $e^* \in \{e_1, \dots, e_{Q_{H_P}}\}$

- $b = 1$ and $e^* \notin \{e_1, \dots, e_{Q_{H_P}}\}$

- $b = 1$ and $e^* \neq e_j$ where $j$ is the index $j$ from $\text{sk}_{b,b'}$.

- $b = 1$, the previous condition doesn't apply, $j$ as above. Denote by $a_j$ and $\overline{m}_j$ the values used in the first signing session where $e_j$ was used as an exponent. If no such session exists, sample $a_j \leftarrow S_a$.

• $b' = 0$ and $a^* = a_j$

• $b' = 1$ and $a^* + \overline{m}^* = a_j + \overline{m}_j$

*Proof.* We calculate the probability of the opposite event.

By lemma 16, extraction works with probability at least $\frac{\varepsilon_{\mathcal{B}_5}^c - \text{negl}(\lambda)}{p_P(\lambda, Q_{H_{\text{fis}}})}$.

The witness committed to in Game 12 is independent of the choices of $b, b', j$. This follows as in Theorem 6.

Therefore, by lemma 17, the witness extracted is also independent. Thus the probability of $b = 1$ and $e^* \in \{e_1, \dots, e_{Q_{H_P}}\}$ is at least $\frac{1}{2}$. The probability of $e^* = e_j$ and $b = 0$ is at least $\frac{1}{2Q_{H_P}}$, multiplied by the probability $\frac{1}{2}$ that either $b' = 1$ and $a^* = a_j$ or $b' = 0$ and $a^* + \overline{m}^* = a_j + \overline{m}_j$.

We briefly describe why solving sRSA works as in Section 4. First of all, $\Pi_{\text{fis}}$ guarantees that $a \in S_a$ and $e \in S_e$. Thus $a < e$ and in the case of $b = 1$, we know $e^*$ is prime and thus co-prime to $a_j - a^*$. In the case of $b = 0$ we cannot guarantee primality of $e^*$ as it is chosen by the adversary, however, $\Pi_{\text{fis}}$ still guarantees that $e^*$ is odd and thus the same strategy as in Section 4 can be applied.

## E Instantiations of NIZKs

In this section, we instantiate the remaining NIZKs required for $BS_{\text{fis}}: \Pi_{\text{ped}}$ and $\Pi_{\text{fis}}$. Let us give first a brief overview of the constructions. Both constructions follow roughly the Fiat-Shamir template: (1) Construct a $\Sigma$-protocol for the desired relation and (2) apply the Fiat-Shamir transformation to obtain a NIZK.
As before, we use the following notational conventions. In $\Sigma$-protocols, we denote by $\Omega$ the ZK commitments sent in the first flow. To improve readability, specific $\Omega$ are indexed by the relation to be shown. We denote by $\gamma$ the challenge. The responses (generally consisting of a linear combination of $\gamma$, a witness $w$ and a mask denoted by $\mu_w$) are denoted by $\tau_w$.

*Design principles of our $\Sigma$-protocols.* Throughout, we will utilize two groups types of groups: $Z_N^*$ and prime-order $G$. The latter is used for commitments (cf. Section 5). The technical difficulty of both instantiations is due to the need to argue over both groups (of distinct order) *consistently*. Also, we cannot reduce to computational assumptions with respect to $N$ because it is part of the statement. Roughly, our approach is as follows:

- For relations over either $Z_N^*$ or $G$ alone, we employ Schnorr-style $\Sigma$-protocol techniques. If a witness $w$ appears within relations over both $Z_N^*$ and $G$, the verifier checks both equations using the same response $\tau_w$ for both relations. Later, this ensures that the extracted witness satisfies the relations in both groups consistently. Because the order of $Z_N^*$ and $G$ is different $^{29}$, for instance, we cannot reuse a response in $Z_p$ within an equation over $Z_N^*$—this would lead to inconsistencies and already correctness fails. Instead, to compute the $\Sigma$-protocol responses, the prover masks the witness over the integers with either rejection sampling or noise flooding. Roughly, this ensures correctness when reusing the same response over both $Z_N^*$ and $G$.

- For relations between witnesses over the integers, we use a technique often used in Lattice-based NIZKs (e.g., [15]). Roughly, we embed the desired relation in the leading coefficient $f_d$ of a polynomial $f$ of degree $d$, where $\gamma$ is interpreted as variable. Here, $f$ is defined over the integers to avoid a dependence on the order of the groups. We design $f$ such that the desired relation holds iff $f_d = 0$ over the integers. Then, the prover proves that $f_d = 0$ over the integers by employing MPed commitments over $QR_{\tilde{N}}$, where $\tilde{N}$ is a fresh RSA modulus $^{30}$. For this, the prover commits to each coefficient except the leading coefficient $f_d$ via MPed. The evaluation $f_d(\gamma)$ is computable by the verifier by design, and the verifier checks that the prover committed to $f_d(\gamma)$ by linearity of MPed. A Schwarz-Zippel argument then allows to argue that $f_d = 0$ over the integers $^{31}$ Note that MPed over $QR_{\tilde{N}}$ is binding over the integers, so $f_d = 0 \in Z$ independent of the order of the group(s).

- To show (relaxed) ranges within the $\Sigma$-protocol, we employ the techniques in Section 5 and Appendix C.1. That is, we commit to the witness via a relaxed integer commitment and open it in zero-knowledge by verifying range memberships of the response.

- To argue special soundness, we need to ensure that we can extract witnesses in $Z$. Then, all relations are well-defined since exponentiation in $Z_N^*$ and $G$ is well-defined for integer exponents. For this, we proceed as in Appendix C.1. That is, the prover commits to all witnesses over $Z$ in an MPed commitment over $QR_{\tilde{N}}$. Due to lemma 6, we can argue that extracted values must be integers. Then, to argue that specific relations hold, we follow standard proof techniques. Formally, we show that the extractor finds a witness for the desired relations, or it finds a witness for a hard relation (e.g., for a relaxed DLOG relation over $QR_{\tilde{N}}$). Later, we argue that the latter does not occur under computational assumptions within the NIZKs.

- Another technicality is that for non-abort HVZK, we need that the witnesses lie within a specified range for masking to hide the witness statistically. Since some range checks are introduced in a modular manner later, the soundness extractor does not guarantee this at this

<footnote>$^{29}$ Furthermore, the order of $Z_N^*$ is unknown to both verifier and prover within this section.</footnote>

<footnote>$^{30}$ We stress that we cannot reuse the modulus $N$ for the MPed commitment because soundness relies on binding of MPed (which holds under sRSA). As $N$ is part of the statement, we cannot reduce to computational assumptions related to $N$ within our proof. On the other hand, we later embed $\tilde{N}$ into the NIZK's crs, more precisely srs. In that case, we can reduce extraction failure to assumptions over $\tilde{N}$. Let us also remark that for subversion zero-knowledge, we also cannot use assumptions related to $\tilde{N}$ either since $\tilde{N}$ is non-uniform.</footnote>

<footnote>$^{31}$ Roughly, the check ensures that $f_d(x)$ and polynomial $f'(x) := \sum_{i \in [0,d-1]} f_i x^i$ committed to in MPed evaluate to the same values for $x = \gamma$. If $f_d(\gamma) - f'(\gamma) = 0$ for $d+1$ different values $\gamma$, then it must hold that $f_d(x) = f'(x)$. Since the degree of $f'$ is $d-1$, this means that $f_d = 0$. We provide more details when introducing our specific $\Sigma$-protocols below.</footnote>
point <fnref n="32" />. These technicalities are why there are more than one relation per Σ-protocol: one for correctness and HVZK, and one for special soundness.

NIZKs. To construct both NIZKs, we construct appropriate Σ-protocols. Let us now give more intuition on how they are employed within our NIZKs.

- $\Pi_{\text{ped}}$: The first NIZK $\Pi_{\text{ped}}$ is an online-extractable NIZK. We achieve online-extraction as follows. We commit to each witness in an ElGamal commitment. A trapdoor for extraction is a decryption key for ElGamal. Because we encrypt in the exponent, we need the messages to be small (i.e., within $[0, B]$ for $B = \text{poly}$—this also ensures that they are well-defined as integers). The latter is proven via Bulletproofs [22]. An appropriate Σ-protocol compiled with Fiat-Shamir proves that the desired relation holds for the witnesses that are encrypted via ElGamal. (Because the witnesses are in general larger than $B$, we decompose them in $B$-ary representation first.) The extractor simply decrypts the ElGamal commitments. Due to the Bulletproof, decryption is guaranteed to work and due the Σ-protocol, the decrypted values satisfy the desired relation. To show that online extraction succeeds with high probability, we rely on the techniques in [66].

- $\Pi_{\text{fis}}$: This NIZK is obtained by applying the Fiat-Shamir transformation to an appropriate Σ-protocol.

More details are given below.

## E.1 Instantiation of $\Pi_{\text{ped}}$

We instantiate the online-extractable NIZK $R_{\text{ped}}$. We follow the well-known blueprint of combining an extractable commitment (e.g., ElGamal) with an adaptively knowledge sound NIZK for the relation to obtain online-extraction (see, e.g., [66]). Roughly, we decompose the witnesses into short values committed in ElGamal commitments and show that the relation holds with respect to these values. A range proof (i.e., a variant of Bulletproofs [22, 9]) guarantees that the committed values are short to enable online-extraction via a discrete logarithm computation. (The trapdoor is the ElGamal decryption key.) These ElGamal commitments function as the integer commitment $C_Z$. The commitment and its public parameters pp are part of the statement, but since these are sampled uniform, we can embed a trapdoor into pp (cf. Definition 25).

**Integer Commitment.** Recall that we want to show that $c \equiv h_2^{\overline{m}} \cdot g^{re} \bmod N$, where $\overline{m} \in [0, 2^{\lambda}-1]$ and $r \in [0, S]$ are committed in some integer commitment $(c_Z, d_Z) \leftarrow C_Z \cdot \text{Commit}(pp, (\overline{m}, r))$ with bounded range. Let $B = \text{poly}(\lambda)$ be a power of two. Let $\overline{G}_p$ be a group with prime order $p \ge 2^{2^{\lambda}}$. To instantiate $C_Z$, we essentially decompose $\overline{m}, r$ into values $(m_i)_i, (r_i)_i \in [0, B-1]$ via a $B$-ary decomposition, respectively, and commit to the values via ElGamal commitments over $\overline{G}_p$. Let $\ell_m = \lfloor \frac{\lambda}{\log B} - 1 \rfloor$ and $\ell_r = \lfloor \log_B(S) - 1 \rfloor$. The scheme $C_Z$ is defined below.

- $C_Z \cdot \text{Setup}(1^{\lambda})$: Samples $\overline{G}, \overline{H} \leftarrow \overline{G}_p$ and outputs pp $\leftarrow \overline{G}, \overline{H}$.

- $C_Z \cdot \text{Commit}(pp, (\overline{m}, r))$: Takes as input public parameters pp and message $(\overline{m}, r)$, where $\overline{m} \in [0, 2^{\lambda}-1]$ and $r \in [0, S]$. Decomposes $\overline{m} = \sum_{i=1}^{\ell_m} m_i B^{i-1}$ and $r = \sum_{i=1}^{\ell_r} r_i B^{i-1}$. Let $\overline{e} = (m_1, \dots, m_{\ell_m}, r_1, \dots, r_{\ell_r}) \in [0, B-1]^{\ell_m+\ell_r}$. Samples $s_i \leftarrow \mathbb{Z}_p$ and sets $E_i = e_i \overline{G} + s_i \overline{H}, S_i = s_i \overline{G}$. Outputs $c_Z = (E_i, S_i)_{i=1}^{\ell_m+\ell_r}$ and $d_Z = (s_1, \dots, s_{\ell_m+\ell_r})$.

- $C_Z \cdot \text{Verify}(pp, c_Z, (\overline{m}, r), d_Z)$: Parses $c_Z$ and $d_Z$ as above. Decomposes $\overline{m}$ and $r$ into $m_i$ and $r_i$, respectively, and defines $\overline{e}$ as above. Checks that $E_i = e_i \overline{G} + s_i \overline{H}, S_i = s_i \overline{G}$ and $e_i \in [0, B]$ for all $i \in [\ell_m + \ell_r]$.

**Lemma 19.** The integer commitment scheme with bounded range $C_Z$ with message space $C_Z \cdot C_{\text{msg}} = [0, 2^{\lambda}-1] \times [0, S]$ is correct, hiding under DDH in $\overline{G}_p$ and perfectly binding (cf. Definition 6).

<footnote n="32">³² Also, sometimes the ranges required for HVZK and ranges guaranteed by soundness are different due to optimizations akin to Section 5.</footnote>
**Proof.** For correctness, given $c_Z, d_Z$ from $C_Z \cdot \text{Commit}(\text{pp}, (\bar{m}, r))$ and the opening $(\bar{m}, r)$, we parse $c_Z = (E_i, S_i)_{i=1}^{\ell_m+\ell_r}$ and $d_Z = (s_i)_{i=1}^{\ell_m+\ell_r}$. The values $s_i$ are the same that are used in $C_Z \cdot \text{Commit}$. Since $B = \text{poly}(\lambda)$ is a power of two, or more generally since the super-increasing $(1, B, B^2, \dots)$ satisfies $B^i > \sum_{j=0}^{i-1} B^j$, the $B$-ary decomposition of $\bar{m}$ and $r$ is unique. Hence, in $C_Z \cdot \text{Verify}(\text{pp}, c_Z, (\bar{m}, r), d_Z)$, decomposing $\bar{m} = \sum_{i=1}^{\ell_m} m_i B^{i-1}$ and $r = \sum_{i=1}^{\ell_r} r_i B^{i-1}$ gives the same vector $\bar{e} = (m_1, \dots, m_{\ell_m}, r_1, \dots, r_{\ell_r}) \in [0, B-1]^{\ell_m+\ell_r}$ that is used in $C_Z \cdot \text{Commit}$, satisfying the range checks of $e_i$ for all $i \in [\ell_m + \ell_r]$. Finally, the fact that $\bar{G}, \bar{H} \leftarrow \bar{G}_p$ being cyclic ensures that the equality $E_i = e_i \bar{G} + s_i \bar{H}$ holds, by using the same $(e_i, s_i)$ that are used in $C_Z \cdot \text{Commit}(\text{pp}, (\bar{m}, r))$ to set $E_i$.

For hiding, observe that a commitment $c_Z$ is comprised of $\ell_m + \ell_r = \text{poly}(\lambda)$ ElGamal commitments $(E_i, S_i)$. Let us argue with a hybrid argument. Let $\mathcal{A}$ be an adversary on hiding. In the $i$-th hybrid, replace $(E_i, S_i)$ with $(E'_i, S'_i) \leftarrow \bar{G}_p$. Since $(\bar{H}, S_i, s_i \bar{H})$ form a DDH-tuple, it is straightforward to construct an adversary on DDH that distinguishes two consecutive hybrids with advantage $\varepsilon = \text{Adv}_\mathcal{A}^{\text{hide}}(\lambda)$. Since $(\ell_m + \ell_r)\varepsilon = \text{negl}(\lambda)$ under DDH, the claim follows.

Let us show binding. Let $c_Z = (E_i, S_i)_{i \in [\ell_m + \ell_r]} \in \mathbb{G}^{(2 \cdot \ell_m + \ell_r)}$. Observe that $(E_i, S_i)$ fixes $e_i \mod p$ perfectly $^{33}$. If $\exists i : e_i \notin [0, B]$, then the commitment cannot be opened because the interval membership check in verification fails. Else, since $\text{poly}(\lambda) = B < 2^\lambda \le p$, any valid opening of $(E_i, G_i)$ fixes unique $e_i$ over the integers as described above. These values determine the message $(\bar{m}, r)$ uniquely within $[0, 2^\lambda - 1] \times [0, S]$ through $B$-ary decomposition. In conclusion, $c_Z$ can only be opened to $(\bar{m}, r)$ fixed as described above.

**Online-Extractable NIZK.** We are now ready to instantiate $\Pi_{\text{ped}}$. Let $B = \text{poly}(\lambda)$ and $\ell_m := \lfloor \frac{\lambda}{\log B} - 1 \rfloor$, $\ell_r := \lfloor \log_B(S) - 1 \rfloor$. For the above $C_Z$, we can rewrite the relation $R_{\text{ped}}$ as follows.

$$R_{\text{ped}} = \{(x, w) \mid c = h_2^{\bar{m}} \cdot g^{r\epsilon} \bmod N, E_i = e_i \bar{G} + s_i \bar{H}, S_i = s_i \bar{G}, e_i \in [0, B-1], \\ \bar{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1}, r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}\},$$

for $x = (B, \bar{G}, \bar{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$ and $w = (\bar{m}, r, (s_i)_{i \in [\ell_m+\ell_r]})$. Above, $\bar{m} \in [0, 2^\lambda - 1]$, $r \in [0, S]$ and $s_i \in \mathbb{Z}_p$. Note and that the values $e_i$ are unique given $\bar{m}$ and $r$ via the $B$-ary decomposition. Moreover, by the choices of $(\ell_m, \ell_r)$ it holds that

$$0 \le \bar{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1} \le \sum_{i=1}^{\ell_m} (B-1) B^{i-1} \le \sum_{i=1}^{\ell_m} B^i < \sum_{i=0}^{\ell_m} B^i < B^{\ell_m+1} \stackrel{(*)}{\le} 2^\lambda$$

where $(*)$ follows from the fact that $\ell_m = \lfloor \frac{\lambda}{\log B} - 1 \rfloor$ and $\lfloor x \rfloor \le x$ for all $x \in \mathbb{R}$. A similar calculation on $r$ can be obtained

$$0 \le r < B^{\ell_r+1} \stackrel{(**)}{\le S}$$

and $(**)$ follows from the fact that $\ell_r = \lfloor \log_B(S) - 1 \rfloor$.

To instantiate $\Pi_{\text{ped}}$, we construct a standard $\Sigma$-protocol $\Sigma_{\text{ped}}$ to show that $R_{\text{ped}}$ holds, except for the statement $e_i \in [0, B-1]$. For the latter, we later use a range proof $\Pi_{\text{rp}}$ from [9]. Then, we compile $\Sigma_{\text{ped}}$ into an NIZK $\Pi_{\text{ped}}$ via Fiat-Shamir and combine both NIZKs $\Pi_{\text{ped}}$ and $\Pi_{\text{rp}}$ into an NIZK for the full relation $R_{\text{ped}}$ as in [66], Section 6. This approach was shown to be secure in [66].

There is one difficulty that arises during the construction of $\Sigma$-protocol: the relations for $\bar{m}$ and $r$ have to hold over the integers. For example, notice that it is not sufficient to show that $r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1} \bmod p$ over $\bar{G}_p$ since the commitment $C_Z$ is (perfectly) binding only if this relation holds over $\mathbb{Z}$. To ensure that soundness guarantees that the relations hold over $\mathbb{Z}$, we add an additional MPed commitment $\tilde{c}$ over $QR_N$ for a fresh RSA modulus $N$. If we commit to all witnesses (except $s_i$ since these are defined over $\mathbb{Z}_p$) in $\tilde{c}$ and open it in ZK, the extracted values are integers under sRSA (cf. lemma 6). We can also use MPed commitments to show the statements over the integers (leveraging the binding property of MPed). To ensure subversion zero-knowledge,

<footnote n="33">33 An inefficient algorithm can recompute a unique $e_i \in \mathbb{Z}_p$ that satisfies $E_i = e_i \bar{G} + s_i \bar{H}$, where $s_i$ is the DLOG of $S_i$.</footnote>
we add a $\Pi_{\text{gen}}$ proof (cf. Appendix C.1) which ensures that the public parameters of MPed are setup in a manner that ensures hiding.

Below, we provide the protocols $\Sigma_{\text{ped}}$ and $\Pi_{\text{rp}}$, and then combine them to construct $\Pi_{\text{ped}}$.

**Step 1: the $\Sigma$-protocol.** Let $C = 2^{\lambda}$ (which determines the challenge space). Let $\tilde{N} \in \mathbb{N}$ and let $\tilde{\text{pp}} = (\tilde{h}, \tilde{g}_1, \dots, \tilde{g}_{\ell_m+\ell_r}) \in (\mathbb{Z}_{\tilde{N}}^*)^{1+\ell_m+\ell_r}$ denote the public parameters of an MPed commitment with message space $\mathbb{Z}^{\ell_m+\ell_r}$. (Since membership in $QR_{\tilde{N}}$ cannot be efficiently tested without factorization of $\tilde{N}$, the MPed commitment is formally defined over $\mathbb{Z}_{\tilde{N}}^*$. Later, $\tilde{N}$ and $\tilde{\text{pp}}$ are given in the crs.) Denote by $R$ the relation

$$R = \{(x, w) : c \equiv h_2^{\overline{m}} \cdot g^{re} \mod N, E_i = e_i \overline{G} + s_i \overline{H}, S_i = s_i \overline{G} \\ \qquad \overline{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1}, r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}\},$$

where $x = (\tilde{N}, \tilde{\text{pp}}, B, \overline{G}, \overline{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$ and $w = ((e_i, s_i)_{i=1}^{\ell_m+\ell_r}, \overline{m}, r)$. Here, $\overline{m}, r, e_i \in \mathbb{Z}$ and $s_i \in \mathbb{Z}_p$. The protocol $\Sigma_{\text{ped}}$ for relation

$$R_{\Sigma_{\text{ped}}} = \{(x, w) : (x, w) \in \mathbb{R} \text{ and } e_i \in [0, B-1] \text{ and } \langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle\},$$

is given in Fig. 4. We include the statements $e_i \in [0, B-1]$ and $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$ in the relation $R_{\Sigma_{\text{ped}}}$ because this is required for correctness and HVZK$^{34}$. For the soundness relation, we omit $e_i \in [0, B-1]$ and $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$ (since these statements are shown via a separate NIZK within $\Pi_{\text{ped}}$ later—in particular these relations are not ensured to hold by $\Sigma$-protocol yet). We remark that to show the decompositions, we use a standard technique that is often used in lattices to show multiplicative relations (e.g., [15]). In particular, we show 2-special soundness for the relation

$$\tilde{R}_{\Sigma_{\text{ped}}} = \{(x, w) : (x, w) \in \mathbb{R} \text{ or } (\tilde{\text{pp}}, w) \in R_{C, \ell}(\tilde{\text{pp}}) \text{ or } (\tilde{\text{pp}}, w) \in R_{\text{dlog}}\},$$

where $R_{C, \ell}(\tilde{\text{pp}})$ is defined in Definition 7 and $R_{\text{dlog}}$ denotes the relation that contains all non-trivial DLOG relations in $\tilde{\text{pp}}$ (see [9] for more details). Note that under the factoring assumption, it is hard to find a witness for $R_{\text{dlog}}$ if the statement $\tilde{\text{pp}}$ are random generators of $QR_{\tilde{N}}$.

Our construction follows the design principles discussed at the start of this section. Let us give a brief overview. To show the statements over $\mathbb{Z}_{\tilde{N}}^*$ and $\overline{G}_p$, we use use Schnorr-type $\Sigma$-protocol techniques except that the witnesses are masked over the integers via noise flooding$^{35}$. This ensures that we can reuse the responses over groups of distinct order. For the relations related to the $B$-ary decomposition of $\overline{m}$ and $r$, we define two polynomials $f_m$ and $f_r$ of degree 1 where the leading coefficient is $f_{m,1} = \overline{m} - \sum_{i=1}^{\ell_m} e_i B^{i-1}$ and $f_{r,1} = r - \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}$, respectively. The polynomials are designed such that $f_m(\gamma)$ and $f_r(\gamma)$ can be recomputed given the $\Sigma$-protocol responses, where $\gamma$ is the challenge. Notably, if $f_m$ and $f_r$ are constant, then the desired relations hold. This can be efficiently verified if the prover commits to the constant terms $f_{m,0}$ of $f_{r,0}$ in a separate MPed commitment and the verifier checks that $f_{m,0}(\gamma) = f_m(\gamma)$ and $f_{r,0}(\gamma) = f_r(\gamma)$ using the commitment's linearity. Roughly, special soundness is argued as follows: If $f_{m,0}(\gamma) - f_m(\gamma) = 0$ for two distinct values $\gamma$, then because $f_{m,0} - f_m$ is of degree 1 but has two zeroes, it must hold that $f_{m,0} - f_m = 0$. But then, $f_{m,1} = 0$ because $f_{m,0}$ is constant. Thus, the relation holds as discussed above.

The above discussion is formalized below.

**Lemma 20.** The $\Sigma$-protocol $\Sigma_{\text{ped}}$ is correct, HVZK, has high min-entropy for relation $R_{\Sigma_{\text{ped}}}$, and is 2-special sound for relation $\tilde{R}_{\Sigma_{\text{ped}}}$.

<footnote>$^{34}$ As discussed in the beginning of this section, we commit to $e_i$ via an MPed commitment over $\tilde{N}$ to ensure that $e_i \in \mathbb{Z}$ and that the statements hold over the integers. Thus, we need that the public parameters $\tilde{\text{pp}}$ is setup such that MPed is hiding. This is guaranteed by $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$. Further, we know that in an honest execution, we have that $e_i \in [0, B-1]$. We add this condition in the correctness and HVZK relation in order to mask over the integers with small masks. (This is required to compute the $\Sigma$-protocol responses.)</footnote>

<footnote>$^{35}$ We could use rejection sampling and compile $\Sigma_{\text{ped}}$ with Fiat-Shamir with aborts for better efficiency. We choose noise flooding for simplicity.</footnote>
Proof. For correctness, the first check on line 16 follows arithmetics modulo $N$ where $c^{-\gamma} \equiv h_2^{-\gamma \overline{m}} \cdot g^{-\gamma re} \mod N$ together with

$$h_2^{\tau_{\overline{m}}} \cdot g^{\tau_{re}} \equiv h_2^{\gamma \overline{m} + \mu_{\overline{m}}} \cdot g^{\gamma re + \mu_{re}} \mod N$$

and $\Omega_c \leftarrow h_2^{\mu_{\overline{m}}} \cdot g^{\mu_{re}} \mod N$ implies $c^{-\gamma} h_2^{\tau_{\overline{m}}} \cdot g^{\tau_{re}} \equiv \Omega_c \mod N$. In a similar manner, the checks on lines 23 and 22 follow from modular arithmetics in $\mathbb{Z}_{\tilde{N}}$. More specifically, the check on line 22 passes because

$$\tilde{c}^{-\gamma} \cdot \tilde{h}^{\tau_{\tilde{t}}} \cdot \prod_{i=1}^{\ell_m+\ell_r} \tilde{g}_i^{\tau_{e_i}} \equiv \tilde{h}^{-\gamma \tilde{t}+\tau_{\tilde{t}}} \cdot \prod_{i=1}^{\ell_m+\ell_r} \tilde{g}_i^{-\gamma e_i+\tau_{e_i}} \stackrel{(*)}{\equiv} \tilde{h}^{\mu_{\tilde{t}}} \cdot \prod_{i=1}^{\ell_m+\ell_r} \tilde{g}_i^{\mu_{e_i}} \mod \tilde{N}$$

and is congruent to $\Omega_{\tilde{c}}$ modulo $\tilde{N}$ thanks to $\Omega_{\tilde{c}} \leftarrow \tilde{h}^{\mu_{\tilde{t}}} \cdot \prod_{i=1}^{\ell_m+\ell_r} \tilde{g}_i^{\mu_{e_i}} \mod \tilde{N}$, where (*) follows from $\tau_{\tilde{t}} \leftarrow \gamma \tilde{t} + \mu_{\tilde{t}}$ and $\tau_{e_i} \leftarrow \gamma e_i + \mu_{e_i}$. To examine the check on line 23, we observe the following in $\mathbb{Z}$

$$\begin{aligned} f_m &= (\sum_{i=1}^{\ell_m} \tau_{e_i} B^{i-1}) - \tau_{\overline{m}} \\ &= (\sum_{i=1}^{\ell_m} (\gamma e_i + \mu_{e_i}) B^{i-1}) - (\gamma \overline{m} + \mu_{\overline{m}}) \\ &= \gamma \underbrace{(\sum_{i=1}^{\ell_m} B^{i-1} e_i - \overline{m})}_{=0} + (\sum_{i=1}^{\ell_m} B^{i-1} \mu_{e_i}) - \mu_{\overline{m}} = f_{m,0} \end{aligned}$$

and in the same manner, also in $\mathbb{Z}$,

$$\begin{aligned} f_r &= (\sum_{i=1}^{\ell_r} B^{i-1} \tau_{e_{\ell_m+i}}) - \tau_r \\ &= (\sum_{i=1}^{\ell_r} (\gamma e_{\ell_m+i} + \mu_{e_{\ell_m+i}}) B^{i-1}) - (\gamma r + \mu_r) \\ &= \gamma \underbrace{(\sum_{i \in [\ell_r]} e_{\ell_m+i} B^{i-1} - r)}_{=0} + (\sum_{i=1}^{\ell_r} \mu_{e_{\ell_m+i}} B^{i-1}) - \mu_r = f_{r,0}. \end{aligned}$$

This gives

$$\tilde{h}^{t_q} \cdot \tilde{g}_1^{f_m} \cdot \tilde{g}_2^{f_r} \equiv \tilde{h}^{t_q} \cdot \tilde{g}_1^{f_{m,0}} \cdot \tilde{g}_2^{f_{r,0}} \equiv \Omega_q \mod \tilde{N}.$$

Finally, the checks on lines 18 and 19 are done in $\mathbb{G}_p$, even though $\gamma s_i \in \mathbb{Z}$ while $\mu_{s_i} \in \mathbb{Z}_p$, the computation is in $\mathbb{G}_p$ of order $p$ and thus $\tau_{s_i} \overline{H} = (\gamma s_i + \mu_{s_i}) \overline{H} \in \mathbb{G}_p$ is well-defined (which would not be the case if $\mu_{s_i}$ was a congruent class of a modulus other than $p$). The calculations can be verified with ease

$$\begin{aligned} -\gamma E_i + \tau_{e_i} \overline{G} + \tau_{s_i} \overline{H} &= -\gamma(e_i \overline{G} + s_i \overline{H}) + (\gamma e_i + \mu_{e_i}) \overline{G} + (\gamma s_i + \mu_{s_i}) \overline{H} = \mu_{e_i} \overline{G} + \mu_{s_i} \overline{H} = \Omega_{E_i} \in \mathbb{G}_p \\ \text{and } -\gamma S_i + \tau_{s_i} \overline{G} &= -\gamma s_i \overline{G} + (\gamma s_i + \mu_{s_i}) \overline{G} = \mu_{s_i} \overline{G} = \Omega_{S_i} \in \mathbb{G}_p. \end{aligned}$$

For showing high min-entropy, we consider the first flow

$$\Omega := (\tilde{c}, \Omega_{\tilde{c}}, \Omega_q, (\Omega_{E_i})_i, (\Omega_{S_i})_i, \Omega_c).$$

The cyclic group $\mathbb{G}_p$ has order $p \ge 2^\lambda$ and because $\mu_{s_i} \leftarrow \mathbb{Z}_p$ uniformly at random modulo $p$, the terms $\mu_{s_i} \overline{H}, \mu_{s_i} \overline{G}$ are uniformly distributed in $\mathbb{G}_p$ and implying $\Omega_{E_i}, \Omega_{S_i}$ are uniformly distributed in $\mathbb{G}_p$. The probability that an adversary correctly guesses $\Omega$ is thus at most $2^{-\lambda}$, concluding the high min-entropy property.

For HVZK, we observe that following the properties of noise flooding (see Supplementary materials A.2), the masking by

$$\mu_{\tilde{t}} \leftarrow [0, C \tilde{N} \cdot 2^{2\lambda}], \quad \mu_{\overline{m}} \leftarrow [0, C 2^{3\lambda}], \quad \mu_r \leftarrow [0, C S \cdot 2^{\lambda}] \\ \mu_{e_i} \leftarrow [0, C B \cdot 2^{\lambda}], \quad \mu_{s_i} \leftarrow \mathbb{Z}_p$$

ensures that the values

$$\begin{aligned} \tau_{\overline{m}} &\leftarrow \gamma \overline{m} + \mu_{\overline{m}}, & \tau_r &\leftarrow \gamma r + \mu_r, & \tau_{\tilde{t}} &\leftarrow \gamma \tilde{t} + \mu_{\tilde{t}} \\ \tau_{e_i} &\leftarrow \gamma e_i + \mu_{e_i}, & \tau_{s_i} &\leftarrow \gamma s_i + \mu_{s_i} \end{aligned}$$
sent in the third flow are statistically close to uniform over their respective ranges $[0, CB \cdot 2^\lambda]^{\ell_m} \times \mathbb{Z}_p^{\ell_r} \times [0, C \cdot 2^{3\lambda}] \times [0, CS \cdot 2^\lambda] \times [0, CN \cdot 2^{2\lambda}] \times [0, \tilde{N} \cdot 2^\lambda]$. Moreover, the commitment $\tilde{c}$ is distributed close to uniform over $\langle \tilde{h} \rangle$ (with statistical distance at most $2^{-\lambda}$) because $\tilde{t}$ is drawn uniform over $[0, \tilde{N} \cdot 2^\lambda]$, and because $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$. The remaining values $\Omega_{\tilde{c}}$, $\Omega_q$, $(\Omega_{E_i})_i$, $(\Omega_{S_i})_i$, $\Omega_c$ are determined from the third flow and the challenge $\gamma$, by setting with respect to the verification equations

$$
\begin{align*}
\Omega_c &= c^{-\gamma} h_2^{\tau_m} \cdot g^{\tau_r e} \mod N \\
\forall i \in [\ell_m + \ell_r] &: \Omega_{E_i} = -\gamma E_i + \tau_{e_i} \overline{G} + \tau_{s_i} \overline{H}; \quad \Omega_{S_i} = -\gamma S_i + \tau_{s_i} \overline{G} \\
\Omega_{\tilde{c}} &= \tilde{c}^{-\gamma} \cdot \tilde{h}^{\tau_i} \cdot \prod_{i=1}^{\ell_m + \ell_r} \tilde{g}_i^{\tau_{e_i}} \mod \tilde{N} \\
\Omega_q &= \tilde{h}^{t_q} \cdot \tilde{g}_1^{f_m} \cdot \tilde{g}_2^{f_r} \mod \tilde{N}.
\end{align*}
$$

Given the above discussion, the simulator receives the challenge $\gamma$ and samples the responses (for the third flow) according to the above distributions. It also samples $\tilde{c}$ (with negligible distance close to) uniform over $\langle \tilde{h} \rangle$. Finally, it recomputes the remaining first flow that is determined as above and outputs the full transcript. Since the distribution is statistically close to the real protocol, the simulator suffices.

Let us finally show 2 special soundness. We want to construct a deterministic PT extractor so that, for

$$x = (\tilde{N}, \tilde{p}\tilde{p}, B, \overline{G}, \overline{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r}),$$

given 2 valid transcripts that are indexed by $i \in [2]$ with

Identical first flow: $\Omega = (\tilde{c}, \Omega_{\tilde{c}}, \Omega_q, (\Omega_{E_i})_i, (\Omega_{S_i})_i, \Omega_c)$

Pairwise distinct challenge: $\gamma_i$

Third flow: $\tilde{\tau}_i = ((\tau_{e_{k,i}})_k, (\tau_{s_{k,i}})_k, \tau_{\overline{m}_i}, \tau_{r_i}, \tau_{\tilde{t}_i}, t_{q,i})$

the extractor extracts the witness $w = ((e_k, s_k)_{k=1}^{\ell_m+\ell_r}, \overline{m}, r)$ such that $(x, w) \in \tilde{\mathbb{R}}_{\Sigma_{\text{ped}}}$. In the following, we denote by $\Delta v_{i,j} := \tau_{v,i} - \tau_{v,j} \in \mathbb{Z}$ for $v \in \{(e_k, s_k)_{k=1}^{\ell_m+\ell_r}, \overline{m}, r\}$ and $\Delta \gamma_{i,j} := \gamma_i - \gamma_j \neq 0$.

By verification on line 22, we have that for $i \in [2]$, it holds that

$$\tilde{c}^{-\gamma_i} \cdot \tilde{h}^{\tau_{\tilde{t}_i}} \cdot \prod_{k=1}^{\ell_m+\ell_r} \tilde{g}_k^{\tau_{e_{k,i}}} \equiv \Omega_{\tilde{c}} \mod \tilde{N}$$

Thus, it holds for $i \neq j \in [2]$ that

$$\tilde{c}^{\Delta \gamma_{i,j}} \equiv \tilde{h}^{\Delta \tilde{t}_{i,j}} \cdot \prod_{k=1}^{\ell_m+\ell_r} \tilde{g}_k^{\Delta e_{k,i,j}} \mod \tilde{N}$$

Thus, either $\Delta \gamma_{i,j}$ divides $\Delta v_{i,j}$ for $v \in \{(e_i, s_i)_{i=1}^{\ell_m+\ell_r}, \overline{m}, r\}$ over $\mathbb{Z}$, or the above equation yields a witness $w$ for $(\tilde{p}\tilde{p}, w) \in \mathbb{R}_{C, \tilde{\ell}}(\tilde{p}\tilde{p})$. In the latter case, the extractor outputs the witness $w$.

Further, the verification checks ensure that

$$c^{-\gamma_1} h_2^{\tau_{\overline{m},1}} \cdot g^{\tau_{r,1}e} = c^{-\gamma_2} h_2^{\tau_{\overline{m},2}} \cdot g^{\tau_{r,2}e} \quad (11)$$

$$\forall k \in [\ell_m + \ell_r] : -\gamma_1 E_k + \tau_{e_k,1} \overline{G} + \tau_{s_k,1} \overline{H} = -\gamma_2 E_k + \tau_{e_k,2} \overline{G} + \tau_{s_k,2} \overline{H} \quad (12)$$

$$\forall k \in [\ell_m + \ell_r] : -\gamma_1 S_k + \tau_{s_k,1} \overline{G} = -\gamma_2 S_k + \tau_{s_k,2} \overline{G} \quad (13)$$

We set $e_k = \Delta e_{k,1}/\Delta \gamma_{1,2}$, $s_k = \Delta s_{k,1}/\Delta \gamma_{1,2} \mod p$, $\overline{m} = \Delta \overline{m}_{1,2}/\Delta \gamma_{1,2}$, and $r = \Delta r_{1,2}/\Delta r_{1,2}$. From (11), it holds that

$$c = h_2^{\Delta \overline{m}_{1,2}/\Delta \gamma_{1,2}} \cdot g^{(\Delta r_{1,2}/\Delta \gamma_{1,2}) \cdot e} \mod N$$

where we note that the division $\Delta \overline{m}_{1,2}/\Delta \gamma_{1,2}$ and $\Delta r_{1,2}/\Delta \gamma_{1,2}$ are well defined over integer values $\Delta \overline{m}_{1,2}$, $\Delta r_{1,2}$, $\Delta \gamma_{1,2} \in \mathbb{Z}$, with respect to the above argument regarding verification in line 22. Consequently, setting $\overline{m} = \Delta \overline{m}_{1,2}/\Delta \gamma_{1,2}$, and $r = \Delta r_{1,2}/\Delta r_{1,2}$ satisfies $c = h_2^{\overline{m}} \cdot g^{re} \mod N$. Next, for each $k \in [\ell_m + \ell_r]$, (12) and (13) imply that

$$E_k = \Delta e_{k,1}/\Delta \gamma_{1,2} \overline{G} + \Delta s_{k,1}/\Delta \gamma_{1,2} \overline{H} \quad \text{and} \quad S_k = \Delta s_{k,1}/\Delta \gamma_{1,2} \overline{G}$$
where the inverse $1/\Delta\gamma_{1,2}$ is well defined in $\mathbb{Z}$ following a similar argument regarding verification in line 22, else we find a witness for the relaxed DLOG relation. As a result, setting $e_k = \Delta e_{k1,2}/\Delta\gamma_{1,2}$ and $s_k = \Delta s_{k1,2}/\Delta\gamma_{1,2}$ satisfies $E_k = e_k \tilde{G} + s_k \tilde{H}$, $S_k = s_k \tilde{G}$ for all $k \in [\ell_m + \ell_r]$.

From line 23, we obtain two openings for $\Omega_q$. Thus, we know that $f_m = f'_m$ and $f_r = f'_r$, else we find a non-trivial DLOG relation in $\tilde{p}\tilde{p}$ as in [34], Section 5.1. By definition, we have

$$ 
\begin{align*}
f_m &= \left( \sum_{i=1}^{\ell_m} B^{i-1} \tau_{e_i} \right) - \tau_{\bar{m}} = \left( \sum_{i=1}^{\ell_m} B^{i-1} \tau_{e_i'} \right) - \tau_{\bar{m}'} = f_m' \\
&\implies \left( \sum_{i=1}^{\ell_m} B^{i-1} e_i \right) - \bar{m} = 0 \\
&\implies \sum_{i=1}^{\ell_m} B^{i-1} e_i = \bar{m}.
\end{align*}
$$

Similarly, we obtain $r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}$. This concludes the proof.

<figure><img src="image_3.png" /><figcaption>Fig. 4: Description of $\Sigma_{\text{ped}}$ for $x = (\tilde{N}, \tilde{p}\tilde{p}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$ and $w = ((e_i, s_i)_{i=1}^{\ell_m+\ell_r}, \bar{m}, r)$.</figcaption></figure>
**Step 2: the range proof.** Next, let $\Pi_{rp}$ be the NIZK with random oracle $H_{rp}$ from [66] (cf. Section 6.2). Note that $\Pi_{rp}$ is obtained by compiling Bulletproofs [22, 9] via Fiat-Shamir. The correctness and zero-knowledge relation is

$$R_{rp} = \{(x, w) : E_i = e_i \overline{G} + s_i \overline{H}, e_i \in [0, B-1] \text{ for } i \in [\ell_m + \ell_r]\},$$

with $x = (\overline{G}, \overline{H}, B, (E_i)_{i \in [\ell_m + \ell_r]})$ and $w = ((e_i, s_i)_{i \in [\ell_m + \ell_r]})$, where $B$ is a power of two$^{36}$. Note that $\text{srs} = \perp$ and $\text{urs}_{rp} = ((\tilde{g}_i)_{i \in [\ell_{rp}]}) \in \overline{\mathbb{G}}_{\ell_{rp}}^{\ell_{rp}}$ define the $\text{crs} = \text{urs}_{rp}$ of $\Pi_{rp}$, where $\ell_{rp} \in \mathbb{N}$ is chosen appropriately. The soundness relation is

$$\tilde{R}_{rp} := \{(x, w) : (x, w) \in R_{rp} \text{ or } ((\overline{G}, \overline{H}, \text{urs}_{rp}), w) \in R_{dlog}\},$$

where $R_{dlog} = \{(\overline{G}, \overline{H}, \text{urs}_{rp}), w\}$ denotes the relation that contains all non-trivial DLOG relations $w$ for $(\overline{G}, \overline{H}, \text{urs}_{rp})$ (see [9] for more details). Note that for uniform statement, it is hard to find a witness for $R_{dlog}$ under the DLOG assumption. We recall well-known properties of $\Pi_{rp}$ in lemma 21.

**Lemma 21 ([66], Theorem 17).** The NIZK $\Pi_{rp}$ for relation $R_{rp}$ is correct, zero-knowledge and adaptively knowledge sound for the relaxed relation $\tilde{R}_{rp} \supseteq R_{rp}$.

**Step 3: the online-extractable NIZK.** Finally, we combine $\Sigma_{ped}$ and $\Pi_{rp}$ to construct $\Pi_{ped}$ for the relation

$$R_{ped} = \{(x, w) \mid c \equiv h_2^{\overline{m}} \cdot g^{re} \mod N, E_i = e_i \overline{G} + s_i \overline{H}, S_i = s_i \overline{G}, e_i \in [0, B-1], \\ \overline{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1}, r = \sum_{i=1}^{\ell_r} e_{\ell_m + i} B^{i-1}\}.$$

The construction is similar to the NIZK in Section 6.3 [66] except that our $\Sigma$-protocol is more involved. We first define the $\text{srs}$ space. Recall that $\Sigma_{ped}$ relies on a fresh modulus $\tilde{N}$ and MPed parameters $\tilde{p}$. These are provided in the $\text{srs}$. To ensure subversion zero-knowledge, we follow the approach in Appendix C.1. That is, we add a NIZK to prove that shows that $\tilde{p}$ is setup in a hiding manner and set

$$\begin{aligned} \text{SRS} = & \{(\tilde{N}, \tilde{p}, \pi_{\text{gen}}) \mid \tilde{N} \in \mathbb{N}, \tilde{p} = (\tilde{h}, \tilde{g}_1, \dots, \tilde{g}_{\ell_m + \ell_r}) \in (\mathbb{Z}_N^*)^{1+\ell_m + \ell_r}, \\ & \Pi_{\text{gen}}.\text{Verify}^{\text{H}_{\text{gen}}}(x_{\text{gen}}, \pi_{\text{gen}}) = 1, x_{\text{gen}} = (\tilde{N}, \ell_m + \ell_r, \tilde{h}, (\tilde{g}_1, \dots, \tilde{g}_{\ell_m + \ell_r}))\}. \end{aligned}$$

The proof $\pi_{gen}$ ensures that the preconditions with respect to $\tilde{p}$ for the HVZK relation of $\Sigma_{ped}$ are ensured for malicious $\text{srs}$, and thus ensure subversion zero-knowledge. We denote by $H_{ped}$ the random oracle of $\Pi_{ped}$ and by $\text{URS} = \overline{\mathbb{G}}_{\ell_{rp}}^{\ell_{rp}}$ the space for the urs of $\Pi_{ped}$. Below, we have $\text{urs} \in \text{URS}$ and $\text{crs} = (\text{srs}, \text{urs})$ for some $\text{srs} \in \text{SRS}$. Let $H_\gamma$ be a random oracle mapping into $[0, C]$. The random oracle of $\Pi_{ped}$ is $H_{ped} = (H_{rp}, H_\gamma)$. Let $x = (B, \overline{G}, \overline{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m + \ell_r})$ and $w = (\overline{m}, r, (s_i)_{i \in [\ell_m + \ell_r]})$. The scheme is given below. Roughly, the prover decomposes $\overline{m}$ and $r$ via $B$-ary decomposition, commits to $e_i$ in ElGamal commitments $(E_i, S_i)$, and then proves that $e_i \in [0, B]$ via $\Pi_{rp}$ and that the committed values satisfy $\tilde{R}_{\Sigma_{ped}}$ via Fiat-Shamir compiled $\Sigma_{ped}$.

- $\Pi_{ped}.\text{GenSRS}(1^\lambda)$: Samples $\text{pp}_{MPed} = (\tilde{N}, \tilde{p}) \leftarrow \text{MPed}.\text{Setup}(1^\lambda)$ with $\tilde{p} = (\tilde{h}, \tilde{g}_1, \dots, \tilde{g}_{\ell_m + \ell_r})$. Then, sets $\pi_{gen} \leftarrow \Pi_{gen}.\text{Prove}^{\text{H}_{\text{gen}}}(w_{\text{gen}}, x_{\text{gen}})$ for $x_{\text{gen}}$ as above and appropriate $w_{\text{gen}}$. Outputs the structured reference string $\text{srs} = (\tilde{N}, \tilde{p}, \pi_{gen})$.

- $\Pi_{ped}.\text{Prove}^{\text{H}_{\text{ped}}}(\text{crs}, x, w)$: Parses $x = (B, \overline{G}, \overline{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m + \ell_r})$ and $w = (\overline{m}, r, (s_i)_{i \in [\ell_m + \ell_r]})$. Decomposes $\overline{m}$ and $r$ into $(m_i)_i$ and $(r_i)_i$ via $B$-ary decomposition, respectively. Note that $(E_i, S_i) = (e_i \overline{G} + s_i \overline{H}, s_i \overline{G})$. Then, computes

$$\pi_0 \leftarrow \Pi_{rp}.\text{Prove}^{\text{H}_{rp}}(\text{crs}, x_0, w_0),$$

<footnote>$^{36}$ We moved the generators $\overline{G}$ and $\overline{H}$ to the statement from the uniform reference string $\text{urs}_{rp}$. This is a purely notational change and we adapted the soundness relation below accordingly.</footnote>
for $x_0 = (\overline{G}, \overline{H}, B, (E_i)_{i \in [\ell_m + \ell_r]})$ and $w_0 = ((e_i, s_i)_{i \in [\ell_m + \ell_r]}),$

$$ (\Omega_{\Sigma}, \text{st}) \leftarrow \Sigma_{\text{ped}}.\text{Init}(x_1, w_1), $$

$$ \gamma_{\Sigma} \leftarrow \text{H}_{\gamma}(x_1, \Omega_{\Sigma}), $$

$$ \tau_{\Sigma} \leftarrow \Sigma_{\text{ped}}.\text{Resp}(x_1, \text{st}, \gamma_{\Sigma}), $$

$$ \pi_1 \leftarrow (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}), $$

for statement $x_1 = (\tilde{N}, \tilde{p}\tilde{p}, B, \overline{G}, \overline{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$ and witness $w_1 = ((e_i, s_i)_{i=1}^{\ell_m+\ell_r}, \overline{m}, r)$.

Outputs $\pi = (\pi_0, \pi_1)$.

– $\Pi_{\text{ped}}.\text{Verify}^{\text{H}_{\text{ped}}}(\text{crs}, x, \pi)$: On input crs, $x$, and $\pi = (\pi_0, \pi_1)$, checks

$$ \Pi_{\text{rp}}.\text{Verify}^{\text{H}_{\text{rp}}}(\text{crs}, x_0, \pi_0) = 1, $$

$$ \text{H}_{\gamma}(x_0, \Omega_{\Sigma}) = \gamma_{\Sigma}, $$

$$ \Sigma_{\text{ped}}.\text{Verify}(x_1, \Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}) = 1, $$

where $\pi_1 = (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma})$ and $x_0, x_1$ are defined as above, and outputs 1 iff all checks succeed.

We show that the scheme is sufficient to instantiate our framework $\text{BS}_{\text{fis}}$ in Section 6 (i.e., the NIZK is correct, subversion zero-knowledge, and partially online-extractable). Correctness and subversion zero-knowledge follow from the discussion above. For partial online-extraction, recall that statement $x$ and witness $w$ of relation $\text{R}_{\text{ped}}$ are split into $x_0 = (\overline{G}, \overline{H})$, $w_0 = (s_1, \dots, s_{\ell_m+\ell_r})$ and $x_1 = (B, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$, $w_1 = (\overline{m}, r)$. For the sake of simplicity, we sketch how the extractor proceeds to extract from a single proof. Let $\mathcal{A}$ be an adversary (i.e., prover) for online-extraction. Since the tuple $x_0 = (\overline{G}, \overline{H})$ is drawn at random from $X_0 = \overline{\mathbb{G}}_p^2$, the extractor samples $\overline{G} \leftarrow \overline{\mathbb{G}}_p$ and $\text{td} \leftarrow \mathbb{Z}_p$ at random, then sets $\overline{H} = \text{td} \cdot \overline{G}$. Then, it outputs $x_0 = (\overline{G}, \overline{H})$ and crs = (srs, urs) to $\mathcal{A}$, where srs $\leftarrow \Pi_{\text{ped}}.\text{GenSRS}(1^{\lambda})$ and urs $\leftarrow \text{URS}$. After obtaining (partial) statement $x_1$ and proof $\pi$ from $\mathcal{A}$, the extractor decrypts the ElGamal commitments $(E_i, S_i)$ via a brute-force computation of the discrete logarithm $e_i = \text{DLOG}_{\overline{G}}(E'_i)$ of $E'_i \leftarrow E_i - \text{td} \cdot S_i$. If $e_i \notin [0, B-1]$, the extractor aborts. (Since $B = \text{poly}(\lambda)$, the extractor remains efficient and the NIZKs guarantee that aborts happen with low probability.) Using $e_i$, the adversary recomputes $\overline{m}$ and $r$ via $B$-ary decomposition and checks that $c \equiv \overline{h}_i^m \cdot g^{re} \mod N$. Note that in that case, the existence of suitable ElGamal openings $w_0 = (s_i)_i$ is guaranteed. (These are the discrete logarithms $s_i = \text{DLOG}_{\overline{G}}(S_i)$ of $S_i$. A subtlety of the proof is that we need to extract from both proofs $\pi_0$ and $\pi_1$ of $\pi = (\pi_0, \pi_1)$ simultaneously in the case that extraction fails. Fortunately, this was shown to be possible in [66]. In both extractions succeed, we can reduce to either DLOG in $\overline{\mathbb{G}}_p$ or sRSA.

**Theorem 10.** The NIZK $\Pi_{\text{ped}}$ is correct, subversion zero-knowledge under the DDH assumption, and partially online-extractable under the sRSA assumption and the DLOG assumption in $\overline{\mathbb{G}}_p$.

*Proof.* Correctness is straightforward. In more detail, let us show that $(x_0, w_0) \in \text{R}_{\text{rp}}$ and $(x_1, w_1) \in \text{R}_{\text{sub}}$. Then, correctness of both $\Pi_{\text{rp}}$ and $\Sigma_{\text{ped}}$ yield correctness of $\Pi_{\text{ped}}$. First, observe that $e_i \in [0, B-1]$. Also, $E_i = e_i \overline{G} + s_i \overline{H}$ holds since $(x, w) \in \Sigma_{\text{ped}}$. Thus, $(x_0, w_0) \in \text{R}_{\text{rp}}$. Similarly, $(x, w) \in \Sigma_{\text{ped}}$ yields that $c \equiv \overline{h}_2^m \cdot g^{re} \mod N$, $S_i = s_i \overline{G}$. By construction, it holds that $e_i \in [0, B-1]$ and $\overline{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1}$, $r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}$. Further, we have that $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$ by definition of MPed. Setup. Thus, $(x_1, w_1) \in \text{R}_{\text{sub}}$ as desired.

Subversion zero-knowledge follows similarly to Theorem 9. Notably, we have $(x_0, w_0) \in \text{R}_{\text{sub}}$ by design—this follows as above and since $\pi_{\text{gen}}$ in the adversarial srs ensures that $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$ under soundness of $\Pi_{\text{gen}}$ with overwhelming probability. The simulator then simply simulates $\pi_1$ via HVZK of $\Sigma_{\text{ped}}$ and by programming $\text{H}_{\gamma}$ accordingly. (The latter is possible due to high min-entropy of $\Sigma_{\text{ped}}$.) Similarly, $\pi_0$ is simulated via the zero-knowledge simulator of $\Pi_{\text{rp}}$. This is possible since $(x_1, w_1) \in \text{R}_{\text{rp}}$ which again, follows as above.

Online-extraction requires some care, but the proof is similar to the proof of Theorem 20, [66] (taking into account that we embed the trapdoor into the statement $x_0 = (\overline{G}, \overline{H})$ instead of the crs). That is, the extractor Ext proceeds as follows.

– Ext$(1^{\lambda})$: Sets up $\overline{G} \leftarrow \overline{\mathbb{G}}_p$ and $\overline{H} \leftarrow \text{td} \cdot \overline{G}$ for $\text{td} \leftarrow \mathbb{Z}_p$ and outputs $x_0 = (\overline{G}, hp)$
- Ext(crs, td, x, π): Parses $x = (x_0, x_1)$ with $x_0 = (\bar{G}, \bar{H})$ and $x_1 = (B, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$. Note that $\bar{H} = \text{td} \cdot \bar{G}$. Decrypts the ElGamal commitments $(E_i, S_i)$ to $e_i = \text{DLOG}_{\bar{G}}(E'_i)$ via a discrete logarithm computation of $E'_i \leftarrow E_i - \text{td} \cdot S_i$ (but outputs $\perp$ and aborts if there is no such $e_i \in [0, B-1]$). Then, sets $\bar{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1}$ and $r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}$. Checks that $c \equiv h_2^{\bar{m}} \cdot g^{re} \bmod N$. If the check succeeds, outputs partial witness $w_1 = (\bar{m}, r)$, and $\perp$ otherwise.

Note that $\text{Ext}(1^\lambda)$ outputs uniform $(\bar{G}, \bar{H})$ over $\mathbb{G}_p^2 = X_0$ and that $\text{Ext}$ runs in polynomial time (since the DLOG computation aborts in case $e_i$ is not short, i.e., of polynomial size). Also, if all check succeed, then the output of $\text{Ext}$ is sufficient, i.e., there is a $w_0 = (s_1, \dots, s_{\ell_m+\ell_r})$ such that $((w_0, w_1), x) \in \mathbb{R}_{\text{ped}}$ due to the following facts.

- We have that $c \equiv h_2^{\bar{m}} \cdot g^{re} \bmod N$ due to the last check.

- We have that $E_i = e_i \bar{G} + s_i \bar{H}$ and $S_i = s_i \bar{G}$, $e_i \in [0, B-1]$, where $s_i = \text{DLOG}_{\bar{G}}(E'_i)$ for some $s_i \in \mathbb{Z}_p$. This holds by construction since for $s_i = \text{DLOG}_{\bar{G}}(S_i)$, we have that $E_i = E'_i + \text{td} \cdot S_i = e_i \bar{G} + s_i \bar{H}$.

- We have that $\bar{m} = \sum_{i=1}^{\ell_m} e_i B^{i-1}$, $r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1}$ by construction.

Now let $\mathcal{A}$ be an adversary that on input $(crs, x_0)$ outputs $Q_S$ pairs $(x_{1,i}, \pi_i)_{i \in [Q_S]}$ that verify (i.e., we have that $\Pi_{\text{ped}}.\text{Verify}^{\text{H}_{\text{ped}}}(crs, (x_0, x_{1,1}), \pi_i) = 1$) with probability at least $\mu(\lambda)$. Here, $crs = (\text{srs}, \text{urs}_{\text{rp}})$ is setup via $\text{srs} \leftarrow \Pi_{\text{ped}}.\text{Setup}(1^\lambda)$ and $\text{urs}_{\text{rp}} \leftarrow \mathbb{G}_p^{\ell_{\text{rp}}}$. Denote with $\text{Fail}_i$ the event that the proof $(x_{1,i}, \pi_i)$ verifies but extraction fails for $i \in [Q_S]$. It remains to show $\text{Pr}[\text{Fail}_i] = \text{negl}(\lambda)$. Then, we can conclude that $\text{Pr}[\exists i : \text{Fail}_i] = \text{negl}(\lambda)$ via a union bound.

Assume that $\text{Fail}_i$ occurs. Parse $x_{1,i} = (N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$ and $\pi_i = (\pi_{i,0}, \pi_{i,1})$ with $\pi_{i,0} = (\Omega_\Sigma, \gamma_\Sigma, \tau_\Sigma)$. Set $x = (x_0, x_{1,i})$, $x_{\text{rp}} = (\bar{G}, \bar{H}, B, (E_i)_{i \in [\ell_m+\ell_r]})$ and $x_\Sigma = (\tilde{N}, \tilde{p}\bar{p}, B, \bar{G}, \bar{H}, N, e, h_2, g, c, (E_i, S_i)_{i=1}^{\ell_m+\ell_r})$. We then use the procedure from Theorem 20, [66] to obtain a witness $w_{\text{rp}}$ such that $(x_{\text{rp}}, w_{\text{rp}}) \in \tilde{\mathbb{R}}_{\text{rp}} \supset \mathbb{R}_{\text{rp}}$ and two related transcripts $(tr, tr')$ of $\Sigma_{\text{ped}}$ for the statement $x_\Sigma$$^{37}$.

Under the DLOG assumption, we have $((\bar{G}, \bar{H}, \text{urs}_{\text{rp}}), w_{\text{rp}}) \in \mathbb{R}_{\text{dlog}}$ with at most negligible probability. Thus, $(x_{\text{rp}}, w_{\text{rp}}) \in \mathbb{R}_{\text{rp}}$ which means that $w_{\text{rp}} = (e'_i, s'_i)_{i \in [\ell_m+\ell_r]}$ and

$$E_i = e'_i \bar{G} + s'_i G' \text{ and } e'_i \in [0, B-1]. \qquad (14)$$

Then, we invoke 2-special soundness of $\Sigma_{\text{ped}}$ on $(tr, tr')$ and obtain a witness $w_\Sigma$ with $(x_\Sigma, w_\Sigma) \in \mathbb{R}_{\Sigma_{\text{ped}}}$. We have that $(x_\Sigma, w_\Sigma) \in \mathbb{R}$ or $(\bar{p}\bar{p}, w_\Sigma) \in \mathbb{R}_{C, \tilde{\ell}}(\bar{p}\bar{p})$ or $(\bar{p}\bar{p}, w_\Sigma) \in \mathbb{R}_{\text{dlog}}$. Under sRSA, we have that $(\bar{p}\bar{p}, w_\Sigma) \in \mathbb{R}_{C, \tilde{\ell}}(\bar{g})$ or $(\bar{p}\bar{p}, w_\Sigma) \in \mathbb{R}_{\text{dlog}}$ with at most negligible probability. Thus, $(x_\Sigma, w_\Sigma) \in \mathbb{R}$. Parse $w_\Sigma = ((e_i, s_i)_{i=1}^{\ell_m+\ell_r}, \bar{m}, r)$. By definition, it holds that

$$ \begin{align} c &\equiv h_2^{\bar{m}} \cdot g^{re} \bmod N \nonumber \\ E_i &= e_i \bar{G} + s_i \bar{H}, \quad S_i = s_i \bar{G} \nonumber \\ \bar{m} &= \sum_{i=1}^{\ell_m} e_i B^{i-1}, \quad r = \sum_{i=1}^{\ell_r} e_{\ell_m+i} B^{i-1} \tag{15} \end{align} $$

Notably, we have $e_i = e'_i$ under DLOG as otherwise, we can compute a non-trivial DLOG relation between $\bar{H}$ and $\bar{G}$. Finally, observe that Eqs. (14) and (15) with $e_i = e'_i$ imply that extraction of $\Pi_{\text{ped}}$ via $\text{Ext}$ succeeds, i.e., $\text{Fail}_i$ does not occur. Thus, $\text{Pr}[\text{Fail}_i] = \text{negl}(\lambda)$. This concludes the proof.

**Optimizations.** We apply standard $\Sigma$-protocol optimizations for $\Sigma_{\text{ped}}$. That is, we omit the first flow of $\Sigma_{\text{ped}}$ (i.e., the values $\Omega_{\tilde{c}}, \Omega_q, (\Omega_{E_i})_i, (\Omega_{S_i})_i, \Omega_c$ except $\tilde{c}$) from the proof $\pi_1$. The verification equations are then verified within the hash function $H_\gamma$.

**Efficiency.** We set $B = 2^{64}$. Then, the DLOG computation in extraction runs in time $O(2^{32})$. Further, we use standard RSA moduli and groups for $\lambda = 128$ bit security, i.e., $N$ and $\tilde{N}$ of size 3072 bit and group $\mathbb{G}_p$ with order 256 bit. With these parameters, we have $\ell_m + \ell_r = 54$ and an integer commitment $\mathbb{C}_Z$ is of size 3.46 KB. The online-extractable NIZK is of size 5.62 KB and the range proof $\Pi_{\text{rp}}$ is of size 1088 Byte. In total, the proof size of $\Pi_{\text{ped}}$ is 6.7 KB.

<footnote>$^{37}$ Roughly, the procedure extracts a witness for $x_{\text{rp}}$ via the knowledge extractor of $\Pi_{\text{rp}}$ and two related transcripts for $x_\Sigma$ via forking. Notably, the argument is agnostic to the concrete $\Sigma$-protocol that is being used. [66] proves that the procedure succeeds in polynomial time with probability close to $\text{Pr}[\text{Fail}_i]$. We refer to [66] for more details.</footnote>
## E.2 Instantiation of $\Pi_{fis}$

In this section, we instantiate $\Pi_{fis}$. Recall that $\Pi_{fis}$ allows to prove knowledge of a valid $S_{fis}$ signature $(e, a, y)$, where $(e, a)$ are fixed in a $C_{RInt}$ commitment $c_I$. We instantiate $C_{RInt}$ with $C_{RInt}^{\vec{B},T}$, where $\vec{B} = (2^{3\lambda}, 2^{3\lambda})$ and $T = 2^{\lambda+1}L$ for $L \in \mathbb{N}$ (cf. Section 5). As discussed in Section 6.1, we set $\overline{E} = 2^{5\lambda}$. The public parameters are $pp_I = (G_1, G_2, H) \in \mathbb{G}$ for some group $\mathbb{G}$ of order $p$ such that $2^{3\lambda}T < \frac{p-1}{2}$. We assume without loss of generality that $G_1, G_2, H \neq 0$. Denote by $\vec{G} := (G_1, G_2)$. We can rewrite the relation $R_{fis}$ as follows

$$R_{fis} := \left\{ (x, w) \mid \begin{array}{l} y^e \equiv h \cdot h_1^a \cdot h_2^{a+\vec{m}} \bmod N, e \equiv 1 \bmod 2, y \in \langle h_1 \rangle, \\ (e - \overline{E}, a) \in [0, \vec{B}], \vec{C} = (e - \overline{E}, a)H + r\vec{G}, F = rH \end{array} \right\},$$

for $x = (pp_I, N, h_1, h_2, h, \overline{m}, \vec{C}, F)$, $w = (e, a, y, r)$. The soundness relation can be written as $\tilde{R}_{fis}$

$$\tilde{R}_{fis} := \left\{ (x, w) \mid \begin{array}{l} y^e \equiv h \cdot h_1^a \cdot h_2^{a+\vec{m}} \bmod N, e \equiv 1 \bmod 2, \\ (e - \overline{E}, a) \in [\vec{B}T, \overline{B}T], \vec{C} = (e - \overline{E}, a)H + r\vec{G}, F = rH \end{array} \right\},$$

We construct a $\Sigma$-protocol $\Sigma_{fis}$ for the relation $R_{fis}$, and then compile it via Fiat-Shamir.

**Step 0: Preparing a ZK-friendly relation for $R_{fis}$.** First, we derive a more $\Sigma$-protocol friendly relation that implies $R_{fis}$. Assume that $y \in \langle h_1 \rangle^{38}$. Note that the relation $R_{fis}$ contains the equation

$$y^e \equiv h \cdot h_1^a \cdot h_2^{a+\vec{m}} \bmod N.$$

Since both $y$ and $e$ are part of the witness, this equation is non-trivial to prove, especially since $y$ is an element of a group $\langle h_1 \rangle$ that might be setup maliciously. We solve this by committing to $y$ in an additional $C_{Grp}$ commitment $c_N$ (cf. Section 5.2) over the group $\langle h_1 \rangle$. We recall that $C_{Grp}$ is an ElGamal commitment of the form $c_N = y \cdot h_1^s \in \langle h_1 \rangle$, where the integer randomness $s$ is fixed via an $\Pi_{int}$ commitment over a prime-order group. Then, with $\omega = e \cdot s \in \mathbb{Z}$, we have that

$$y^e \equiv c_N^e \cdot h_1^{-es} \equiv c_N^e \cdot h_1^{-\omega} \bmod N$$

and consequently, we have an equivalence

$$y^e \equiv h \cdot h_1^a \cdot h_2^{a+\vec{m}} \bmod N \Leftrightarrow c_N^e \cdot h_1^{-\omega} \equiv h \cdot h_1^a \cdot h_2^{a+\vec{m}} \bmod N \quad (16)$$

in $\mathbb{Z}_N^*$. More specifically, it suffices to show

$$c_N^e \cdot h_1^{-\omega} \equiv h \cdot h_1^a \cdot h_2^{a+\vec{m}} \bmod N \quad \wedge \quad \omega = e \cdot s \quad \wedge \quad C_{Grp} \cdot \text{Verify}(pp, c_N, y, s) = 1$$

and we can resort to well-known techniques for quadratic equations over $\mathbb{Z}$. Also, we follow the technique to open $c_N$ in zero-knowledge outlined in Section 5. Recall that $C_{Grp}$ is defined over a prime-order group. In order to use the same group $\mathbb{G}$ for the relaxed integer commitment of $C_{Grp}$ and the commitment $c_I$ of $(e, a)$ defined above, we split the integer randomness $s$ of $C_{Grp}$ into $\ell_s$ values $s_i \in [0, 2^{3\lambda} - 1]$ via $2^{3\lambda}$-ary decomposition, i.e., $s = \sum_{i=1}^{\ell_s} s_i \cdot 2^{3\lambda(i-1)}$. We recall to Section 5.2 for this splitting of $s$ into $\ell_s$ values in a vector $\vec{s} = (s_i)_{i \in [\ell_s]}$, while remarking that the domain of $s$ is $[0, N \cdot 2^{3\lambda}]$, since the order of $\langle h_1 \rangle$ is upper bounded by $N$. Specifically, we set $\ell_s = \lceil \frac{\log(N \cdot 2^{3\lambda})}{3\lambda} \rceil$ and $\vec{B}' = (2^{3\lambda}, \dots, 2^{3\lambda}) \in \mathbb{N}^{\ell_s}$. Then, we use a second relaxed integer commitment $C'_{RInt} = C_{RInt}^{\vec{B}',T}$ with public parameters $pp'_I = (H', G'_1, \dots, G'_{\ell_s})$ to commit to $\vec{s}$ satisfying $s_i \in [0, 2^{3\lambda} - 1]$ for all $i \in [\ell_s]$. Below, we denote by $\vec{G}' := (G'_1, \dots, G'_{\ell_s})$.

We modify the relation in two other ways:

1. Instead of using witness $e$, we use $\overline{e} = e - \overline{E}$ for some even $\overline{E} \in \mathbb{Z}$ and adapt the relations accordingly. As $\overline{e}$ is shorter, this reduces the proof size. Also, note that $e \equiv 1 \bmod 2$ is equivalent to showing that $\overline{e} = 2e' + 1$ over $\mathbb{Z}$ because $\overline{E}$ is even.

<footnote n="38">38 This is guaranteed by the correctness and HVZK relation.</footnote>
2. Let $\tilde{N} \in \mathbb{N}$. We add public parameters $\tilde{p} = (\tilde{h}, \tilde{g}_1, \dots, \tilde{g}_\ell) \in (\mathbb{Z}_{\tilde{N}}^*)^{\ell+1}$ for MPed to the statement, where $\ell = 4 + \ell_s$. In the $\Sigma$-protocol, the prover commits to the witnesses over $\mathbb{Z}$ via MPed. As in previous NIZKs, this allows to ensure that the extracted values are integers in the soundness proof.

We are now ready to describe the $\Sigma$-protocol-friendly relation. First, let us define the relation $R$ as follows. ($R$ serves as basis for both the correctness and HVZK relation, and the soundness relation.)

$$R := \{ (x, w) \mid c_N^{\bar{e}+\bar{E}} \cdot h_1^{-\omega} \cdot h_1^{-s \cdot \bar{E}} \equiv h \cdot h_1^a \cdot h_2^{a+\bar{m}} \mod N, \quad (17) $$

$$\omega = \bar{e} \cdot s, \bar{e} = 2e' + 1, \quad (18)$$

$$\tilde{C} = (\bar{e} \cdot H, a \cdot H) + r\tilde{G}, F = rH, \quad (19)$$

$$\tilde{C}' = \tilde{s}H' + r'\tilde{G}', F' = r'H, s = \sum_{i \in [\ell_s]} s_i 2^{3\lambda(i-1)}, c_N \equiv y \cdot h_1^s \mod N \}, \quad (20)$$

where $x = (c_N, \tilde{N}, \tilde{p}, pp_I, pp'_I, c, N, h_1, h_2, h, \bar{m}, \tilde{C}, F, \tilde{C}', F')$, $w = (e, a, y, r, r', \omega, (s_1, \dots, s_{\ell_s}))$. Let us remark that Eqs. (17) and (18) correspond to verifying that the signature $(e, a, y)$ is valid with respect to $S_{fis}$ verification (except the range membership), where $e = \bar{e} + \bar{E}$. Also, $y$ is committed in a $C_{Grp}$ commitment $(c_N, \tilde{C}', F')$ and $(\bar{e}, a)$ is committed in a $C_{Rint}$ commitment $(\tilde{C}, F)$, as specified by Eqs. (19) and (20), respectively, except range checks are omitted. Then, adding the range and subgroup checks, gives the correctness and HVZK relation $R_\Sigma$ as follows:

$$R_\Sigma := \{(x, w) \mid (x, w) \in R, y \in \langle h_1 \rangle, (\bar{e}, a) \in [0, \tilde{B}], (s_1, \dots, s_{\ell_s}) \in [0, \tilde{B}'], \langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle\}. \quad (21)$$

Note that $R_\Sigma$ is obtained by applying the modifications discussed above to $R_{fis}$. Similarly, applying the above modifications to the soundness relation $\tilde{R}_{fis}$, we obtain relation

$$\tilde{R}_{\Sigma} = \{(x, w) \mid ((x, w) \in R, (\bar{e}, a) \in [-\tilde{B}T, \tilde{B}T], (s_1, \dots, s_{\ell_s}) \in [-\tilde{B}'T, \tilde{B}'T]) \text{ or} \\ (\tilde{p}\tilde{p}, w) \in R_{C, \tilde{\ell}}(\tilde{p}\tilde{p}) \text{ or } (\tilde{p}\tilde{p}, w) \in R_{dlog}\},$$

where $R_{C, \tilde{\ell}}(\tilde{p}\tilde{p})$ is defined in Definition 7 and $R_{dlog}$ denotes the relation that contains all non-trivial DLOG relations in $\tilde{p}\tilde{p}$ (cf. Appendix E.1). Later, we show that a $\Sigma$-protocol for these relations allows to construct a NIZK for $R_{fis}$ via Fiat-Shamir under sRSA.

**Step 1: the $\Sigma$-protocol.** We now construct a $\Sigma$-protocol for relations $R_\Sigma, \tilde{R}_\Sigma$ defined in the previous paragraph. Set $C = 2^\lambda - 1$ which defines the challenge space $[0, C]$. The $\Sigma$-protocol $\Sigma_{fis}$ is given in Fig. 5. We briefly discuss the construction. (Note that we follow the design guidelines described in the beginning of Appendix E.)

- The Eq. (19) and the (relaxed) range membership for $(\bar{e}, a)$ correspond to opening a $C_{Rint}$ commitment in zero-knowledge. We proceed as discussed in Appendix C.1 for these equations (using MPed with parameters $\tilde{p}\tilde{p}$ to argue over the integers).

- The Eq. (20) and the (relaxed) range membership for $(s_i)_{i \in [\ell_s]}$ correspond to opening a $C_{Grp}$ commitment in zero-knowledge. We proceed as discussed in Appendix C.1 for these equations (again, using MPed with parameters $\tilde{p}\tilde{p}$ to argue over the integers).

- We show Eq. (17) with Schnorr-style $\Sigma$-protocol techniques.

- To show Eq. (18), we define degree 2 polynomials, where the leading coefficient is 0 iff both relations hold. That is, we construct a polynomial $f_e = f_{e,2}\gamma^2 + f_{e,1}\gamma + f_{e,0}$ and $f_\omega = f_{\omega,2}\gamma^2 + f_{\omega,1}\gamma + f_{\omega,0}$, where the challenge $\gamma$ is interpreted as variable, such that $f_{\omega,2} = f_{e,2} = 0$ implies that $\omega = \bar{e} \cdot s$ and $\bar{e} = 2e' + 1$. The prover shows that indeed $f_{\omega,2} = f_{e,2} = 0$ by committing to the non-zero coefficients in a MPed commitment. Then, the verifier recomputes $f_\omega(\gamma)$ and $f_e(\gamma)$ (which is possible by construction) and verifies that $f_\omega(\gamma) = f_{\omega,1}\gamma + f_{\omega,0}$ and $f_e(\gamma) = f_{e,1}\gamma + f_{e,0}$ by linearity of MPed over $\mathbb{Z}_{\tilde{N}}^*$.

Then, 3 special soundness is argued as follows. If $f_e(\gamma) = f_{\omega,1}\gamma + f_{\omega,0}$ holds for three 3 distinct challenge $\gamma$, then the polynomial $f_{diff} := f_e(x) - f_{e,1}x + f_{e,0}$ has three zeroes. Since the polynomial $f_{diff}$ is of degree 2 with 3 zeroes, it must be the zero polynomial. In particular, the leading coefficient of $f_e$ is zero and thus, $\bar{e} = 2e' + 1$. The equation $\omega = \bar{e} \cdot s$ is argued similarly.
- The integer witnesses are committed in a MPed commitment $\tilde{c}$ (with public parameters $\tilde{p}, \tilde{p}$). This allows to argue that extracted values are integers.

**Lemma 22.** The $\Sigma$-protocol $\Sigma_{\text{fis}}$ for relation $\mathbb{R}_{\Sigma}$ is correct with abort probability $1 - (1 - \frac{1}{L})^{\ell_s+3}$, is non-abort HVZK, has high min-entropy, and is 3-special sound for $\mathbb{R}_{\Sigma}$.

*Proof.* We only give a brief sketch as this follows as similarly to security of previous $\Sigma$-protocols. For correctness, we examine each of the checks. The range checks on lines 19 and 20 for $(\tau_{\tilde{e}}, \tau_a, \tilde{\tau}_s, \tau_{e'})$ are satisfied thanks to the checks by prover before sending the responses (on lines 17 and 18). The check on line 21 on the commitment $\Omega_f$ is satisfied by

$$ 
\begin{align*}
& c_N^{-\tau_{\tilde{e}}} \cdot h_1^{\tau_{\tilde{\omega}}} \cdot h_1^{\bar{E}} \sum_{i \in [\ell_s]} \tau_{s_i} 2^{3\lambda(i-1)} \cdot h^{\gamma} \cdot h_1^{\tau_a} \cdot h_2^{\tau_a + \gamma \bar{m}} \\
& \equiv c_N^{-\gamma \bar{e} - \mu_{\tilde{e}}} \cdot h_1^{\gamma \omega + \mu_{\tilde{\omega}}} \cdot h_1^{\bar{E}} \sum_{i \in [\ell_s]} (\gamma s_i + \mu_{s_i}) 2^{3\lambda(i-1)} \cdot h^{\gamma} \cdot h_1^{\gamma a + \mu_a} \cdot h_2^{\gamma a + \mu_a + \gamma \bar{m}} \mod N \\
& \equiv c_N^{-\mu_{\tilde{e}}} \cdot h_1^{\mu_{\tilde{\omega}}} \cdot h_1^{\bar{E}} \sum_{i \in [\ell_s]} \mu_{s_i} 2^{3\lambda(i-1)} \cdot h_1^{\mu_a} \cdot h_2^{\mu_a} \cdot \left( c_N^{-\gamma \bar{e}} \cdot h_1^{\gamma \omega} \cdot h_1^{\gamma \bar{E}} \sum_{i \in [\ell_s]} s_i 2^{3\lambda(i-1)} \cdot h^{\gamma} \cdot h_1^{\gamma a} \cdot h_2^{\gamma a + \gamma \bar{m}} \right) \mod N \\
& \stackrel{(*)}{\equiv} c_N^{-\mu_{\tilde{e}}} \cdot h_1^{\mu_{\tilde{\omega}}} \cdot h_1^{\bar{E}} \sum_{i \in [\ell_s]} \mu_{s_i} 2^{3\lambda(i-1)} \cdot h_1^{\mu_a} \cdot h_2^{\mu_a} \cdot \left( c_N^{-\gamma \bar{e}} \cdot h_1^{\gamma \omega} \cdot h_1^{\gamma \bar{E}s} \cdot h^{\gamma} \cdot h_1^{\gamma a} \cdot h_2^{\gamma a + \gamma \bar{m}} \right) \mod N \\
& \stackrel{(**)}{\equiv} c_N^{-\mu_{\tilde{e}}} \cdot h_1^{\mu_{\tilde{\omega}}} \cdot h_1^{\bar{E}} \sum_{i \in [\ell_s]} \mu_{s_i} 2^{3\lambda(i-1)} \cdot h_1^{\mu_a} \cdot h_2^{\mu_a} \mod N \\
& \equiv \Omega_f \mod N
\end{align*}
$$

where we make use of the response calculations $\tau_e \leftarrow \gamma e + \mu_e, \tau_a \leftarrow \gamma a + \mu_a, \tau_\omega \leftarrow \gamma \omega + \mu_\omega$ over $\mathbb{Z}$, (*) follows from the unique $2^{3\lambda(i-1)}$-decomposition of $s = \sum_{i \in [\ell_s]} s_i 2^{3\lambda(i-1)}$, and (**) follows from Equation (17). Next, the check on line 22 is satisfied as per the following computation over $\mathbb{G}$

$$ (\tau_{\tilde{e}}, \tau_a)H + \tau_r \tilde{G} - \gamma \tilde{C} = (\gamma \tilde{e} + \mu_{\tilde{e}}, \gamma a + \mu_a)H + (\gamma r + \mu_r)\tilde{G} - \gamma((\tilde{e} \cdot H, a \cdot H) + r\tilde{G}) \quad (22) $$

$$ = (\mu_{\tilde{e}}, \mu_a)H + \mu_r \tilde{G} = \tilde{\Omega}_C, \quad (23) $$

$$ \begin{align*}
& \tau_r H - \gamma F \\
&= (\gamma r + \mu_r)H - \gamma r H \\
&= \Omega_F \tag{24}
\end{align*} $$

where the first equality (22) follows from the definition (19) of $\tilde{C} = (\bar{e}H, aH) + r \cdot \tilde{G}$ in relation $\mathbb{R}_{\Sigma}$, and equalities (23, 24) follow from the definitions by prover at line 6.

We now examine the next check on line 23. In the same vein of computation

$$ 
\begin{align*}
& \tau_s H' + \tau_{r'} \tilde{G}' - \gamma \tilde{C}' \\
&= (\gamma \tilde{s} + \tilde{\mu}_s) H' + (\gamma r' + \mu_{r'}) \tilde{G}' - \gamma (\tilde{s} \cdot H' + r' \tilde{G}') \\
&= \tilde{\mu}_s H' + \mu_{r'} \tilde{G}' \\
&= \tilde{\Omega}_{C'}, \\
& \tau_{r'} H' - \gamma F' \\
&= (\gamma r' + \mu_{r'}) H' - \gamma r' H' \\
&= \Omega_{F'},
\end{align*}
$$

where the opening $\tau_s \leftarrow \gamma \tilde{s} + \tilde{\mu}_s$ and the opening $\tau_{r'} \leftarrow \gamma r' + \mu_{r'}$ are both over $\mathbb{Z}$ from lines (16, 13), for which the group exponentiation is well defined in the cyclic group $\mathbb{G}$. Regarding the check on line 24, we apply the specification of the opening $\tau_t \leftarrow \gamma \tilde{t} + \mu_t$, together with those of $\tau_{\tilde{e}} \leftarrow \gamma \bar{e} + \mu_{\tilde{e}}, \tau_a \leftarrow \gamma a + \mu_a, \tau_{e'} \leftarrow \gamma e' + \mu_{e'}$ as well as $\tau_s \leftarrow \gamma \tilde{s} + \tilde{\mu}_s$ by the prover on lines (14, 15, 16),
respectively:

$$
\begin{align*}
& \tilde{c}^{-\gamma} \cdot h^{\tau_{\tilde{t}}} \cdot \tilde{g}_1^{\tau_{\tilde{e}}} \tilde{g}_2^{\tau_{\tilde{a}}} \tilde{g}_3^{\tau_{\tilde{e}'}} \prod_{i \in [\ell_s]} \tilde{g}_{3+i}^{\tau_{s_i}} \cdot \tilde{g}_{4+\ell_s}^{\tau_{\omega}} \\
& \equiv \tilde{c}^{-\gamma} \cdot h^{\gamma \tilde{t} + \mu_{\tilde{t}}} \cdot \tilde{g}_1^{\gamma \tilde{e} + \mu_{\tilde{e}}} \tilde{g}_2^{\gamma a + \mu_a} \tilde{g}_3^{\gamma e' + \mu_{e'}} \prod_{i \in [\ell_s]} \tilde{g}_{3+i}^{\gamma s_i + \mu_{s_i}} \cdot \tilde{g}_{4+\ell_s}^{\gamma \omega + \mu_{\omega}} \\
& \stackrel{(*)}{=} (h^{\tilde{t}} \cdot \tilde{g}_1^{\tilde{e}} \tilde{g}_2^{\tilde{a}} \tilde{g}_3^{\tilde{e}'}) \prod_{i \in [\ell_s]} \tilde{g}_{3+i}^{s_i} \cdot \tilde{g}_{4+\ell_s}^{\omega} \stackrel{-\gamma}{=} h^{\gamma \tilde{t} + \mu_{\tilde{t}}} \cdot \tilde{g}_1^{\gamma \tilde{e} + \mu_{\tilde{e}}} \tilde{g}_2^{\gamma a + \mu_a} \tilde{g}_3^{\gamma e' + \mu_{e'}} \prod_{i \in [\ell_s]} \tilde{g}_{3+i}^{\gamma s_i + \mu_{s_i}} \tilde{g}_{4+\ell_s}^{\gamma \omega + \mu_{\omega}} \\
& \equiv (h^{\mu_{\tilde{t}}} \cdot \tilde{g}_1^{\mu_{\tilde{e}}} \tilde{g}_2^{\mu_a} \tilde{g}_3^{\mu_{e'}}) \prod_{i \in [\ell_s]} \tilde{g}_{3+i}^{\mu_{s_i}} \cdot \tilde{g}_{4+\ell_s}^{\mu_{\omega}} \\
& \equiv \Omega_{\tilde{c}} \mod \tilde{N}
\end{align*}
$$

where (*) and the last equality follow from the definition of $\tilde{c}$ and the definition of $\Omega_{\tilde{c}}$ by prover on line 10, respectively. Lastly, the check on line 26 is satisfied by

$$
\tilde{c}_q^\gamma \cdot \Omega_q \equiv (\tilde{h}^{t_q} \cdot \tilde{g}_1^{f_{\omega,1}} \cdot \tilde{g}_2^{f_{e,1}})^\gamma \cdot \tilde{h}^{\mu_{t_q}} \cdot \tilde{g}_1^{f_{\omega,0}} \cdot \tilde{g}_2^{f_{e,0}} \quad (25)
$$

$$
\equiv \tilde{h}^{\gamma t_q + \mu_{t_q}} \cdot \tilde{g}_1^{\gamma \cdot (\mu_{\omega} - \sum_{i \in [\ell_s]} (\mu_{s_i} e + s_i \mu_e) 2^{3\lambda(i-1)})} - \sum_{i \in [\ell_s]} \mu_{s_i} \mu_e 2^{3\lambda(i-1)} \cdot \tilde{g}_2^{\mu_e - 2\gamma\mu_e'} \quad (26)
$$

$$
\equiv \tilde{h}^{\tau_{t_q}} \cdot \tilde{g}_1^{f_{\omega}} \cdot \tilde{g}_2^{f_e} \qquad (27)
$$

where equation (25) follows from the definition of $\tilde{c}_q$ and $\Omega_q$ by prover on line 10, equation (26)
comes from $f_{\omega,0} \leftarrow - \sum_{i \in [\ell_s]} \mu_{s_i} \tilde{\mu}_e 2^{3\lambda(i-1)}$ as well as

$$
f_{\omega,1} \leftarrow \mu_{\omega} - \sum_{i \in [\ell_s]} (\mu_{s_i} e + s_i \mu_e) 2^{3\lambda(i-1)} + \sum_{i \in [\ell_s]} \mu_{s_i} \overline{E} 2^{3\lambda(i-1)} = \mu_{\omega} - \sum_{i \in [\ell_s]} (\mu_{s_i} \overline{e} + s_i \mu_{\overline{e}}) 2^{3\lambda(i-1)},
$$

where we are using the fact that $\bar{e} = e - \overline{E}$. Moreover, $f_{e,0} \leftarrow \mu_{\bar{e}}, f_{e,1} \leftarrow -2\mu_{e'}$ on lines (8, 9)
by prover, and the last equation (27) results from $\tau_{t_q} \leftarrow \gamma t_q + \mu_{t_q} \in \mathbb{Z}$ together with the below
calculation

$$
\begin{align}
f_{\omega} &= \gamma \cdot \tau_{\omega} - \left( \sum_{i \in [\ell_s]} \tau_{s_i} 2^{3\lambda(i-1)} \right) \cdot \tau_{\bar{e}} \nonumber \\
&= \gamma \cdot (\mu_{\omega} + \gamma\omega) - \left( \sum_{i \in [\ell_s]} (\mu_{s_i} + \gamma s_i) \cdot 2^{3\lambda(i-1)} \right) \cdot (\mu_{\bar{e}} + \gamma\bar{e}) \nonumber \\
&= \gamma \cdot \left( \mu_{\omega} - \sum_{i \in [\ell_s]} (\mu_{s_i} \bar{e} + s_i \mu_{\bar{e}}) 2^{3\lambda(i-1)} \right) - \sum_{i \in [\ell_s]} \mu_{s_i} 2^{3\lambda(i-1)} \mu_{\bar{e}} + \gamma^2 \cdot (\omega - s\bar{e}) \nonumber \\
&= \gamma \cdot \left( \mu_{\omega} - \sum_{i \in [\ell_s]} (\mu_{s_i} \bar{e} + s_i \mu_{\bar{e}}) 2^{3\lambda(i-1)} \right) - \sum_{i \in [\ell_s]} \mu_{s_i} 2^{3\lambda(i-1)} \mu_{\bar{e}} \tag{28}
\end{align}
$$

$$
\begin{align}
f_e &= \gamma \cdot (\tau_{\bar{e}} - (2 \cdot \tau_{e'} + \gamma)) \nonumber \\
&= \gamma \cdot (\gamma \bar{e} + \mu_{\bar{e}} - 2 \cdot \mu_{e'} - 2\gamma e' - \gamma) \nonumber \\
&= \gamma \cdot (\mu_{\bar{e}} - 2 \cdot \mu_{e'}) \tag{29}
\end{align}
$$

in which equation (28) follows from the condition (18) that $\omega = \bar{e}s$ in $\mathbb{R}_{\Sigma}$, while equation (29) also
follows from $\bar{e} = 2e' + 1$ in condition (18) of $\mathbb{R}_{\Sigma}$.

For showing that the $\Sigma$-protocol has high min-entropy, we consider the first flow

$$
\Omega := (\tilde{c}, \tilde{c}_q, \tilde{\Omega}_C, \Omega_F, \tilde{\Omega}_{C'}, \Omega_{F'}, \Omega_{\tilde{c}}, \Omega_q).
$$

Recall that $\mathbb{G}$ is of order $p > 2^{2\lambda}$. Observe that $\Omega_F = \mu_r H$ is distributed uniform over $\mathbb{G}$, since $H \neq 0$ and $\mu_r$ is sampled uniform over $\mathbb{Z}_p$. Thus, an adversary can predict $\Omega$ with probability at most $2^{-2\lambda}$, and the $\Sigma$-protocol has high min-entropy.

For non-abort HVZK, we need to show that the transcript can be simulated indistinguishably conditioned that the prover does not abort and the challenge $\gamma$ of an honest verifier is known in
advance. We observe that following properties of noise flooding (recall Supplementary Materials A.2), the masking by

$$
\begin{align*}
\mu_{\tilde{t}}, \mu_{t_q} &\leftarrow [0, CN \cdot 2^{2\lambda}] \\
(\mu_{\tilde{e}}, \mu_a) &\leftarrow [0, (\tilde{B}C + 1)L], \mu_{e'} \leftarrow [0, (B_1C + 1)L] \\
\vec{\mu}_s &\leftarrow [0, (\tilde{B}'C + 1)L] \\
\mu_{\omega} &\leftarrow [0, CB_1N \cdot 2^{2\lambda}]
\end{align*}
$$

ensures that the following values

$$
\begin{align*}
\tau_{\tilde{t}} &\leftarrow \gamma \tilde{t} + \mu_{\tilde{t}}, \tau_{t_q} &\leftarrow \gamma t_q + \mu_{t_q} \\
\tau_{\tilde{e}} &\leftarrow \gamma \tilde{e} + \mu_{\tilde{e}}, \tau_a &\leftarrow \gamma a + \mu_a, \tau_{e'} &\leftarrow \gamma e' + \mu_{e'} \\
\vec{\tau}_s &\leftarrow \gamma \vec{s} + \mu_{\vec{s}}, \tau_{\omega} &\leftarrow \gamma \omega + \mu_{\omega}
\end{align*}
$$

sent in the third flow are distributed uniform over the corresponding interval in the prover's range conditioned on no abort. Similarly, $\tau_r \leftarrow \gamma r + \mu_r$, $\tau_{r'} \leftarrow \gamma r' + \mu_{r'}$ are distributed uniform since $\mu_r, \mu_{r'}$ are sampled uniformly at random from $\mathbb{Z}_p$. Also, $\tilde{c}$ and $\tilde{c}_q$ are distributed close to uniform over $\langle \tilde{h} \rangle$ (with statistical distance at most $2^{-\lambda}$) because $\tilde{t}$ and $t_q$ are drawn uniform over $[0, N \cdot 2^{\lambda}]$, and because $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$. (Note that the order of $\langle \tilde{h} \rangle \subseteq \mathbb{Z}_N^*$ is at most $N$.) The remaining values $\tilde{\Omega}_C, \tilde{\Omega}_F, \tilde{\Omega}_{C'}, \tilde{\Omega}_{F'}, \tilde{\Omega}_{\tilde{c}}$ and $\tilde{\Omega}_q$ are determined from the third flow and the challenge $\gamma$, by setting with respect to the verification equations

$$
\begin{align*}
\Omega_f &= c_N^{-\tau_{\tilde{e}}} \cdot h_1^{\tau_{\tilde{\omega}}} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} \tau_{s_i} 2^{3\lambda(i-1)}} \cdot h^{\gamma} \cdot h_1^{\tau_a} \cdot h_2^{\tau_a + \gamma \overline{m}} \mod N \\
\tilde{\Omega}_C &= (\tau_{\tilde{e}}, \tau_a)H + \tau_r \tilde{G} - \gamma \tilde{C}, \quad \Omega_F = \tau_r H - \gamma F \\
\tilde{\Omega}_{C'} &= \tilde{\tau}_s H' + \tau_{r'} \tilde{G}' - \gamma \tilde{C}', \quad \Omega_{F'} = \tau_{r'} H' - \gamma F' \\
\Omega_{\tilde{c}} &= \tilde{c}^{-\gamma} \cdot h^{\tau_{\tilde{t}}} \cdot \tilde{g}_1^{\tau_{\tilde{e}}} \tilde{g}_2^{\tau_a} \tilde{g}_3^{\tau_{e'}} \prod_{i \in [\ell_s]} \tilde{g}_{3+i}^{\tau_{s_i}} \mod \tilde{N} \\
\Omega_q &= \tilde{c}_q^{-\gamma} \cdot \tilde{h}^{\tau_{t_q}} \cdot \tilde{g}_1^{f_{\omega}} \cdot \tilde{g}_2^{f_e} \mod \tilde{N}
\end{align*}
$$

where $f_\omega = \gamma \cdot \tau_\omega - (\sum_{i \in [\ell_s]} \tau_{s_i} 2^{3\lambda(i-1)}) \cdot (\tau_{\tilde{e}})$, $f_e = \gamma(\tau_{\tilde{e}} - (2 \cdot \tau_{e'} + \gamma))$. Given the above discussion, it is straightforward to provide an appropriate simulator. Roughly, the simulator receives the challenge $\gamma$ and samples the responses (for the third flow) according to the above distributions. It also samples $\tilde{c}$ and $\tilde{c}_q$ (with negligible distance close to) uniform over $\langle \tilde{h} \rangle$. Finally, it recomputes the remaining first flow that is determined as above and outputs the full transcript. Since the distribution is statistically close to the real protocol (conditioned on no abort), the simulator suffices.

For 3-special soundness, let us construct a deterministic PT extractor so that, for

$$
x = (c_N, \tilde{N}, \tilde{p}, \tilde{p}_I, \tilde{p}'_I, c, N, h_1, h_2, h, \bar{m}, \vec{C}, F, \vec{C}', F'),
$$

given 3 valid related transcripts that are indexed by $i \in [3]$

$$
\begin{array}{ll}
\text{Identical first flow:} & \Omega = (\tilde{c}, \tilde{c}_q, \Omega_f, \tilde{\Omega}_C, \Omega_F, \tilde{\Omega}_{C'}, \Omega_{F'}, \tilde{\Omega}_{\tilde{c}}, \Omega_q) \\
\text{Pairwise distinct challenge:} & \gamma_i \\
\text{Third flow:} & \vec{\tau}_i = (\tau_{r,i}, \tau_{r',i}, \tau_{\tilde{t},i}, \tau_{t_q,i}, \tau_{\tilde{e},i}, \tau_{a,i}, \tau_{e',i}, \tau_{s,i}, \tau_{\omega,i})
\end{array}
$$

the extractor extracts a witness $w$ such that $(x, w) \in \tilde{\mathbb{R}}_\Sigma$. In the following, we denote by $\Delta v_{i,j} := \tau_{v,i} - \tau_{v,j} \in \mathbb{Z}$ for $v \in \{r, r', \tilde{t}, t_q, \tilde{e}, a, e', s, \omega\}$ and $\Delta \gamma_{i,j} := \gamma_i - \gamma_j$.

By verification, we have that for $i \in [3]$, it holds that

$$
\tilde{c}^{-\gamma_i} \cdot h^{\tau_{\tilde{t},i}} \cdot \tilde{g}_1^{\tau_{\tilde{e},i}} \tilde{g}_2^{\tau_{a,i}} \tilde{g}_3^{\tau_{e',i}} \prod_{k \in [\ell_s]} \tilde{g}_{3+k}^{\tau_{s,k,i}} \cdot \tilde{g}_{4+\ell_s}^{\tau_{\omega}} \equiv \Omega_{\tilde{c}} \mod \tilde{N}
$$

Thus, it holds for $i \neq j \in [3]$ that

$$
\tilde{c}^{\Delta \gamma_{i,j}} \equiv h^{\Delta \tilde{t}_{i,j}} \cdot \tilde{g}_1^{\Delta \tilde{e}_{i,j}} \tilde{g}_2^{\Delta a_{i,j}} \tilde{g}_3^{\Delta e'_{i,j}} \prod_{k \in [\ell_s]} \tilde{g}_{3+k}^{\Delta s_{k,i,j}} \cdot \tilde{g}_{4+\ell_s}^{\Delta \omega_{i,j}} \mod \tilde{N}
$$
Thus, either $\Delta\gamma_{i,j}$ divides $\Delta v_{i,j}$ for $v \in \{\tilde{t}, \bar{e}, a, e', s, \omega\}$ over $\mathbb{Z}$, or the above equation yields a witness $w$ for $(\overline{\mathfrak{p}\mathfrak{p}}, w) \in \mathbb{R}_{C, \ell}(\overline{\mathfrak{p}\mathfrak{p}})$. In the latter case, the extractor outputs the witness $w$. In the former case, the extractor defines $r := \Delta r_{1,2}/\Delta\gamma_{1,2} \bmod p$, $r' := \Delta r'_{1,2}/\Delta\gamma_{1,2} \bmod p$ over $\mathbb{Z}_p$, as well $\bar{e} := \Delta\bar{e}_{1,2}/\Delta\gamma_{1,2}$, $a := \Delta a_{1,2}/\Delta\gamma_{1,2}$, $s_i := \Delta(s_i)_{1,2}/\Delta\gamma_{1,2}$, and $\omega := \Delta(\omega)_{1,2}/\Delta\gamma_{1,2}$ over $\mathbb{Z}$ (which is now well-defined).

Further, the verification checks ensure that

$$ (\tau_{\bar{e},1}, \tau_{a,1})H + \tau_{r,1}\vec{G} - \gamma_1\vec{C} = (\tau_{\bar{e},2}, \tau_{a,2})H + \tau_{r,2}\vec{G} - \gamma_2\vec{C} = (\tau_{\bar{e},3}, \tau_{a,3})H + \tau_{r,3}\vec{G} - \gamma_3\vec{C} \quad (30) $$

$$ \tau_{r,1}H - \gamma_1 F = \tau_{r,2}H - \gamma_2 F = \tau_{r,3}H - \gamma_3 F \quad (31) $$

$$ \vec{\tau}_{s,1}H' + \tau_{r',1}\vec{G}' - \gamma_1\vec{C}' = \vec{\tau}_{s,2}H' + \tau_{r',2}\vec{G}' - \gamma_2\vec{C}' = \vec{\tau}_{s,3}H' + \tau_{r',3}\vec{G}' - \gamma_3\vec{C}' \quad (32) $$

$$ \tau_{r',1}H' - \gamma_1 F' = \tau_{r',2}H' - \gamma_2 F' = \tau_{r',3}H' - \gamma_3 F' \quad (33) $$

We first use the identities (31, 33) to obtain

$$ F = \frac{\Delta r_{1,2}}{\Delta \gamma_{1,2}} H = rH $$

$$ F' = \frac{\Delta r'_{1,2}}{\Delta \gamma_{1,2}} H' = r'H $$

as correct representations of $F$ and $F'$. Then, the identity (30) gives

$$ \begin{aligned} & (\tau_{\bar{e},1}, \tau_{a,1})H + \tau_{r,1}\vec{G} - \gamma_1\vec{C} &&= (\tau_{\bar{e},2}, \tau_{a,2})H + \tau_{r,2}\vec{G} - \gamma_2\vec{C} \\ \Rightarrow & (\tau_{\bar{e},1} - \tau_{\bar{e},2}, \tau_{a,1} - \tau_{a,2})H + (\tau_{r,1} - \tau_{r,2})\vec{G} &&= (\gamma_1 - \gamma_2)\vec{C} \\ \Rightarrow & \vec{C} &&= \left( \frac{\Delta\bar{e}_{1,2}}{\Delta\gamma_{1,2}}, \frac{\Delta a_{1,2}}{\Delta\gamma_{1,2}} \right) H + \frac{\Delta r_{1,2}}{\Delta\gamma_{1,2}}\vec{G} \\ \Rightarrow & \vec{C} &&= (\bar{e}, a)H + r\vec{G}. \end{aligned} $$

Thus, the extractor obtains a correct opening for $\vec{C}$ where the range is ensured $(\bar{e}, a) \in [-\vec{B}T, \vec{B}T]$ thanks to check on line 19 and $0 \neq \Delta\gamma_{1,2} \in (0, C]$ without loss of generality. The same calculation based on (32) can be carried out for $\vec{C}'$ as well, yielding

$$ \vec{C}' = \vec{s}H' + r'\vec{G}' $$

The obtained opening is ensured to be correct (in the sense that $\vec{s} \in [-\vec{B}'T, \vec{B}'T]$) thanks to passing the check on line 20 and $0 \neq \Delta\gamma_{1,2} \in (0, C]$ without loss of generality.

Next, we look at the check on line 21, where the three valid transcripts give

$$ \begin{aligned} & c_N^{-\tau_{\bar{e},1}} \cdot h_1^{\tau_{\omega,1}} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} \tau_{1,s_i} 2^{3\lambda(i-1)}} \cdot h_1^{\gamma_1} \cdot h_1^{\tau_{a,1}} \cdot h_2^{\tau_{a,1}+\gamma_1 \overline{m}} \\ & \equiv c_N^{-\tau_{\bar{e},2}} \cdot h_1^{\tau_{\omega,2}} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} \tau_{2,s_i} 2^{3\lambda(i-1)}} \cdot h_1^{\gamma_2} \cdot h_1^{\tau_{a,2}} \cdot h_2^{\tau_{a,2}+\gamma_2 \overline{m}} \\ & \equiv c_N^{-\tau_{\bar{e},3}} \cdot h_1^{\tau_{\omega,3}} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} \tau_{3,s_i} 2^{3\lambda(i-1)}} \cdot h_1^{\gamma_3} \cdot h_1^{\tau_{a,3}} \cdot h_2^{\tau_{a,3}+\gamma_3 \overline{m}} \\ & \equiv \Omega_f \bmod N. \end{aligned} $$

In particular, this implies

$$ c_N^{-\Delta\bar{e}_{1,2}} \cdot h_1^{\Delta\omega_{1,2}} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} \Delta s_{i(1,2)} 2^{3\lambda(i-1)}} \equiv h^{\Delta\gamma_{1,2}} \cdot h_1^{\Delta a_{1,2}} \cdot h_2^{\Delta a_{1,2}+\Delta\gamma_{1,2} \overline{m}} \bmod N. \quad (34) $$

As noted above, $\Delta\gamma_{1,2}$ divides all the values in the exponent over $\mathbb{Z}$, and thus, equation (34) implies that:

$$ \begin{aligned} & c_N^{-\Delta\bar{e}_{1,2}/\Delta\gamma_{1,2}} \cdot h_1^{\Delta\omega_{1,2}/\Delta\gamma_{1,2}} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} \frac{\Delta s_{i(1,2)}}{\Delta\gamma_{1,2}} 2^{3\lambda(i-1)}} \equiv h \cdot h_1^{\Delta a_{1,2}/\Delta\gamma_{1,2}} \cdot h_2^{\Delta a_{1,2}/\Delta\gamma_{1,2}+\overline{m}} \bmod N \\ & \Rightarrow c_N^{-\bar{e}} \cdot h_1^{\omega} \cdot h_1^{\overline{E} \sum_{i \in [\ell_s]} s_i 2^{3\lambda(i-1)}} \equiv h \cdot h_1^a \cdot h_2^{a+\overline{m}} \bmod N \end{aligned} $$
leading to a witness for equation (17) in $\tilde{\mathbb{R}}_\Sigma$. Also, the extractor sets $y$ such that $y \equiv c_N \cdot h_1^{-s}$, where $s = \sum_{i \in [\ell_s]} s_i 2^{3\lambda(i-1)}$ and finally, $w = (e, a, y, r, r', \omega, (s_1, \dots, s_{\ell_s}))$. It remains to show that $\omega = \bar{e} \cdot s, \bar{e} = 2e' + 1$. Roughly, this follows due to the check in line 26 since we there are three related transcripts. This follows similarly to the equations over $\mathbb{Z}$ in Lemma 20, else we find a witness for the hard DLOG relation. (Note that we need 3 related transcripts because the degree of $f$ is 2 instead of 1 but the required adaptions to obtain the result are straightforward).

**Step 2: the NIZK.** For the final NIZK, we compile $\Pi_{fis}$ into an NIZK via Fiat-Shamir with abort. Again, we require public parameters for MPed in the srs, where $SRS$ is defined as in Appendix E.1, i.e.,

$$ SRS = \{(\tilde{N}, \tilde{\mathbb{p}}, \pi_{\text{gen}}) \mid \tilde{N} \in \mathbb{N}, \tilde{\mathbb{p}} = (\tilde{h}, \tilde{g}_1, \dots, \tilde{g}_{4+\ell_s}) \in (\mathbb{Z}_N^*)^{5+\ell_s}, \\ \Pi_{\text{gen}}.\text{Verify}^{\text{H}_{\text{gen}}}(x_{\text{gen}}, \pi_{\text{gen}}) = 1, x_{\text{gen}} = (\tilde{N}, 3+\ell_s, \tilde{h}, (\tilde{g}_1, \dots, \tilde{g}_{\ell_m+\ell_r})) \} $$

Let $URS = \mathbb{G}^{1+\ell_s}$. Note that $urs = \mathbb{p}\mathbb{p}'$ specifies the public parameters for a second $C_{RInt}$ commitment (in addition to the $\mathbb{p}\mathbb{p}'$ within the statement). This is the commitment for $C_{Grp}$. We denote by $H_{fis} = (H_{gen}, H_\gamma)$ random oracle of $\Pi_{fis}$. (Here, $H_{gen}$ corresponds to the random oracle for $\Pi_{gen}$ and $H_\gamma$ maps into $[0, C]$.) Below, we have $urs \in URS$ and $crs = (srs, urs)$ for some srs $\in SRS$. Also, let $x = (\mathbb{p}\mathbb{p}'_I, N, h_1, h_2, h, \bar{m}, \vec{C}, F)$ and $w = (e, a, y, r)$. (Note that $(\vec{C}, F)$ corresponds to an $C_{RInt}$ commitment to $(a, e - \bar{E})$ with opening $r$.) The scheme is given below.

- $\Pi_{fis}.\text{GenSRS}(1^\lambda)$: Samples $\mathbb{p}\mathbb{p}_{MPed} = (\tilde{N}, \tilde{\mathbb{p}}) \leftarrow \text{MPed}\cdot\text{Setup}(1^\lambda)$ with $\tilde{\mathbb{p}} = (\tilde{h}, \tilde{g}_1, \dots, \tilde{g}_{4+\ell_s})$. Then, sets $\pi_{gen} \leftarrow \Pi_{gen}.\text{Prove}^{\text{H}_{gen}}(w_{gen}, x_{gen})$ for $x_{gen}$ as above and appropriate $w_{gen}$. Outputs the structured reference string srs = $(\tilde{N}, \tilde{\mathbb{p}}, \pi_{gen})$.

- $\Pi_{fis}.\text{Prove}^{\text{H}_{fis}}(crs, x, w)$: First, commits to $y$ via $C_{Grp}$. That is, samples $s \leftarrow [N \cdot 2^\lambda]$, splits $s$ into $(s_i)_i \in [0, 2^{3\lambda}]^{\ell_s}$ via $2^{3\lambda}$-ary decomposition and computes $c_N = y \cdot h_1^s, \vec{C}' = \bar{s}H' + r'\vec{G}'$ and $F' = r'H$. Then, compiles $\Sigma_{fis}$ into a proof $\pi$ via

$$ (\Omega_\Sigma, \text{st}) \leftarrow \Sigma_{\text{fis}}.\text{Init}(x_\Sigma, w_\Sigma), \\ \gamma_\Sigma \leftarrow H_\gamma(x_\Sigma, \Omega_\Sigma), \\ \tau_\Sigma \leftarrow \Sigma_{\text{fis}}.\text{Resp}(x_\Sigma, \text{st}, \gamma_\Sigma), \\ \pi_\Sigma \leftarrow (\Omega_\Sigma, \gamma_\Sigma, \tau_\Sigma), $$

for statement $x_\Sigma = (c_N, \tilde{N}, \tilde{\mathbb{p}}, \mathbb{p}\mathbb{p}'_I, \mathbb{p}\mathbb{p}'_I, c, N, h_1, h_2, h, \bar{m}, \vec{C}, F, \vec{C}', F')$ and witness $w_\Sigma = (e, a, y, r, r', \omega, (s_1, \dots, s_{\ell_s}))$, where $\omega = (e - \bar{E}) \cdot s$. Outputs $\pi = (\pi_\Sigma, c_N, \vec{C}', F')$.

- $\Pi_{fis}.\text{Verify}^{\text{H}_{fis}}(crs, x, \pi)$: On input $crs, x$, and $\pi = (\pi_\Sigma, c_N, \vec{C}', F')$, checks

$$ H_{\text{fis}}(x_{\Sigma}, \Omega_{\Sigma}) = \gamma_{\Sigma}, \\ \Sigma_{\text{fis}}.\text{Verify}(x_{\Sigma}, \Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}) = 1, $$

where $\pi_\Sigma = (\Omega_\Sigma, \gamma_\Sigma, \tau_\Sigma)$. The statement $x_\Sigma$ is defined as above. Outputs 1 iff all checks succeed.

**Theorem 11.** The NIZK $\Pi_{fis}$ is correct, subversion zero-knowledge under the DDH assumption, and adaptively knowledge sound under the sRSA assumption.

*Proof.* First, correctness follows by correctness of $\Sigma_{fis}$. (It is easy to check that $(x_\Sigma, w_\Sigma) \in \mathbb{R}_{fis}$ by design.)

Subversion ZK follows as in previous NIZKs (cf. Theorems 9 and 10) and since $C_{Grp}$ is hiding. In more detail, observe that $\pi_{gen}$ in the adversarial srs ensures that $\langle \tilde{h} \rangle = \langle \tilde{g}_i \rangle$ under soundness of $\Pi_{gen}$ with overwhelming probability. Since thus $(x_\Sigma, w_\Sigma) \in \mathbb{R}_{fis}$ in the real proof generation, the simulator simply simulates $\pi_\Sigma$ via non-abort HVZK of $\Sigma_{fis}$ and by programming $H_\gamma$ accordingly. (The latter is possible due to high min-entropy of $\Sigma_{fis}$.) Also, the simulator outputs a fresh $C_{Grp}$ commitment $(c_N, \vec{C}', F')$ to $1 \in \langle h_1 \rangle$ (instead of a commitment to $y$). This is justified by the hiding property of $C_{Grp}$. A simple hybrid argument allows to show that the above simulator suffices for subversion zero-knowledge.
Finally, we show adaptive knowledge soundness (cf. Definition 24). Roughly, this follows by forking the adversary twice to obtain three related transcripts. Then, 3 special soundness of $\Sigma_{fis}$ ensures that a witness can be recomputed. In more detail, SimCRS simply outputs crs = (srs, urs) with srs $\leftarrow$ GenCRS(1$^{\lambda}$) and urs $\leftarrow$ URS. Since crs follows the real distribution, CRS indistinguishability holds. (Note that $td = \perp$.) To define the extractor Ext with oracle access to some prover A making Q H$_{\gamma}$ queries, let us make some preparations. First, assume that

$$ \Pr[\text{crs} \leftarrow \text{SimCRS}(1^{\lambda}), (x, \pi) \leftarrow \mathcal{A}^{\text{H}_{\gamma}}(\text{crs}; \rho) : \text{Verify}^{\text{H}_{\text{fis}}}(\text{crs}, x, \pi) = 1] \geq \mu(\lambda) $$

Denote by $(x, \pi) \leftarrow \mathcal{A}^{\text{H}_\gamma}(\text{crs}; \rho)$ the statement-proof pair output by A on input (crs; $\rho$), where the oracle queries to H$_{\gamma}$ are answered via a vector $\vec{h} \in [0, C]^Q$ and H$_{\text{gen}}$ queries are answered via a vector $\vec{h}'$. Parse $x = (\text{pp}_I, N, h_1, h_2, h, \overline{m}, \vec{C}, F)$, $\pi = (\pi_\Sigma, c_N, \vec{C}', F')$ and $\pi_\Sigma = (\Omega_\Sigma, \gamma_\Sigma, \tau_\Sigma)$. Denote $x_\Sigma = (c_N, \tilde{N}, \tilde{\text{pp}}, \text{pp}_I, \text{pp}'_I, c, N, h_1, h_2, h, \overline{m}, \vec{C}, F, \vec{C}', F')$, where $(\tilde{\text{pp}}, \text{pp}'_I)$ are specified by the crs. Define by $i$ the index of the first oracle query $q_i = (x_\Sigma, \Omega_\Sigma)$ to H$_{\gamma}$ made by A. If no such query exists, then $i = \perp$. Note that if $(x, \pi)$ verifies, then except with probability $1/(C+1)$ such a query exists because H$_{\gamma}(x_\Sigma, \Omega_\Sigma) = \gamma_\Sigma$ must hold. Denote by E the event that Verify$^{\text{H}_{\text{fis}}}(\text{crs}, x, \pi) = 1$ and $i \neq \perp$. By the above discussion, we have

$$ \Pr[E] \geq \mu(\lambda) - 1/(C+1). $$

For fixed (crs, $\rho$, $\vec{h}'$), let us define a function $F_{\text{Ext}}: [0, C]^Q \mapsto [Q]$ by $F_{\text{Ext}}(\vec{h}) = i - 1$ if E occurs and $F_{\text{Ext}}(\vec{h}) = 1$ otherwise.

We are now ready to define the extractor Ext. First, Ext samples randomness $\rho$ for A and a tuple $\vec{h}_1 \in [0, C]^Q$ which corresponds to the H$_{\gamma}$ outputs to A's queries. Also, samples the H$_{\text{gen}}$ outputs $\vec{h}'$ which remain unaltered in the following. Then, Ext runs A on input (crs; $\rho$) answering the H$_{fis}$ queries via $\vec{h}_1$ and $\vec{h}'$. If E occurs, then Ext samples 2 other vectors $\vec{h}_2$ and $\vec{h}_3$ from $[0, C]$ at random conditioned on $F_{\text{Ext}}(\vec{h}_1) = F_{\text{Ext}}(\vec{h}_2) = F_{\text{Ext}}(\vec{h}_3)$. Then, Ext runs A two more times on input (crs; $\rho$) by answering the H$_{\gamma}$ queries $\vec{h}_2$ and $\vec{h}_3$ (and the H$_{\text{gen}}$ queries via $\vec{h}'$). If E occurs for all $\vec{h}_k$, $k \in [3]$, parse A's output for each run as above but indexed by $k$. By construction, we have that $(x_\Sigma, \Omega_\Sigma) := (x_{\Sigma,1}, \Omega_{\Sigma,1}) = (x_{\Sigma,2}, \Omega_{\Sigma,2}) = (x_{\Sigma,3}, \Omega_{\Sigma,3})$ $^{39}$. If the challenges $(\gamma_{\Sigma,k})_{k \in [3]}$ are distinct, then Ext applies the extractor of $\Sigma_{fis}$ to the three related transcripts $(\Omega_{\Sigma,k}, \gamma_{\Sigma,k}, \tau_{\Sigma,k})_{k \in [3]}$ for statement $x_\Sigma$. This yields a witness $w_\Sigma$ such that $(w_\Sigma, x_\Sigma) \in \tilde{\mathbb{R}}_\Sigma$. Parse $w_\Sigma = (e, a, y, r, r', \omega, (s_1, \dots, s_{\ell_s}))$. Finally, Ext outputs $w = (e, a, y, r)$. If the challenges are not distinct or E does not occur for $i \in [k]$, Ext outputs $\perp$.

It remains to show that Ext outputs a witness $w$ such that $(x, w) \in \tilde{\mathbb{R}}_{\text{fis}}$ with sufficient probability. For convenience, let us recall the definition of $\tilde{\mathbb{R}}_{\text{fis}}$ below.

$$ \tilde{\mathbb{R}}_{\text{fis}} = \{(x, w) \mid y^e \equiv h \cdot h_1^a \cdot h_2^{a+\overline{m}} \mod N, e \equiv 1 \mod 2, (e-\overline{E}, a) \in [\vec{B}T, \overline{B}T], \vec{C} = (e-\overline{E}, a)H+r\vec{G}, F = rH\}. $$

First, let us analyze the probability that Ext outputs some witness $w \neq \perp$. By lemma 4, the event E occurs for all runs of A with probability at least $\mu(\lambda)^3/Q^2$. Also, with probability $1 - 3/(C+1)$, the challenges $(\gamma_{\Sigma,k})_k$ are distinct. Thus, we have

$$ \Pr[(x_{\Sigma}, w_{\Sigma}) \in \tilde{\mathbb{R}}_{\Sigma}] \geq \mu(\lambda)^3/q^2 - 3/(C+1) = \mu(\lambda)^3/Q^2 - \text{negl}(\lambda), $$

Further, under the sRSA assumption, it holds that

$$ \Pr[(\tilde{\text{pp}}, w_{\Sigma}) \in \mathbb{R}_{C, \tilde{\ell}}(\tilde{\text{pp}}) \text{ or } (\text{pp}, w_{\Sigma}) \in \mathbb{R}_{C, \tilde{\ell}}(\text{pp})] = \text{negl}(\lambda). $$

To see this, recall that finding a witness for either of the above relations is hard under sRSA for random $\tilde{\text{pp}} \in \mathbb{Q}\mathbb{R}_{\tilde{N}}^{\ell_s+5}$ and RSA modulus $\tilde{N}$. Since $(\tilde{N}, \tilde{\text{pp}})$ is part of the srs, it is possible to embed a hard instance into srs. It is straightforward to construct appropriate adversaries on sRSA and we omit details. Thus, we have

$$ \Pr[(x_{\Sigma}, w_{\Sigma}) \in \tilde{\mathbb{R}}_{\Sigma} \wedge (\tilde{\text{pp}}, w_{\Sigma}) \notin \mathbb{R}_{C, \tilde{\ell}}(\tilde{\text{pp}}), (\text{pp}, w_{\Sigma}) \notin \mathbb{R}_{C, \tilde{\ell}}(\text{pp})] \geq \mu(\lambda)^3/Q^2 - \text{negl}(\lambda), $$

<footnote n="39">39 Observe that for fixed $\vec{h} \in [0, C]^Q$, the output of A is deterministic. Because each run, the H$_{\gamma}$ queries are answered identically until query $q_{i,k} = (x_{\Sigma,k}, \Omega_{\Sigma,k})$, the input $q_{i,k}$ to this query is identical for all $k \in [3]$.</footnote>
By definition of $\tilde{\mathbb{R}}_{\Sigma}$, if $(w_{\Sigma}, x_{\Sigma}) \in \tilde{\mathbb{R}}_{\Sigma}$ but $(\tilde{\mathbb{p}}, w_{\Sigma}) \notin \mathbb{R}_{C,\ell}(\tilde{\mathbb{p}})$ and $(\tilde{\mathbb{p}}, w_{\Sigma}) \notin \mathbb{R}_{C,\ell}(\tilde{\mathbb{p}})$, the following holds:

$$c_N^{\bar{e}+\bar{E}} \cdot h_1^{-\omega} \cdot h_1^{-s \cdot \bar{E}} \equiv h \cdot h_1^a \cdot h_2^{a+\bar{m}} \mod N, \omega = \bar{e} \cdot s, \bar{e} = 2e' + 1, e = \bar{e} + \bar{E}$$

$$\vec{C} = (\bar{e} \cdot H, a \cdot H) + r\vec{G}, F = rH$$

$$\vec{C}' = \vec{s}H' + r'\vec{G}', F' = r'H, s = \sum_{i \in [\ell_s]} s_i 2^{3\lambda(i-1)}, c_N \equiv y \cdot h_1^s \mod N,$$

$$(\bar{e}, a) \in [-\vec{B}T, \vec{B}T], (s_1, \dots, s_{\ell_s}) \in [-\vec{B}'T, \vec{B}'T]$$

It follows that $(x, w) \in \tilde{\mathbb{R}}_{\text{fis}}$. To see this, observe that all equations but $y^e \equiv h \cdot h_1^a \cdot h_2^{a+\bar{m}} \mod N$ follow immediately. The latter follows because

$$\begin{align*}
& c_N^{\bar{e}+\bar{E}} \cdot h_1^{-\omega} \cdot h_1^{-s \cdot \bar{E}} \\
& \equiv (y \cdot h_1^s)^e \cdot h_1^{-\bar{e} \cdot s} \cdot h_1^{-s \cdot \bar{E}} \\
& \equiv y^e \cdot (h_1^{e \cdot s} \cdot h_1^{-s(\bar{e} \cdot \bar{E})}) \equiv y^e \mod N.
\end{align*}$$

This concludes the proof.

*Optimizations.* Again, we omit the first flow of $\Sigma_{\text{fis}}$ (i.e., the values $\bar{\Omega}_C, \Omega_F, \bar{\Omega}_{C'}, \Omega_{F'}, \Omega_{\tilde{c}}, \Omega_q$ except $\tilde{c}$ and $\tilde{c}_q$) from the proof $\pi_{\Sigma}$. The verification equations are verified within the hash function $H_{\text{fis}}$.

*Efficiency.* We use standard RSA moduli and groups for $\lambda = 128$ bit security, i.e., $N$ and $\tilde{N}$ of size $3072$ bit. We set $L = 2^{10}$ and thus $T = 2^{\lambda+11}$. Further, we assume that $\mathbb{G}$ is of order $4\lambda+12$ (which is required for $\mathbb{C}_{\text{RInt}}$). With these parameters, we have $\ell_s = 9$. In total, a proof is of size 4.08 KB.
<table><caption>Fig. 5: Description of Σ<sub>fis</sub> with x = (c<sub>N</sub>, N̄, p̄p, pp<sub>I</sub>, pp'<sub>I</sub>, c, N, h<sub>1</sub>, h<sub>2</sub>, h, m̄, C̄, F̄, C̄', F') and w = (e, a, y, r, r', ω, (s<sub>1</sub>, ..., s<sub>ℓ<sub>s</sub></sub>)).</caption><thead><tr><th>Prover(x; w)</th><th>Verifier(x)</th></tr></thead><tbody><tr><td>1: t̃, t<sub>q</sub> ← [0, N · 2<sup>λ</sup>], μ<sub>r</sub>, μ<sub>r'</sub> ← Z<sub>p</sub>, μ<sub>t̃</sub>, μ<sub>t<sub>q</sub></sub> ← [0, CN · 2<sup>2λ</sup>]</td><td></td></tr><tr><td>2: (μ<sub>ε</sub>, μ<sub>a</sub>) ← [0, (B̄C + 1)L], μ<sub>e'</sub> ← [0, (B<sub>1</sub>C + 1)L]</td><td></td></tr><tr><td>3: μ̄<sub>s</sub> ← [0, (B̄C + 1)L]</td><td></td></tr><tr><td>4: ω ← ē · (∑<sub>i∈[ℓ<sub>s</sub>]</sub> s<sub>i</sub>2<sup>3λ(i-1)</sup>), μ<sub>ω</sub> ← [0, CB<sub>1</sub>N · 2<sup>2λ</sup>]</td><td></td></tr><tr><td>5: Ω<sub>f</sub> ← c<sub>N</sub><sup>-μ<sub>ε</sub></sup> · h<sub>1</sub><sup>μ<sub>ω</sub></sup> · h<sub>1</sub><sup>E</sup> ∑<sub>i∈[ℓ<sub>s</sub>]</sub> μ<sub>s<sub>i</sub></sub>2<sup>3λ(i-1)</sup> · h<sub>1</sub><sup>μ<sub>a</sub></sup> · h<sub>2</sub><sup>μ<sub>a</sub></sup> mod N,</td><td></td></tr><tr><td>6: Ω̄<sub>C</sub> = (μ<sub>ε</sub>, μ<sub>a</sub>)H + μ<sub>r</sub>Ḡ, Ω<sub>F</sub> ← μ<sub>r</sub>H,</td><td></td></tr><tr><td>7: Ω̄<sub>C'</sub> = (μ̄<sub>s</sub>)H + μ<sub>r'</sub>Ḡ, Ω<sub>F'</sub> ← μ<sub>r'</sub>H,</td><td></td></tr><tr><td>8: f<sub>ω,0</sub> ← -∑<sub>i∈[ℓ<sub>s</sub>]</sub> μ<sub>s<sub>i</sub></sub>μ<sub>ε</sub>2<sup>3λ(i-1)</sup>, f<sub>ω,1</sub> ← μ<sub>ω</sub> - ∑<sub>i∈[ℓ<sub>s</sub>]</sub> (μ<sub>s<sub>i</sub></sub>e + s<sub>i</sub>μ<sub>e</sub>)2<sup>3λ(i-1)</sup> + ∑<sub>i∈[ℓ<sub>s</sub>]</sub> μ<sub>s<sub>i</sub></sub>E2<sup>3λ(i-1)</sup></td><td></td></tr><tr><td>9: f<sub>e,0</sub> ← μ<sub>ε</sub>, f<sub>e,1</sub> ← -2μ<sub>e'</sub></td><td></td></tr><tr><td>10: c̄ ← h<sup>t̃</sup> · ḡ<sub>1</sub>ḡ<sub>2</sub>ḡ<sub>3</sub><sup>e'</sup> ∏<sub>i∈[ℓ<sub>s</sub>]</sub> ḡ<sub>3+i</sub><sup>s<sub>i</sub></sup> · ḡ<sub>4+ℓ<sub>s</sub></sub>, Ω<sub>c̄</sub> ← h<sup>μ̃t̃</sup> · ḡ<sub>1</sub><sup>μ̃ε</sup>ḡ<sub>2</sub><sup>μ<sub>a</sub></sup>ḡ<sub>3</sub><sup>μ<sub>e'</sub></sup> ∏<sub>i∈[ℓ<sub>s</sub>]</sub> ḡ<sub>3+i</sub><sup>s<sub>i</sub></sup> · ḡ<sub>4+ℓ<sub>s</sub></sub></td><td></td></tr><tr><td>11: c̄<sub>q</sub> ← h<sup>t<sub>q</sub></sup> · ḡ<sub>1</sub><sup>f<sub>ω,1</sub></sup> · ḡ<sub>2</sub><sup>f<sub>e,1</sub></sup>, Ω<sub>q</sub> ← h<sup>μ<sub>t<sub>q</sub></sub></sup> · ḡ<sub>1</sub><sup>f<sub>ω,0</sub></sup> · ḡ<sub>2</sub><sup>f<sub>e,0</sub></sup></td><td></td></tr><tr><td>12: γ ← [0, C]</td><td></td></tr><tr><td>13: τ<sub>r</sub> ← γr + μ<sub>r</sub>, τ<sub>r'</sub> ← γr' + μ<sub>r'</sub></td><td></td></tr><tr><td>14: τ̃<sub>t</sub> ← γt̃ + μ̃<sub>t</sub>, τ<sub>t<sub>q</sub></sub> ← γt<sub>q</sub> + μ<sub>t<sub>q</sub></sub></td><td></td></tr><tr><td>15: τ̄ε ← γε + μ<sub>ε</sub>, τ<sub>a</sub> ← γa + μ<sub>a</sub>, τ<sub>e'</sub> ← γe' + μ<sub>e'</sub></td><td></td></tr><tr><td>16: τ̄s ← γs̄ + μ̄<sub>s</sub>, τ<sub>ω</sub> ← γω + μ<sub>ω</sub></td><td></td></tr><tr><td>17: check (τ<sub>ε</sub>, τ<sub>a</sub>) ∈ [B̄C, (B̄C + 1)L]</td><td></td></tr><tr><td>18: check τ̄s ∈ [B̄'C, (B̄'C + 1)L], τ<sub>e'</sub> ∈ [B<sub>1</sub>C, (B<sub>1</sub>C + 1)L]</td><td></td></tr><tr><td>19: check (τ<sub>ε</sub>, τ<sub>a</sub>) ∈ [0, (B̄C + 1)L]</td><td></td></tr><tr><td>20: check τ̄s ∈ [0, (B̄'C + 1)L], τ<sub>e'</sub> ∈ [0, (B<sub>1</sub>C + 1)L]</td><td></td></tr><tr><td>21: check c<sub>N</sub><sup>-τ<sub>ε</sub></sup> · h<sub>1</sub><sup>τ<sub>ω</sub></sup> · h<sub>1</sub><sup>E</sup> ∑<sub>i∈[ℓ<sub>s</sub>]</sub> τ<sub>s<sub>i</sub></sub>2<sup>3λ(i-1)</sup> · h<sup>γ</sup> · h<sub>1</sub><sup>τ<sub>a</sub></sup> · h<sub>2</sub><sup>τ<sub>a</sub>+γm̄</sup> ≡ Ω<sub>f</sub> mod N</td><td></td></tr><tr><td>22: check (τ<sub>ε</sub>, τ<sub>a</sub>)H + τ<sub>r</sub>Ḡ - γḠ = Ω̄<sub>C</sub>, τ<sub>r</sub>H - γF̄ = Ω<sub>F</sub></td><td></td></tr><tr><td>23: check τ̄sH' + τ<sub>r'</sub>Ḡ' - γḠ' = Ω̄<sub>C'</sub>, τ<sub>r'</sub>H' - γF' = Ω<sub>F'</sub></td><td></td></tr><tr><td>24: check c̄<sup>-γ</sup> · h<sup>τ̃t̃</sup> · ḡ<sub>1</sub><sup>τ<sub>ε</sub></sup>ḡ<sub>2</sub><sup>τ<sub>a</sub></sup>ḡ<sub>3</sub><sup>τ<sub>e'</sub></sup> ∏<sub>i∈[ℓ<sub>s</sub>]</sub> ḡ<sub>3+i</sub><sup>s<sub>i</sub></sup> · ḡ<sub>4+ℓ<sub>s</sub></sub> ≡ Ω<sub>c̄</sub> mod N̄</td><td></td></tr><tr><td>25: f<sub>ω</sub> = γ · τ<sub>ω</sub> - (∑<sub>i∈[ℓ<sub>s</sub>]</sub> τ<sub>s<sub>i</sub></sub>2<sup>3λ(i-1)</sup>) · (τ<sub>ε</sub>), f<sub>e</sub> = γ(τ<sub>ε</sub> - (2 · τ<sub>e'</sub> + γ))</td><td></td></tr><tr><td>26: check c̄<sub>q</sub><sup>γ</sup> · Ω<sub>q</sub> ≡ h̃<sup>τ<sub>t<sub>q</sub></sub></sup> · ḡ<sub>1</sub><sup>f<sub>ω</sub></sup> · ḡ<sub>2</sub><sup>f<sub>e</sub></sup> mod N̄</td><td></td></tr></tbody></table>