# Pairing-Free Blind Signatures from Standard Assumptions in the ROM

Julia Kastner, Ky Nguyen, Michael Reichle

► To cite this version:

Julia Kastner, Ky Nguyen, Michael Reichle. Pairing-Free Blind Signatures from Standard Assumptions in the ROM. IACR CRYPTO 2024 - 44th Annual International Cryptology Conference, International Association for Cryptologic Research, Aug 2024, Santa Barbara, United States. pp.210-245, 10.1007/978-3-031-68376-3_7. hal-05029146

HAL Id: hal-05029146

https://hal.science/hal-05029146v1

Submitted on 10 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

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

Distributed under a Creative Commons Attribution 4.0 International License
Pairing-Free Blind Signatures from Standard Assumptions in
the ROM

Julia Kastner¹ ID, Ky Nguyen² ID, and Michael Reichle¹,³ ID

¹ Department of Computer Science

ETH Zürich, Switzerland

{julia.kastner,michael.reichle}@inf.ethz.ch

² DIENS, École normale supérieure, CNRS, Inria, PSL University,
Paris, France

ky.nguyen@ens.psl.eu

³ Work done partially while at ENS and Inria, Paris.

**Abstract.** Blind Signatures are a useful primitive for privacy preserving applications such as electronic payments, e-voting, anonymous credentials, and more. However, existing practical blind signature schemes based on standard assumptions require either pairings or lattices. We present the first practical construction of a round-optimal blind signature in the random oracle model based on standard assumptions without resorting to pairings or lattices. In particular, our construction is secure under the strong RSA assumption and DDH (in pairing-free groups). For our construction, we provide a NIZK-friendly signature based on strong RSA, and efficiently instantiate a variant of Fischlin's generic framework (CRYPTO'06). Our Blind Signature scheme has signatures of size 4.28 KB and communication cost 10.98 KB. On the way, we develop techniques that might be of independent interest. In particular, we provide efficient *relaxed* range-proofs for large ranges with subversion zero-knowledge and compact commitments to elements of arbitrary groups.

# 1 Introduction

In privacy-preserving authentication of data, a central question is how to authenticate without compromising one's private information. A *blind signature* solves this question by allowing a *user* to obtain signatures blindly from a *signer* while satisfying strong security guarantees. The property of *blindness* ensures that the signer cannot learn anything about the message when signing and cannot link signatures to the signing sessions of a user. This must hold even when the signer's public key is chosen *maliciously*. On the other hand, the property *one-more unforgeability* imposes that after *l* completed signing sessions, a user cannot obtain more than *l* valid signatures (*i.e.*, it cannot forge an additional signature).

Due to the strong security guarantees, blind signatures have applications in e-cash [28, 31, 74], e-voting [30, 49], or anonymous credentials [29, 21], and more. In the past few years blind signatures also play an important role in new applications such as blockchains [86, 23] or private access tokens [59, 53].

*Initial constructions.* Since their introduction by Chaum [28], many variants of blind signatures were proposed. The first proposed construction—blind RSA [28]—was proven secure under one-more RSA [13]. A similar construction secure under one-more CDH was proposed in [20]. These constructions have great efficiency—a signing interaction requires only two rounds—but require both the random oracle model (ROM) and an interactive security assumption. These strong assumptions are only *somewhat* falsifiable [71] and are tailored to the schemes itself.

*Protocols with three or more rounds.* Historically, the main alternative to the aforementioned blind signatures are based on linear identification protocols, e.g., blind Schnorr [78] or similar constructions [73, 6, 55, 64]. These blind signatures are shown to be secure under falsifiable assumptions (e.g., DLOG, RSA) for poly-logarithmically many concurrent signing sessions in the ROM. But for a polynomially large number of concurrent sessions, there are efficient attacks on such protocols [81, 16]. Since, interesting mechanisms that bind an obtained signature to a signing session were proposed, and the resulting schemes are secure in the ROM for an unbounded number of concurrent
sessions [0, 46, 62, 89] under standard assumptions. Unfortunately, the security proof also requires the generic group model (i.e., it is assumed that the adversary interacts with the group in a black-box manner). Alternatively, stateful blind signatures can be obtained for an a-priori bounded number of signatures via a cut-and-choose technique [25, 76, 67]. Generally, these Schnorr-style approaches require more than two moves, i.e., are not round-optimal.

*Round optimality.* Round optimality is a desirable efficiency measure as it removes the requirement of storing a state for each signing session and less interaction is required to obtain a signature. Another advantage of round optimal blind signatures is that sequential security implies concurrent security [68, 56]. However, it is difficult to construct round-optimal blind signatures in the plain model under standard assumptions which is supported by several impossibility results [68, 43, 75]. Katsumata et al. [65] shows that this is possible under classical and quantum standard assumptions. While this result is of theoretical interest, the construction is impractical, due to its reliance on general-purpose cryptographic primitives, namely garbled circuits. More commonly, constructions circumvent such hurdles via a trusted setup [42, 5, 70, 17, 19, 79, 3], idealized models (e.g., generic groups and/or the random oracle model [54, 4, 18, 37, 54, 66]), complexity leveraging [51, 50], or interactive assumptions [11, 69, 8, 46, 45, 52]. All such constructions require pairings or lattices <fnref n="4" /> with the exception of blind RSA [28, 13, 69, 8].

But over large networks and complex web applications, existing implementations of pairings (e.g., [83]) seem to remain a significant bottleneck. Another disadvantage of pairing-based constructions is that highly-verified standard cryptographic libraries (for instance BoringSSL and NSS) do not support pairing-friendly curves. Similarly, lattice-based constructions are still in the process of being standardized [82]. On the other hand, plain groups (without pairings) and RSA-based constructions have found widespread use in practice, e.g., in Apple's Proposal for Click Fraud Prevention in Safari [84] or SSH [85]. The only efficient round-optimal blind signature in this setting is blind RSA [28, 13] and its variants [69, 8]. The latter are covered in an RTF draft [38] and blind RSA is still a recommended nowadays [27]. Unfortunately, these schemes require both an interactive assumption (tailored to the scheme itself) and the ROM. This brings us to the following natural question:

*Can we construct efficient round optimal blind signatures in the ROM, based on standard non-interactive assumptions without resorting to pairings or lattices?* <fnref n="5" />

## 1.1 Our Contributions

In this paper we answer this question affirmatively. We construct a round optimal blind signature scheme with competitive efficiency, whose security is proven in the ROM under standard assumptions in the RSA setting and group setting (without pairings) simultaneously. Concretely, our construction is secure under the strong RSA (sRSA) assumption and DDH in ordinary prime-order groups.

Our starting point for our construction is the variant of Fischlin's framework [42] proposed in [66]. Roughly, [66] shows how to construct a blind signature via a signature scheme with an all-but-one reduction <fnref n="6" />. We instantiate the framework with a variant of the signature proposed in [41] (hereafter denoted by $S_{fis}$), and obtain blind signatures with 10.98 KB communication and signatures of size 4.28 KB. We provide a comparison to prior works in Table 1. Notably, we provide the first round-optimal blind signature without pairings or lattices. On a practical level, our signature is 2 times smaller than the previously most efficient blind signature in this regime [25]—and adds the desirable features of stateless, session-independent efficiency and round optimality. In particular, the computation cost in [25] (measured in group operations) grows linearly with the number of signing sessions opened, whereas in our construction communication and computation is $O(\lambda)$ in

<footnote n="4">⁴ The framework of Fischlin [42] yields round-optimal blind signatures with trusted setup generically, but efficient instantiations rely either on pairings [18, 4, 66] or lattices [37, 7].</footnote>

<footnote n="5">⁵ Note that due to impossibility results for round optimal blind signatures [68, 43, 75], the reliance on random oracles can likely not be removed *efficiently*.</footnote>

<footnote n="6">⁶ In the context of signatures, an all-but-one reduction allows to puncture the verification key in such a way that all-but-one message $m^*$ can be signed and given a signature on $m^*$, a hard problem can be solved. We refer to [72] for more details.</footnote>
the number of group elements. Compared to Blind RSA [28], our construction is only around 10 larger times *without* relying on a strong interactive assumption <fnref n="7" />.

We emphasize that our instantiation is non-trivial and requires several new techniques to achieve round-optimality and malicious blindness (i.e., blindness holds even if the signer's verification key was setup maliciously). Also, since the security proof of $S_{fis}$ does not fit the framework as it has no all-but-one reduction, the one-more unforgeability proof requires new insights. We refer to the technical overview in Section 2 for more details. Along the way, we provide techniques that might be of independent interest, such as:

- Easy-to-use notions for subversion zero-knowledge in the ROM (i.e., zero-knowledge holds even for a maliciously setup crs).

- Efficient relaxed range proofs for large ranges, i.e., zero-knowledge proofs that prove to a verifier that a given value $x \in [0, B]$ lies in a range $[-TB, BT]$, where $T \in \mathbb{N}$ is the slack, with subversion zero-knowledge.

- Compact commitments to elements of arbitrary cyclic groups based on DDH in an independent prime-order group. Our commitments can be opened efficiently in zero-knowledge using our relaxed range proofs.

- A zero-knowledge-friendly variant of the $S_{fis}$ signature [41]. Knowledge of a signature on a given message $m$ can be shown efficiently in zero-knowledge using our relaxed range proofs.

<table><caption>Table 1: Comparison to relevant state-of-the-art blind signatures.</caption><thead><tr><th>Reference</th><th>Sig. size</th><th>Comm. size</th><th>Setting</th><th>Assumption</th></tr></thead><tbody><tr><td>del Pino et al. [37]</td><td>100 KB</td><td>850 KB</td><td>Lattices</td><td>DSMR, MLWE, MSIS</td></tr><tr><td>Blazy et al. [18]</td><td>96 B</td><td>220 KB <sup>†</sup></td><td>Pairings</td><td>SXDH, CDH</td></tr><tr><td>Abe et al. [4]</td><td>5.5 KB</td><td>1 KB</td><td>Pairings</td><td>SXDH</td></tr><tr><td rowspan="2">Hanzlik et al. [54]<sup>††</sup></td><td>5 KB</td><td>72 KB</td><td rowspan="2">Pairings</td><td rowspan="2">CDH</td></tr><tr><td>9 KB</td><td>36 KB</td></tr><tr><td rowspan="2">Katsumata et al. [66]</td><td>447 B</td><td>303 B</td><td rowspan="2">Pairings</td><td>SXDH</td></tr><tr><td>96 B</td><td>2.2 KB</td><td>DDH, CDH</td></tr><tr><td>This work</td><td>4.28 KB</td><td>10.98 KB</td><td>RSA, Groups</td><td>sRSA, DDH</td></tr></tbody></table>

We provide signature size, communication size, the algebraic setting, and the underlying assumptions for known *round-optimal* blind signatures in the ROM secure under *non-interactive* assumptions. We stress that our work relies on assumptions in prime-order groups *without* pairing.

(†): Communication of [18] scales linearly with the message size, and is given here for 256 bit messages. (††): [54] offers tradeoffs between signature and communication sizes.

<table><thead><tr><th>Reference</th><th>Sig. size</th><th>Comm. size</th><th>#Rounds</th><th>Assumption</th></tr></thead><tbody><tr><td>Blind RSA and variants [28, 69, 8]</td><td>768 B</td><td>384 B</td><td>2</td><td>One-more RSA</td></tr><tr><td>Chairattana-Apirom et al. [25]<sup>‡</sup></td><td>8.66 KB</td><td>8.08 KB</td><td>5</td><td>RSA</td></tr><tr><td>This work</td><td>4.28 KB</td><td>10.98 KB</td><td>2</td><td>sRSA, DDH</td></tr></tbody></table>

We provide signature size, communication size, number of rounds and the underlying assumption of known blind signatures in the RSA setting.

(‡): [25] is not round-optimal and at most an a-priori fixed number of signatures can be issued, here $2^{36}$. Also, the signer is required to keep a state and communication scales logarithmically in the number sessions in size but *linearly* in computation.

## 1.2 Concurrent Works

There is an independent and concurrent work that also constructs a pairing-free blind signature in the ROM from standard assumptions [26] but for a stricter notion of pairing-free. That is, their construction relies exclusively on a prime-order group without pairing, whereas our construction relies on a prime-order group and a hidden order group (namely $QR_N$). In addition to this difference, we give a brief comparison. [26] presents three blind signatures: two constructions $BS_1$ and $BS_2$ based on an interactive assumption, and $BS_3$ based on a non-interactive assumption in the ROM.

<footnote n="7">⁷ In the pairing setting, the known tradeoffs are similar (cf. [54, 66]) compared to Blind BLS [20].</footnote>
When instantiating $BS_3$ with a group of order 256 bit, it has communication and signature size of roughly 26 KB and 10 KB, respectively. Compared to our construction, their signature size and communication is more than twice as large as ours. Their construction relies on weaker assumptions, namely CDH, but has 4 rounds of interaction. Our construction is round-optimal, but relies on DDH and sRSA. We believe it to be non-trivial to reduce the number of rounds in the protocol of $BS_3$ as it relies on a Schnorr-style proof of knowledge that is interactively computed. Similarly, we believe it to be non-trivial to remove the reliance of hidden order groups in our round-optimal construction.

## 2 Technical Overview

We provide an overview of our construction. Since our blind signature builds on the framework proposed in [66], we give a brief recap.

**The framework.** The framework of [66] is based on a signature scheme $\mathcal{S}$ with a compatible additively homomorphic commitment scheme $\text{Com}$, i.e., $\text{Com}(m; r) + \text{Com}(m'; r') = \text{Com}(m + m'; r + r')$. Here, compatible means that there exists an algorithm $\hat{\text{Sig}}$ such that the signing algorithm $\text{Sign}(\text{sk}, m)$ can be rewritten as $\hat{\text{Sig}}(\text{sk}, \text{Com}(m; r)) - \text{Com}(0; r)$. Namely, $\hat{\text{Sig}}$ computes an intermediate signature $\sigma_r = \hat{\text{Sig}}(\text{sk}, \text{Com}(m; r))$ given a commitment to the message $m$ with randomness $r$. Then, a signature can be computed by removing $\text{Com}(0; r)$ from $\sigma_r$ homomorphically $^8$. To turn this into a blind signature, a user can generate a commitment $c = \text{Com}(m; r)$, send it to the signer, and the signer can simply return $\sigma_r \leftarrow \hat{\text{Sig}}(\text{sk}, c)$. Finally, the user obtains a valid signature $\sigma \leftarrow \sigma_r - \text{Com}(0; r)$. During the signing process, the user also sends a proof $\pi$ along with $c$ that proves knowledge of $(m, r)$ such that $c = \text{Com}(m; r)$ via an online-extractable NIZK $^9$. This is required for proof of one-more unforgeability (OMUF).

The above approach hides the message $m$ during signing, and if the scheme is rerandomizable, then a user can produce a fresh signature $\sigma'$ on the message $m$ to ensure blindness. For OMUF, their proof relies on the all-but-one reduction of their underlying signature scheme—this means the reduction can set up the verification key in an alternate way that allows to sign all but one message $m^*$. Also, this property naturally yields the desired algorithm $\hat{\text{Sig}}$. Since our OMUF proof differs, we refer to [66] for more details. We finally remark that Katsumata et al. [66] instantiates this framework with Boneh-Boyen signatures and Pedersen commitments in the pairing setting.

**A compatible RSA-based commitment.** A natural approach to construct pairing-free blind signatures is to identify a signature scheme in the RSA setting which fulfills these requirements (i.e., a signature scheme with an all-but-one reduction that is rerandomizable and has a compatible commitment scheme). Unfortunately, to the best of our knowledge, all RSA-based signatures are not rerandomizable or have no all-but-one reduction. Instead, we choose a signature scheme that is almost compatible with Pedersen commitments over $\mathbb{Z}_N$, namely the signature scheme $\mathcal{S}_{\text{fis}}$ [41] based on Cramer-Shoup signatures [35]. Here, the verification key $\text{vk} = (N, h, h_1, h_2)$ consists of an RSA modulus $N$ and three QR$_N$ generators $h, h_1, h_2$. As usual, the secret key is the factorization of $N$. To sign a message $m$, the signer chooses a random prime $e$ and a random integer $a$—both from specific intervals—and computes $y$ such that

$$y^e \equiv h \cdot h_1^a \cdot h_2^{a \oplus m} \mod N \quad (1)$$

using its secret key. A valid signature is a tuple $(e, a, y)$ that satisfies Eq. (1), where $a$ and $e$ lie in the aforementioned intervals. While the scheme is not quite compatible with Pedersen commitments due to the XOR operation in the exponent, we observe that $a$ functions as a mask of $m$ within the security proof. If we replace XOR-based masking with noise flooding $^{10}$, then XOR is replaced with

<footnote>$^8$ This view is a simplified variant of [66]'s framework for the sake of exposition. We assume implicitly that $\sigma_r$ contains a component with the same range as $\text{Com}(0; r)$.</footnote>

<footnote>$^9$ Online-extractability allows the reduction to obtain $(m, r)$ in the proof of one-more unforgeability in an on-the-fly manner.</footnote>

<footnote>$^{10}$ With noise flooding, we refer to adding a mask $a$ that is exponentially larger than $m$.</footnote>
a simple addition. We adapt the scheme and modify Eq. (1) as follows:

$$y^e \equiv h \cdot h_1^a \cdot h_2^{a+m} \mod N, \qquad (2)$$

where a is chosen from an exponentially larger interval compared to before. Since in Eq. (2), m is masked statistically by a, the security proof can be adapted in a straightforward manner.

**Turning it into a blind signature.** We observe that the above scheme is almost compatible with Pedersen commitments. Let g be another QRN generator. We can sign a Pedersen commitment $c \equiv h_2^m \cdot g^r \mod N$ for some random r by first choosing an appropriate e and a, then computing y such that

$$y_r^e \equiv h \cdot h_1^a \cdot h_2^a \cdot c \mod N. \qquad (3)$$

This corresponds to the algorithm $\hat{\text{Sig}}$ but unfortunately, the value $y' = y_r \cdot g^{-r}$ does not yield a valid $S_{\text{fis}}$ signature $(e, a, y')$ since Eq. (2) is not satisfied $^{11}$. It even seems that the user cannot derive a valid signature from $y_r$ in another manner, since it requires computing $y \equiv y_r \cdot g^{-r/e \mod \Phi(N)} \mod N$. But taking e-th roots is assumed to be hard in the first place! To fix this, we can let the signer send e first, and let the user commit via $c \equiv h_2^m \cdot g^{e-r} \mod N$. Then, the computable value $y \equiv y_r \cdot g^{-r} \mod N$ satisfies Eq. (2), where $y_r$ is generated as in Eq. (3) as before. Then, as in [66], the user proves with a proof $\pi_{\text{ped}}$ that she committed to message m with randomness $e \cdot r$ to the signer via an online-extractable NIZK $\Pi_{\text{ped}}$. Since the $S_{\text{fis}}$ signatures are not rerandomizable, to present a signature, the user generates a proof $\pi_{\text{fis}}$ via an additional NIZK $\Pi_{\text{fis}}$ that proves that it knows a $S_{\text{fis}}$ signature on message m (instead of presenting $(e, a, y)$ directly).

**Making it round optimal.** Unfortunately, the above construction requires an additional round of communication to send e. Note that the user cannot generate e itself, as the reduction for $S_{\text{fis}}$ needs to be able to choose the primes e used in signatures. Indeed, it is required in the security proof that a fresh prime e and mask a are picked for each fresh message m to be signed. A natural idea is to let the user generate it via a hash function $H_P$ mapping into primes (of desired range).

As the signer also needs to derive the same prime e (i.e. see the input of $H_P$), we need to make sure that the message m is hidden by the input to $H_P$. In particular, we cannot simply derive $e = H_P(m)$. Another idea would be to derive $e = H_P(c)$ as the commitment c is already hiding the message. However, the user needs to know e already to set up c, so there is a cyclic dependency.

Therefore, we require that the user commits to m as well as the randomness r for generating c using an integer commitment $c_Z$ $^{12}$ which can then be hashed to derive e. Since $c_Z$ fixes c implicitly, this ensures that for each fresh commitment c, we use a fresh e. Under binding of $C_Z$, this implies that for each distinct message m, a fresh e is picked as desired. For technical reasons, we also need that if e is reused, e.g., if the same commitment is sent twice, the signer reuses the same mask a. This can be guaranteed by deriving a from a pseudorandom function PRF via $a \leftarrow \text{PRF}(c \parallel c_Z)^{13}$.

In summary, the user commits to $(m, r)$ in $c_Z$, computes $e \leftarrow H_{pp}(c_Z)$ and sets $c \equiv h_2^m \cdot g^{r \cdot e} \mod N$. Then, the user proves in $\pi_{\text{ped}}$ generated via a NIZK $\Pi_{\text{ped}}$ that the commitment c is constructed based on the values committed in $c_Z$, and sends $(c, c_Z, \pi_{\text{ped}})$ to the signer. The signer verifies $\pi_{\text{ped}}$, sets $e \leftarrow H_{pp}(c_Z)$ and $a \leftarrow \text{PRF}(c \parallel c_Z)$, then computes $y_r$ as in Eq. (3). Finally, the user sets $y \leftarrow y_r \cdot g^{-r}$ and obtains a valid $S_{\text{fis}}$ signature $(e, a, y)$ for m. The blind signature is $\pi_{\text{fis}}$ generated via $\Pi_{\text{fis}}$ as before.

**Proving one-more unforgeability.** While the unforgeability reduction of $S_{\text{fis}}$ has no all-but-one flavor, we can show one-more unforgeability for our blind signature with the above modifications if the NIZK $\Pi_{\text{fis}}$ is adaptively knowledge sound $^{14}$. We stress that we cannot reduce to unforgeability

<footnote>$^{11}$ Recall that this property is required for the commitment to be compatible.</footnote>

<footnote>$^{12}$ An integer commitment allows to commit to (vectors) of integers, i.e., has message space $Z^n$, and knowledge of an opening can be proven in zero-knowledge. Here, that means that $(m, r)$ is fixed over $Z^2$. For our construction, we can slightly relax this requirement if we hash m first, but we omit details here.</footnote>

<footnote>$^{13}$ Later, we implement this PRF with a random oracle.</footnote>

<footnote>$^{14}$ That is, there is an extractor that can extract a witness via black-box access to the prover, e.g., via rewinding.</footnote>
the $S_{\text{fis}}$ signature scheme directly, as the adversary obtains the prime $e$ for the signature before the reduction knows the message $m$ to be signed.

Instead, analogous to $S_{\text{fis}}$, the reduction for one-more unforgeability sets up the verification key vk in an alternative way so that it can sign without knowing the factorization of $N$. This involves guessing the “format” of the forgery generated by the adversary $\mathcal{A}$.

To sign a commitment $c$, the reduction extracts $(m, r)$ on-the-fly from the proof $\pi_{\text{ped}}$, and uses the alternatively set up key to sign $m$. It then reapplies the user's blinding. When the adversary outputs its forgeries, the reduction identifies a signature $\pi_{\text{fis}}$ on a message $m$ that it never signed$^{15}$, and then extracts a valid signature $(e, a, y)$ from $\pi_{\text{fis}}$.

Since the final extraction is not performed in a on-the-fly manner, there is a subtlety. For example, if the extractor rewinds the adversary to extract a proof, then the extracted witness might depend on the guess we made during the vk setup, rendering the forgery useless for our reduction. A similar issue was observed, e.g., in [6, 62], since witness indistinguishability is not necessarily preserved when rewinding. To solve this issue, we let the user commit to the signature parts $(e, a)$ in $c_I$ with a perfectly binding integer commitment $C_{\text{RInt}}$$^{16}$. Then, the extracted values $(e, a)$ are fixed during the initial run when our guess is still hidden. Even if our guess is revealed during extraction, the extractor still succeeds in finding a valid signature with fixed $(e, a)$. Since our guess depends only on these values, we can conclude that we guess correctly with sufficient probability which allows to solve sRSA with this modification.

**Making it maliciously blind.** An observant reader might realize that our scheme is not blind yet. Concretely, there are two types of problems: (a) we need to embed the crs into the vk, i.e. the crs is chosen by the signer and (b) Pedersen commitments are not hiding over $Z_N^*$. We show how we deal with both problems below.

(a) *Subversion Zero-knowledge.* Since the signer can choose vk maliciously, we need to ensure that zero-knowledge holds for arbitrary crs in vk. As in [48], we require that the NIZKs $\Pi_{\text{ped}}$ and $\Pi_{\text{fis}}$ are subversion zero-knowledge, i.e., zero-knowledge holds even for a malicious setup [12]. Unfortunately, this notion is difficult to instantiate in our setting. To the best of our knowledge, all instantiations of subversion zero-knowledge NIZKs [12, 44] require strong knowledge assumptions (which we wish to avoid). Instead, we give a simplified definition which yields similar guarantees in the ROM. Roughly, we split the $crs = (urs, srs)$ into a uniform part $urs \in \{0, 1\}^\ell$ of length $\ell$ and structured part $srs \in SRS$. In our notion, we ask that (a) membership in $SRS$ is testable efficiently and (b) zero-knowledge holds with respect to $crs = (urs, srs)$ for some random $urs \leftarrow \{0, 1\}^\ell$ and any malicious $srs \in SRS$. Our notion can be instantiated under standard assumptions (e.g., DDH in pairing-free groups) because in the security proof, we can embed trapdoors into the uniform part (which is output by a random oracle). More details on our instantiations are given below.

(b) *Subgroup arguments over $Z_N^*$. Pedersen commitments over $Z_N^*$ are not hiding for malicious modulus $N$: if $\langle g \rangle$ is a proper subset of $\langle h_2 \rangle$, there is a concrete attack on blindness. Thus, we let the signer prove that $\langle g \rangle = \langle h_2 \rangle$ with a NIZK with subversion soundness [12] (i.e., soundness holds even for malicious crs). We embed this proof into the verification key to avoid the trivial attack. We also need to ensure that $C_{\text{RInt}}$ and $C_Z$ are hiding. For both, we simply ask that public parameters are uniform (and sample them via a random oracle). There remain two more subtle problems.

(b.1) Recall that the user sets $c = h_2^m \cdot g^{r \cdot e} \bmod N$, so even if $\langle h_2 \rangle = \langle g \rangle$, we might have $\langle g^e \rangle \subsetneq \langle h_2 \rangle$. Fortunately, we can show that if $\langle h_2 \rangle = \langle g \rangle$, then $\langle g^e \rangle = \langle h_2 \rangle$ with overwhelming probability over the choice of a random prime $e$ for arbitrary modulus $N$.

(b.2) The signer sends $y_r$ to the user which again, might not be in the same subgroup. If the signature $\pi_{\text{fis}}$ reveals the subgroup of $y_r$, blindness is broken. But conditioned on Eq. (3), we can show that $y_r \in \langle g \rangle$ if $\{h, h_1, h_2\} \subseteq \langle g \rangle$ and $c \in \langle g \rangle$. We let the former be proven by the signer in vk. If we let the user check that Eq. (3) holds, then the latter can be shown to hold with overwhelming probability over the choice of $e$.

<footnote>$^{15}$ Since we sign at most $\ell$ messages but there are $\ell + 1$ forgeries on distinct messages, such a signature exists.</footnote>

<footnote>$^{16}$ Again, we can relax the commitment scheme, i.e., we do not require that $C_{\text{RInt}}$ is a full-fledged integer commitment. We elaborate later.</footnote>
**Instantiation.** There are several challenges when instantiating the NIZKs required for our blind signature. While it is somewhat straightforward to obtain an instantiation with generic techniques, our goal is to keep the instantiation as efficient as possible. We give a brief overview of the challenges and our solutions.

*Online-extraction and integer commitments.* Recall that we require an integer commitment scheme $C_Z$ to commit to $(m, r) \in \mathbb{Z}^2$ in combination with an efficient online-extractable NIZK for the statement

$$c_Z = C_Z \cdot \text{Commit}(m, r; r_z) \wedge c \equiv h_2^m \cdot g^{r \cdot e} \mod N. \quad (4)$$

For online-extraction, we use the approach of [66] (cf. Section 6). Let $\mathbb{G}$ be a pairing-free group of prime order $p$ with generators $G, H$. The values $(m, r)$ are decomposed into $(e_i)_i = ((m_i)_i, (r_i)_i)$ via $B$-ary decomposition (e.g., $B = 2^{64}$), committed in ElGamal commitments $E_i = e_i G + s_i H$ for $s \leftarrow \mathbb{Z}_p$, and a range proof ensures that $e_i \in [0, B - 1]$ (e.g., Bulletproofs [22]). We then interpret $(E_i)_i$ as a *bounded* integer commitment $c_Z$, i.e., the committed values must lie in the limited range $[0, B - 1]$. This notion suffices for our construction. While we follow the template of [66], our instantiation is considerably more complicated since we need to show a statement over two algebraic structures: prime order groups and $\mathbb{Z}_N^*$. For this, we employ a structured srs to argue over the integers with techniques from [32]. We refer to Appendix E for more details.

**Proof for $S_{\text{fis}}$ signatures.** To derive a blind signature, we need a perfectly binding commitment $C_{\text{RInt}}$ and a NIZK $\Pi_{\text{fis}}$ for the relation in Eq. (2) and simultaneously:

$$c_I = C_{\text{RInt}} \cdot \text{Commit}(e, a, r_I) \wedge a \in [0, 2^{3\lambda} - 1] \wedge e \in [2^{3\lambda}, 2^{3\lambda+1}] \cap \mathbb{Z}_{\text{odd}}.$$

Note that these are the specific ranges for $S_{\text{fis}}$ verification. While it is fine to employ range proofs during the (one-time) signing interaction, it is undesirable to include a range proof for presenting the signature (as the verification overhead is noticeable for such large ranges).

Instead, we relax the range requirements in such a way that the unforgeability proof of $S_{\text{fis}}$ still goes through, i.e., we allow that $a$ and $e$ lie in larger (but distinct) intervals for verification. Then, we construct very efficient *relaxed* range proofs with subversion zero-knowledge for $C_{\text{RInt}}$ consisting of ElGamal commitments over a prime-order $\mathbb{G}$ (for perfect binding). Roughly, the range proof is a simple $\Sigma$-protocol to open ElGamal in zero-knowledge, where we also add range checks for the messages sent in third flow, compiled with Fiat-Shamir. In addition, we add a fresh RSA modulus $\tilde{N}$ to the crs and commit to $a$ and $e$ in a commitment over $\mathbb{Z}_{\tilde{N}}^*$ (similar to [32]). This technique guarantees that extracted values are short integers (but within a larger range). The overhead over simply opening the ElGamal commitment in zero-knowledge—which we need anyway to instantiate the NIZK—is just 784 Byte for a modulus of size 3072 bits. For comparison, a Bulletproof for the above ranges requires 932 Byte [22]. Our relaxed range proofs are smaller and allow seamless integration into more complex $\Sigma$-protocols.

To construct $\Pi_{\text{fis}}$, we combine our relaxed range proofs for $C_{\text{RInt}}$ with standard commit-then-prove $\Sigma$-protocol techniques to show the remaining equations. For this, we require commitments over $\mathbb{Z}_N^*$ for potentially malicious $N$ to commit to $y$. Using the above techniques, we construct such commitments and provide efficient openings in zero-knowledge. Roughly, such a commitment is of the form $y \cdot g^s$ for $s \in [N \cdot 2^{\lambda}]$ with $y \in \langle g \rangle$, in conjunction with a $C_{\text{RInt}}$ commitment to fix $s$ over the integers. Especially for this purpose our relaxed range proofs shine, since $s$ lies in a large interval. (For such ranges, e.g., Bulletproofs requires 1.6 seconds for proof generation and almost 5 ms for verification.) We generalize the construction for arbitrary untrusted groups.

The remaining NIZKs are straightforward to instantiate. In total, we obtain blind signatures with 10.98 KB communication of size 4.28 KB.

**Alternative View.** Instead of viewing our construction as an instantiation of the Fischlin-style framework of [66] without pairings, we can view it as a maliciously-secure and optimized instantiation the construction sketched in [24]. In particular, [24] presents a blinded interactive signing protocol for sRSA-based signatures. Our instantiation of the underlying signature is more efficient, and the
construction in [24, Figure 1] does not seem to yield maliciously-secure blind signatures<fnref n="17" />. We provide techniques to achieve OMUF and malicious blindness simultaneously and efficiently, while preserving round optimality.

### 3 Preliminaries

**Notations.** We denote the security parameter by $\lambda$. A polynomial time (PT) algorithm $\mathcal{A}$ runs in time polynomial in the (implicit) security parameter $\lambda$. We denote “probabilistic polynomial time” by PPT. We write $\text{Time}(\mathcal{A})$ for the runtime of $\mathcal{A}$. A function $f(\lambda)$ is negligible in $\lambda$ if it is $O(\lambda^{-c})$ for every $c \in \mathbb{N}$. We write $f = \text{negl}(\lambda)$ for short. Similarly, we write $f = \text{poly}(\lambda)$ if $f(\lambda)$ is a polynomial with variable $\lambda$. If $D$ is a probability distribution, $x \leftarrow D$ means that $x$ is sampled from $D$ and if $S$ is a set, $x \leftarrow S$ means that $x$ is sampled uniformly and independently at random from $S$. We also write $|S|$ for the cardinality of set $S$. Further, we write $D_0 \stackrel{s}{\approx} D_1$ for distributions $D_0, D_1$, if for all PPT adversaries $\mathcal{A}$, we have $|\text{Pr}[x_0 \leftarrow D_0 : \mathcal{A}(1^{\lambda}, x_0) = 1]| - \text{Pr}[x_1 \leftarrow D_1 : \mathcal{A}(1^{\lambda}, x_1) = 1]| = \text{negl}(\lambda)$. Similarly, we write $D_0 \stackrel{s}{\approx} D_1$ if the above holds even for unbounded adversaries. For some PPT algorithm $\mathcal{A}$, we write $\mathcal{A}^\circ$ if $\mathcal{A}$ has oracle access to the oracle $\mathcal{O}$. If $\mathcal{A}$ performs some check, and the check fails, we assume that $\mathcal{A}$ outputs $\perp$ immediately. Generally, we assume that adversaries are implicitly stateful. We denote with $[n]$ the set $\{1, \dots, n\}$ for $n \in \mathbb{N}$. We write $\mathbb{P}$ for the set of primes and $\mathbb{P}_I$ for the set of primes in the interval $I$. For some odd prime $p$, we use the representatives $\{-\frac{p-1}{2}, \dots, \frac{p-1}{2}\}$ for $\mathbb{Z}_p$. For a group $\mathbb{G}$ we write $\text{ord}(\mathbb{G})$ to denote the order of $\mathbb{G}$ and unless stated otherwise we write $\mathbb{G}$ with additive notation. For a group element $g$ we write $\text{ord}(g)$ to denote the order of the group element. We denote by $\text{QR}_N = \{a \in \mathbb{Z}_N^* : \exists b \in \mathbb{Z}_N^*, b^2 \equiv a \bmod N\}$ the quadratic residues $\bmod N$. For some $N \in \mathbb{N}$, the group $\text{QR}_N$ is a cyclic subgroup of $\mathbb{Z}_N^*$ and we denote by $\text{Gen}(\text{QR}_N)$ the set of generators of $\text{QR}_N$. Some properties of $\text{QR}_N$ are recalled in lemma 3 in Appendix A.

**Probability.** Let $V, L \in \mathbb{N}$. We define uniform rejection sampling for the interval $[V, (V+1)L]$ with masking overhead $L$ as in [32]. Let $v \in [0, V]$. To mask $v$ additively with a mask $\mu$ via rejection sampling, perform the following steps.

1. Draw a random mask $\mu \leftarrow [0, (V+1)L]$.

2. Abort if $v + \mu \notin [V, (V+1)L]$.

3. Output $w = v + \mu$.

The value $w$ is uniform over $[V, (V+1)L]$ conditioned on no abort and the abort probability is at most $1/L^{18}$. We use a version of the Forking Lemma from [2, Lemma 1] that fits our usage of it. The lemma was first introduced by Pointcheval and Stern [77] then generalized in [14, 2]. The formal statement can be found in Appendix A.2.

**Hardness Assumptions.** We use the following assumptions in this paper. Let $\text{GenG}$ be a PPT algorithm that on input $1^{\lambda}$ and prime order $p$, outputs (a description of) a group $\mathbb{G} \leftarrow \text{GenG}(1^{\lambda})$ of order $p$. We generally use additive notations for prime order groups and capital letters for elements. Also, we assume that given the description, group operations and membership tests are efficient. We write $g \leftarrow \mathbb{G}$ for drawing elements from some group $\mathbb{G}$ at random. In the following, we assume that prime order groups are setup with $\text{GenG}$ implicitly.

Let $\text{GenRSA}$ be a PPT algorithm that on input $1^{\lambda}$ outputs $(N, P, Q) \leftarrow \text{GenRSA}(1^{\lambda})$ such that $N = P \cdot Q$ with $P, Q \in \mathbb{P}$, where $P = 2P' + 1$ and $Q = 2Q' + 1$ are strong primes (i.e., $P', Q'$ are also primes). We assume that $P', Q' > 2^{\lambda+1}$.

First of all, the $(D, \ell)$-relaxed DLOG assumption with regards to $\vec{g}$, where $\vec{g} = (g_0, \dots, g_\ell) \in \text{QR}_N^{\ell+1}$, assumes that for any PPT adversary, given $(N, g_0, \dots, g_\ell)$ it is only with negligible probability

<footnote n="17">17 For example, observe that $C_x$ is not hiding if $N$ and $(a, b)$ are set up maliciously. In particular, there is an attack if $a$ and $b$ are chosen in different subgroups. Proving that $C_x$ is hiding requires a computational assumption over $\text{QR}_N$, so it is limited (at most) to honest signer blindness.</footnote>

<footnote n="18">18 When $v=0$, the number of “bad” $\mu \in [0, (V+1)L]$ causing abort is $\#\{[0, V-1]\} = V$. For a fixed $0 < v \in (0, V]$, the number of “bad” $\mu$ causing abort is $\#\{[0, V-1-v]\} + \#\{[(V+1)L-v+1, (V+1)L]\} = V$. In both cases the abort probability over choices of $\mu$ is $V/((V+1)L+1) \le 1/L$.</footnote>
to output $(c, d, x_0, \dots, x_\ell)$ satisfying $c^d = \prod_{i=0}^\ell g_i^{x_i} \wedge \exists i: \frac{x_i}{d} \notin \mathbb{Z} \wedge d \in [0, D] \wedge x_i \in \mathbb{Z}$. The $(D, \ell)$-relaxed DLOG assumption holds under the strong RSA assumption for all $D \le 2^{\lambda+1}$. Next, the Decisional Diffie-Hellman (DDH) assumption in a cyclic group $G$ assumes that for all PPT adversary it is only with negligible probability that the adversary can distinguish $(aG, bG, abG)$ from $(aG, bG, cG)$ where $G \leftarrow G$ and $a, b, c \leftarrow \text{ord}(G)$. Finally, the strong RSA (sRSA) assumes that it is only with negligible probability for any PPT adversary to output $(e, z)$ such that $z^e \equiv y \bmod N$.

**Explaining Random Group Elements as Random Strings.** For our framework, we require commitments with uniform public parameters $pp$. For readability, we allow $pp$ (and also uniform random strings of NIZKs) to contain (uniform) group elements $g$ of prime-order groups $G$ with known order $p$. This is without loss of generality because with *explainable sampling*, we can explain $g \leftarrow G$ as a random bitstring. We refer to, e.g., [66, Appendix B] for more details.

## 3.1 Cryptographic Primitives

**Commitment Scheme.** A *commitment scheme* is a tuple of PPT algorithms $C = (\text{C.setup}, \text{C.commit}, \text{C.commit})$ such that

- $\text{C.setup}(1^{\lambda})$: generates the public parameters $pp$,

- $\text{C.commit}(pp, m)$: given the public parameters $pp$, message $m \in C_{\text{msg}}$, computes a commitment $c \in C_{\text{com}}$ with opening randomness $d$, and outputs the pair $(c, d)$,

- $\text{Verify}(pp, c, m, d)$: given the public parameters $pp$, message $m \in C_{\text{msg}}$, and opening randomness $d$, outputs a bit $b \in \{0, 1\}$ which depends on the validity of the opening $(m, d)$ with respect to the commitment $c$.

Here, $C_{\text{msg}}$, $C_{\text{rnd}}$, $C_{\text{com}}$, are message, randomness, and commitment spaces, respectively. If the public parameters are uniform or explainable (i.e., Setup outputs some $pp \leftarrow \{0, 1\}^\ell$ for $\ell \in \mathbb{N}$) we omit Setup without loss of generality.

We require the correctness, hiding and binding properties for a commitment scheme. A commitment schemes is *correct*, if honest commitments $(c, d) \leftarrow \text{Commit}(pp, m; r)$ always verify, i.e. it holds that $\text{Verify}(pp, c, m, d) = 1$ where $pp$ are the public parameters. It is *hiding* if it is hard to decide whether an unopened commitment $c$ commits to message $m_0$ or $m_1$, and it is *binding* if it is hard to open commitments $c$ to distinct messages. We can have *computational, statistical, perfect* variants for hiding and binding properties. The formal definitions can be found in Appendix A.5.

**(Bounded) Integer Commitments.** We refer to a commitment scheme with message space $[A, B] \subseteq \mathbb{N}$ as a (bounded) integer commitment scheme. We often omit the term bounded if the message space is clear by context.

**ElGamal commitments.** We recall ElGamal (EG) over a group $G$ of prime order $p$ with message space $\mathbb{Z}_p$ [39]. We use additive notation for prime order groups.

- EG.GenPP(1$^{\lambda}$): set $(G, H) \leftarrow G$ and output $pp = (G, H)$.

- EG Committed $(pp, m)$: sample $r \leftarrow \mathbb{Z}_p$ and set $c = (mG + rH, rG)$, and output $(c, r)$.

- EG.Verify(pp, c, m, r): check if $c = (mG + rH, rG)$.

Note that the public parameters are uniform and we can sample them via a random oracle to avoid trusted setup. EG commitments are correct, hiding under DDH and perfectly binding.

**Remark 1.** If in verification of EG, we check that $m \in [0, M]$ for $M < p$, then $m$ is fixed over the integers and we can interpret the commitment as an integer commitment with message space $[0, M] \subseteq \mathbb{N}$.
**Pedersen Commitments in QRN.** We recall Pedersen multi-commitments (MPed) over QRN with message space $Z^\ell$ for some $\ell \in \mathbb{N}$ (cf. [34]).

- MPed.GenPP(1^\lambda): set $(N, P, Q) \leftarrow \text{GenRSA}(1^\lambda)$ and sample $\ell$ random generators $g_i$ of QRN, and output $pp = (N, h, g_1, \dots, g_\ell)$. Note that with $(P, Q)$, we can check whether $g_i$ generates QRN.

- MPed-commit(pp, $\vec{m}$): sample $r \leftarrow [0, N \cdot 2^\lambda]$, set $c \leftarrow h^r \prod_{i=1}^\ell g_i^{m_i} \bmod N$, and output $(c, r)$.

- MPed.Verify(pp, $c, \vec{m}, r$): check if $c = \pm h^r \prod_{i=1}^\ell g_i^{m_i} \bmod N$.

MPed commitments are correct, statistically hiding and binding under the factoring assumption (which is implied by sRSA). Throughout this work, we use MPed commitments in QRN to enforce in security proofs that values extracted from NIZKs are integers via lemma 6.

**Signature Scheme.** A signature scheme is a tuple of PPT algorithms $S = (\text{KeyGen}, \text{Sign}, \text{Verify})$ such that

- $\text{KeyGen}(1^\lambda)$: generates a verification key vk and a signing key sk,

- $\text{Sign}(\text{sk}, m)$: given a signing key sk and a message $m \in S_{\text{msg}}$, deterministically outputs a signature $\sigma$,

- $\text{Verify}(\text{vk}, m, \sigma)$: given a verification key pk and a signature $\sigma$ on message $m$, deterministically outputs a bit $b \in \{0, 1\}$.

Here, $S_{\text{msg}}$ is the message space. We define the standard notion of correctness and euf-cma security. Correctness requires that any honestly generated signature $\sigma \leftarrow \text{Sign}(\text{sk}, m)$ verifies, i.e. $\text{Verify}(\text{vk}, m, \sigma) = 1$. The euf-cma security imposes that even with oracle accesses to $\text{Sign}(\text{sk}, \cdot)$, no PPT adversary will be able to forge a valid signature $\sigma$ on a message $m$ that is not queried to $\text{Sign}(\text{sk}, \cdot)$.

**Blind Signature Scheme.** A (two-move) blind signature scheme is a tuple of PPT algorithms $\text{BS} = (\text{KeyGen}, \text{Sign}, \text{Verify})$ such that

**Definition 1 (Blind Signature).** A (two-move) blind signature scheme is a tuple of PPT algorithms $\text{BS} = (\text{KeyGen}, \text{Sign}, \text{Verify})$ such that

- $\text{KG}(1^\lambda)$: generates the verification key `bvk` and signing key `bsk`,

- Sign is split into the following algorithms:

• User(bvk, m): given verification key `bvk` and message $m \in \text{BS}_{\text{msg}}$, outputs a first message $\rho_1$ and a state `st`,

• Signer(bsk, $\rho_1$): given signing key `bsk` and first message $\rho_1$, outputs a second message $\rho_2$,

• Derive(st, $\rho_2$): given state `st` and second message $\rho_2$, outputs a signature $\sigma$

- Verify(bvk, m, $\sigma$): given verification key `bvk` and signature $\sigma$ on message $m \in \text{BS}_{\text{msg}}$, outputs a bit $b \in \{0, 1\}$.

Here, $\text{BS}_{\text{msg}}$ is the message spaces.

We consider the standard security notions for blind signatures [61]. Below, we define correctness, blindness under malicious keys, and one-more unforgeability of a blind signature scheme. Moreover, we will omit the state for better readability on occasion.

**Definition 2 (Correctness).** A blind signature scheme is correct, if for all messages $m \in \text{BS}_{\text{msg}}$, (bvk, bsk) $\leftarrow \text{KG}(1^\lambda)$, $(\rho_1, \text{st}) \leftarrow \text{User}(\text{bvk}, m)$, $\rho_2 \leftarrow \text{Signer}(\text{bsk}, \rho_1)$, $\sigma \leftarrow \text{Derive}(\text{st}, \rho_2)$, it holds that $\text{Verify}(\text{bvk}, m, \sigma) = 1$.

**Definition 3 (Blindness Under Malicious Keys).** A blind signature scheme is blind under malicious keys if for any PPT adversary $\mathcal{A}$, we have

$$ \text{Adv}_{\mathcal{A}}^{\text{blind}}(\lambda) = \left| \Pr \left[ \begin{array}{l} (\text{bvk}, m_0, m_1) \leftarrow \mathcal{A}(1^{\lambda}), \text{coin} \leftarrow \{0, 1\}, \\ (\rho_{1,b}, \text{st}_b) \leftarrow \text{User}(\text{bvk}, m_b) \text{ for } b \in \{0, 1\}, \\ (\rho_{2,\text{coin}}, \rho_{2,1-\text{coin}}) \leftarrow \mathcal{A}(\rho_{1,\text{coin}}, \rho_{1,1-\text{coin}}), \quad : \text{coin} = \mathcal{A}(\sigma_0, \sigma_1) \\ \sigma_b \leftarrow \text{Derive}(\text{st}_b, \rho_{2,b}) \text{ for } b \in \{0, 1\}, \\ \text{if } \exists b \text{ s.t. } \text{Verify}(\text{bvk}, m_b, \sigma_b) = 0: \\ \quad \text{then } \sigma_0 = \sigma_1 = \perp, \end{array} \right] - \frac{1}{2} \right| = \text{negl}(\lambda). $$
**Definition 4 (One-more Unforgeability).** A blind signature scheme is one-more unforgeable if for any $Q = \text{poly}(\lambda)$ and PPT adversary $\mathcal{A}$ that makes at most $Q$ signing queries, we have

$$ \text{Adv}_{\mathcal{A}}^{\text{omuf}}(\lambda) = \text{Pr} \left[ \begin{array}{l} \forall i \neq j \in [Q+1]: \\ \quad (\text{bvk}, \text{bsk}) \leftarrow \text{KG}(1^{\lambda}) \\ \quad \{(m_i, \sigma_i)\}_{i \in [Q+1]} \leftarrow \mathcal{A}^{\text{Signer}(\text{bsk}, \cdot)}(\text{bvk}) : \\ \quad \quad m_i \neq m_j \\ \quad \quad \wedge \\ \quad \quad \text{Verify}(\text{bvk}, m_i, \sigma_i) = 1 \end{array} \right] = \text{negl}(\lambda). $$

**$\Sigma$-Protocol.** Let $R$ be an NP relation with statements $x$ and witnesses $w$. We denote by $\mathcal{L}_R = \{x \mid \exists w \text{ s.t. } (x, w) \in R\}$ the language induced by $R$. A $\Sigma$-protocol for an NP relation $R$ for language $\mathcal{L}_R$ with challenge space $CH$ is a tuple of PPT algorithms $\Sigma = (\text{Init}, \text{Chall}, \text{Resp}, \text{Verify})$ such that

- $\text{Init}(x, w)$: given a statement $x \in \mathcal{L}_R$, and a witness $w$ such that $(x, w) \in R$, outputs a first flow message (i.e., commitment) $\Omega$ and a state st, where we assume st includes $x, w$,

- $\text{Chall}()$: samples a challenge $\gamma \leftarrow CH$ (without taking any input),

- $\text{Resp}(\text{st}, \gamma)$: given a state st and a challenge $\gamma \in CH$, outputs a third flow message (i.e., response) $\tau$,

- $\text{Verify}(x, \Omega, \gamma, \tau)$: given a statement $x \in \mathcal{L}_R$, a commitment $\Omega$, a challenge $\gamma \in CH$, and a response $\tau$, outputs a bit $b \in \{0, 1\}$.

We recall the standard notions of correctness, high-min entropy, (non-abort) honest-verifier zero-knowledge, and k-special soundness. A $\Sigma$-protocol is correct, if for all $(x, w) \in R$, if for any honestly generated transcripts $(\Omega, \gamma, \tau)$, the verifier accepts, i.e. Verify$(x, \Omega, \gamma, \tau) = 1$. It has high min-entropy if for all $(x, w) \in R$, it is statistically hard to predict a honestly generated first flow $\Omega$. It is honest-verifier zero-knowledge (HVZK), if there exists a PPT zero-knowledge simulator Sim such that the distributions of Sim$(x, \gamma)$ and a honestly generated non-aborting transcript with Init initialized with $(x, w)$ are statistically indistinguishable for any $x \in \mathcal{L}_R$, and $\gamma \in CH$, where the honest execution is conditioned on $\gamma$ being used as the challenge. Finally, it is k-special sound, if there exists a deterministic PT extractor Ext such that given $k$ valid transcripts $\{(\Omega, \gamma_i, \tau_i)\}_{i \in [k]}$ for statement $x$ with pairwise distinct challenges $(\gamma_i)_{i}$, outputs a witness $w$ such that $(x, w) \in R$.

**Non-Interactive Zero Knowledge.** All formal definitions of the following can be found in Appendix A.8. Let $URS = \{0, 1\}^\ell$ be a set of uniform random strings for some $\ell \in \mathbb{N}$ and $SRS$ be some set of structured random strings with efficient membership test $^{19}$. A NIZK for a relation $R$ with common reference string space $CRS = SRS \times URS$ is a tuple of PPT algorithms ($\text{GenSRS}, \text{Prove}^H, \text{Verify}^H$), where the latter two are oracle-calling, such that:

- $\text{GenSRS}(1^{\lambda})$: outputs a structured reference string $\text{srs} \in SRS$,

- $\text{Prove}^H(\text{crs}, x, w)$: receives a $\text{crs} = (\text{srs}, \text{urs}) \in CRS$, a statement $x$ and a witness $w$, and outputs a proof $\pi$,

- $\text{Verify}^H(\text{crs}, x, \pi)$: receives a $\text{crs} = (\text{srs}, \text{urs}) \in CRS$, a statement $x$ and a proof $\pi$, and outputs a bit $b \in \{0, 1\}$.

We recall that $\mathcal{L}_R = \{x \mid \exists w : (x, w) \in R\}$ denotes the language induced by $R$. If there is no $\text{crs}$ needed, i.e. $CRS = \emptyset$, we then omit $\text{crs}$ as an input to Prove and Verify. A NIZK is correct if for any $\text{crs} = (\text{srs}, \text{urs})$ with $\text{srs} \leftarrow \text{GenSRS}(1^{\lambda})$ and $\text{urs} \leftarrow URS$, $(x, w) \in R$, and $\pi \leftarrow \text{Prove}^H(\text{crs}, x, w)$, it holds that $\text{Verify}^H(\text{crs}, x, \pi) = 1$. It is zero-knowledge if there exists a PPT simulator $\text{Sim} = (\text{Sim}_{\text{crs}}, \text{Sim}_{\text{H}}, \text{Sim}_{\pi})$ such that the distributions of $\pi' \leftarrow \text{Sim}_{\pi}(\text{crs}, x)$ and $\pi \leftarrow \text{Prove}^H(\text{crs}, x, w)$ are computationally indistinguishable for any $(x, w) \in R$. Note that the sub-algorithms of Sim share state. For simulated proofs, the algorithm $\text{Sim}_\text{H}$ simulates the random oracle and $\text{Sim}_{\text{crs}}$ simulates the $\text{crs} = (\text{srs}, \text{urs})$, where there is an structured part $\text{srs}$. We also define a notion of subversion zero-knowledge, inspired by the notion introduced in [12]. To recall, the second part of the $\text{crs} = (\text{srs}, \text{urs})$ is a random reference string which can later be sampled via a random oracle, and the first part is a structured string $\text{srs}$. For subversion zero-knowledge, there is no $\text{Sim}_{\text{crs}}$

<footnote>$^{19}$ This membership test is required for our definition of subversion zero-knowledge. Let $H$ be a random oracle. Note that in general it is difficult to check that some $\text{srs}$ was generated via GenSRS. (We allow that $SRS$ is not equal to the output space of GenSRS.)</footnote>
anymore and the structured srs can be chosen by $\mathcal{A}$, while urs is sampled uniformly at random by H for the real proofs $\pi \leftarrow \text{Prove}^H(\text{crs}, x, w)$ or by $\text{Sim}_H$ for the simulated proofs $\pi' \leftarrow \text{Sim}_\pi(\text{crs}, x)$. Here we also require that the subverted srs belongs to $\mathcal{SRS}$.

We define adaptive knowledge soundness. An NIZK is adaptively knowledge sound for relation<sup>20</sup> $\tilde{R}$ if there exist positive polynomials $p_T, p_P$, constant $c$, a PPT extractor Ext and a PPT simulator $\text{SimCRS}$ so that for any $(\overline{crs}, td) \leftarrow \text{SimCRS}(1^\lambda)$, given oracle access to any PPT $\mathcal{A}$ (with explicit random tape $\rho$ and making $Q_H = \text{poly}(\lambda)$ RO queries) that cannot distinguish $crs \in \mathcal{CRS}$ from a real crs := (srs $\leftarrow \text{GenSRS}(1^\lambda)$, urs $\leftarrow \mathcal{URS}$), given $(x, \pi) \leftarrow \mathcal{A}^H( crs ; \rho)$, with probability at least $\frac{\mu(\lambda)^c - \text{negl}(\lambda)}{p_P(\lambda, Q_H)}$ the extractor finds $w \leftarrow \text{Ext}(crs, td, x, \pi, \rho, \vec{h})$ where $(x, w) \in \tilde{R}$. Here, $\vec{h}$ contains the outputs of H, the probability is over the random tape $\rho$ of $\mathcal{A}$, the random tape of $\text{SimCRS}$, and the random choices of H. Also, we require that the runtime of Ext is bounded by $p_T(\lambda, Q_H) \cdot \text{Time}(\mathcal{A})$.

We further define *partial online-extractability* for NIZKs over a relation with statements $x = (x_0, x_1)$ and witnesses $w = (w_0, w_1)$. A NIZK is partially online-extractable if there exists an algorithm $\text{Ext} = (\text{Ext}_1, \text{Ext}_2)$ such that $\text{Ext}_1$ samples a partial statement $x_0$ uniformly at random along with a trapdoor td and for any PPT adversary that outputs pairs of partial statements $x_{1,i}$ and proofs $\pi_i$ such that all $((x_0, x_{1,i}), \pi_i)$ verify with probability $\mu(\lambda)$, the extraction algorithm $\text{Ext}_1$ can use the trapdoor to extract partial witnesses $w_{1,i}$ for all statements such that there exist partial witnesses $w_{0,i}$ with probability $\frac{\mu(\lambda)-\text{negl}(\lambda)}{p_P(\lambda, Q_H)}$ where $p_P$ is a polynomial and $Q_H$ is the number of hash queries made by the adversary. Looking forward, we will set the first partial statement $x_0$ to be the public parameters of a commitment scheme and the extracted witness to be the committed values - where the non-extracted witness is the opening of the commitments.

We also define (*statistical*) *adaptive subversion soundness*. Note that this notion does not require an extractor for the witness and the srs can be maliciously set up by an adversary, which differs from the standard notion of adaptive soundness. An NIZK is (*statistically*) *adaptively subversion sound* for relation $\tilde{R}$ inducing a language $\mathcal{L}_{\tilde{R}}$ if no (possibly unbounded) adversary, given a urs and access to the RO H, can output a subverted srs, an instance $x$, and a proof $\pi$ such that $\text{Verify}^H(\text{crs} := (\text{srs}, \text{urs}), x, \pi) = 1$ but $x \notin \mathcal{L}_{\tilde{R}}$.

**Fiat-Shamir transformation.** We recall the Fiat-Shamir transformation [40, 10] to turn a
$\Sigma$-protocol $\Sigma = (\text{Init, Chall, Resp, Verify})$ that satisfies correctness, high-min entropy, honest verifier
zero-knowledge, and $k$-special soundness, into a NIZK $\text{FS}[\Sigma] = (\text{GenSRS}, \text{Prove}^H, \text{Verify}^H)$ using a
random oracle H that maps to the challenge space $CH$ of $\Sigma$:

- GenSRS(1^λ): outputs the empty string ϵ as we do not require a common reference string and omit crs as an input for other below algorithms,

- Prove^H(x, w): receives a statement x and a witness w, runs (Ω, st) ← Init(x, w), computes the challenge γ ← H(x, Ω), then computes τ ← Resp(st, γ) and outputs π = (Ω, γ, τ).

- Verify^H(x, π): receives a statement x and a proof π = (Ω, γ, τ), checks that and outputs b ← Verify(x, Ω, γ, τ) ∧ γ = H(x, Ω).

The resulted NIZK satisfies *correctness*, *adaptive knowledge soundness* and *zero-knowledge*.

4 NIZK-friendly Signature Scheme

In the following, we describe the signature scheme underlying our construction of a blind signature
scheme. The scheme is NIZK-friendly, i.e., compatible with efficiently proving statements about
signatures (e.g. knowledge of a valid signature) in NIZK proofs due to its algebraic structure. Looking
forward, this property will be useful for creating a blind signature scheme using a Fischlin-inspired
construction.

4.1 The scheme

We describe a variant of Fischlin's variant of the Cramer-Shoup signature. We adapt it with the goal of constructing an efficient proof of knowledge of a signature later. The hash function $H: \{0, 1\}^* \to \{0, 1\}^{2\lambda}$ is modelled as a random oracle.

<footnote n="20">20 We remark that the soundness relation $\tilde{R}$ can be different from the (correctness) relation $R$. If $\tilde{R}$ is not explicitly defined, we implicitly set $\tilde{R} = R$.</footnote>
The signature consists of three values $y \in \mathbb{Z}_N^*$, $a \in \mathbb{Z}$ and $e \in \mathbb{Z}$. We define intervals $S_a$ and $S_e$ which we use to sample $a$ and $e$ in Sign, respectively. Also, we define the intervals $\mathcal{R}_a$ and $\mathcal{R}_e$ which we use to in Verify to check range membership of $a$ and $e$, respectively.

Let $A = 2^{3\lambda}$ and $S_a = [0, A]$. Also, let $\mathcal{R}_a \supseteq S_a$, $S_e$ and $\mathcal{R}_e \supseteq S_e$ be intervals such that for all $a \in \mathcal{R}_a$, we have $a < e$ for any $e \in \mathcal{R}_e$. Further, we require that $|\mathbb{P}_{S_e}| = \Omega(2^{2\lambda})$ (i.e., $S_e$ contains at least $\Omega(2^{2\lambda})$ primes).

- $\mathsf{S}_{\text{fis}}.\text{KeyGen}(1^{\lambda})$: Sets $(N, P, Q) \leftarrow \text{GenRSA}(1^{\lambda})$. Samples generators $h, h_1, h_2 \leftarrow \text{Gen}(\text{QR}_N)$ for $\text{QR}_N$ at random. Outputs the public key $\text{vk} = (N, h, h_1, h_2)$ and the secret key $\text{sk} = (P, Q)$.

- $\mathsf{S}_{\text{fis}}.\text{Sign}(\text{sk}, m)$: Parses $\text{sk} = (P, Q)$ and computes $\bar{m} = \text{H}(m)$. Then, picks $e \leftarrow \mathbb{P}_{S_e}$ and $a \leftarrow S_a$ at random. Compute $y$ such that

$$y^e = h \cdot h_1^a \cdot h_2^{a+\bar{m}} \mod N.$$

Output the signature $\sigma = (e, a, y)$.

- $\mathsf{S}_{\text{fis}}.\text{Verify}(\text{vk}, m, \sigma)$: Parses $\text{vk} = (N, h, h_1, h_2)$ and $\sigma = (e, a, y)$. Checks that $e \in \mathcal{R}_e$ is odd, $a \in \mathcal{R}_a$, and that

$$y^e = hh_1^a h_2^{a+\text{H}(m)} \mod N.$$

## 4.2 Proof of Security

A detailed proof is given in Appendix B.2. We give a brief sketch below.

Our proof mostly follows the proof given in [41]. The reduction first punctures the verification key $\text{vk}^*$. Roughly, this is done by generating all primes $\mathcal{E} = \{e_1, \dots, e_Q\}$ chosen during signing in advance, and setting up $h, h_1, h_2$ with respect to $\mathcal{E}$. There are two cases for the punctured setup $^{21}$:

1. The reduction guesses that the forgery's $e$ was used during signing, i.e., $e \in \mathcal{E}$.

2. The reduction guesses that the forgery contains a fresh $e$, i.e., $e \notin \mathcal{E}$.

Then, the reduction sets up $h, h_1, h_2$ in such a way that it can sign $Q$ arbitrary messages via a trapdoor td but without knowing the factorization of $N$. This is done by embedding $\mathcal{E}$ into $h, h_1, h_2$ depending on the guess. Note the punctured setup is indistinguishable from the real setup in both cases. Also, signing via the trapdoor td reveals no information about the guess. Then, it answers all $Q$ signing queries via td and hopes that its guess was correct. If so, the reduction can derive a sRSA solution. Since the guess remains hidden, this happens with sufficient probability.

We also use this strategy in the proof of the blind signature scheme in Section 6. In our blind signature, the primes $e$ are not chosen by the signer but output by a hash function $\text{H}_P$. This still allows the reduction to prepare the list $\mathcal{E}$ of primes used during signing. For a modular security proof, we provide the punctured key generation and alternative signing procedure in Appendix B.1. Since these algorithms depend on guesses with respect to the forgery's format, they are indexed by bits $(b, b')$ that correspond to with in a case distinction in the proof.

# 5 Novel Commitment Schemes

We give an overview of our novel commitment constructions. These are helpful for our instanti-
ation and influence the choice of primitives that our blind signature relies on. We construct two
commitments that admit efficient openings in zero-knowledge:

**Relaxed Integer Commitments:** allows to commit to integers of a specific range $I$. The proof of knowledge of an opening proves that the committed integer lies in $I$. The soundness is relaxed however, i.e., it only guarantees membership in a larger range $I_R \supset I$. Importantly, binding still holds with respect to the range $I_R$.

**Commitments in Groups:** allows to commit to elements of arbitrary cyclic groups $\mathbb{G}$ given a generator $g$ of $\mathbb{G}$.

<footnote>$^{21}$ In the detailed proof, the first case has two additional sub cases.</footnote>
To improve readability, we use additive notation for prime-order groups and multiplicative notation otherwise. Recall that we require several types of commitments in our blind signature construction. Before we describe our novel commitments, we recap the required commitments and sketch how they are instantiated to provide context for the reader. We use the terminology from the technical overview (cf. Section 2):

- Compatible commitment: instantiated via MPed commitments (cf. Section 3.1). This is the homomorphic commitment that the user sends to the signer to sign. The user can then later derive a signature on the original message from the signature on the commitment.

- C<sub>Z</sub>: instantiated via ElGamal commitments via the observation in remark 1. Details are provided in Appendix E.1. Recall that this commitment is used as an input to the hash function H<sub>P</sub> to obtain the prime exponent e.

- C<sub>RInt</sub>: instantiated via our relaxed integer commitments (cf. Section 5.1). This commitment will be used as a building block of the proof of knowledge of a S<sub>fis</sub> signature that the user outputs in the end.

- C<sub>Grp</sub>: This commitment to group elements (cf. Section 5.2) is used as a building block in the NIZK that constitutes our blind signature.

## 5.1 Relaxed Integer Commitments with Slack

We define the notion of relaxed integer commitment schemes parameterized by $B, T \in \mathbb{N}$. Those are commitments with message space $C_{\text{msg}} = [0, B]$ that admit efficient opening proofs in zero-knowledge with some slack, i.e., soundness guarantees that $x \in [-BT, BT]$. We refer to $B$ as the range and $T$ as the slack.

**Definition 5.** A relaxed integer commitment is a commitment scheme $C_{\text{RInt}}^{\vec{B},T} = (\text{Setup}, \text{Commit}, \text{Verify})$ parameterized by two values $T \in \mathbb{N}$ and $\vec{B} \in \mathbb{N}^\ell$ for some $\ell \in \mathbb{N}$. The value $\vec{B}$ defines the message space $C_{\text{msg}} = [0, \vec{B}] \subseteq \mathbb{Z}^\ell$. The value $T$ defines a relaxed message space $C_{\text{msg}}^{\text{rel}} = [-\vec{B}T, \vec{B}T]$. We further require that the commitment scheme $C_{\text{RInt}}$ is

1. correct and hiding with respect to $C_{\text{msg}}$ (i.e., the messages are sampled from $C_{\text{msg}}$ in the Definitions 11 and 12), and

2. binding with respect to $C_{\text{msg}}^{\text{rel}}$ (i.e., the adversarial messages are allowed to be in $C_{\text{msg}}^{\text{rel}}$ instead of $C_{\text{msg}}$ in Definition 13).

We now instantiate $C_{\text{RInt}}$ over a group $\mathbb{G}$ with prime order $p \ge 2^{2\lambda}$. Let $\text{pp} = (G, H) \in (\mathbb{G} \setminus \{0\})^2$ be the public parameters, where 0 denotes the neutral element. Let $B, T \in \mathbb{N}$ such that $BT < \frac{p-1}{2}$. The commitments are ElGamal commitments $c \leftarrow (xG + rH, rG)$ for $r \leftarrow \mathbb{Z}_p$, except that we add the additional requirement of $x \in [-BT, BT]$ in verification. Note that as we have $[-BT, BT] \subset [-\frac{p-1}{2}, \frac{p-1}{2}]$, this condition ensures that no overflows occur (so we commit to a subset of $\mathbb{Z}$). Looking ahead, our zero-knowledge opening proofs leverage the structure of $\mathbb{QR}_N$ to ensure that extracted values are integers in the relaxed range.

We naturally generalize our commitment scheme to vectors $\vec{m} = (m_1, \dots, m_\ell) \in [0, \vec{B}]$ of integers from (potentially different) intervals induced by $\vec{B} = (B_1, \dots, B_\ell)$. We require that $B_i \cdot T < \frac{p-1}{2}$ for all $i \in [\ell]$. The integer commitment $C_{\text{RInt}}^{\vec{B},T}$ with uniform public parameters $\text{pp} = (H, \vec{G})$ is given below, where $\vec{G} = (G_1, \dots, G_\ell)$. The randomness space is $C_{\text{rnd}} = \mathbb{Z}_p$. By definition, the message space is $C_{\text{msg}} = [0, \vec{B}]$ and the relaxed message space is $C_{\text{msg}}^{\text{rel}} = [-\vec{B}T, \vec{B}T]$.

- $C_{\text{RInt}}^{\vec{B},T}$. Commit($\text{pp}, \vec{m}$): Takes as input public parameters $\text{pp}$ and $\vec{m} \in [0, \vec{B}]$, samples $r \leftarrow \mathbb{Z}_p$, sets $C_i \leftarrow m_i H + r G_i$, $\vec{C} \leftarrow (C_1, \dots, C_\ell)$, $F \leftarrow rH$, and outputs $(c, r)$ for $c = (\vec{C}, F)$.

- $C_{\text{RInt}}^{\vec{B},T}$. Verify($\text{pp}, c, \vec{m}, r$): Takes as input $(c, r) \in \mathbb{G}^{\ell+1} \times \mathbb{Z}_p$, parses $c = (\vec{C}, F)$ and checks that

$$ \vec{m} \in [-\vec{B}T, \vec{B}T], \quad F = rH, \quad \vec{C} = \vec{m}H + r\vec{G}. $$

If the (relaxed) range (induced by $\vec{B}$ and $T$) is clear by context, we often write $C_{\text{RInt}}$ for short.

**Theorem 1.** The scheme $C_{\text{RInt}}$ is correct, hiding under DDH in $\mathbb{G}$, and perfectly binding.
*Proof.* Correctness is straightforward.

For hiding, we have $(H, G_i, rH, rG_i) \stackrel{c}{\approx} (H, G_i, rH, t_i G_i)$ for $t_i \leftarrow \mathbb{Z}_p$ under DDH. Since $t_i G_i$ masks $m_i H$ additively, the value $m_i H + t_i G_i$ is uniform in $\mathbb{G}$. Thus, $(\vec{C}, F) \stackrel{c}{\approx} \vec{D}$ for $\vec{D} \leftarrow \mathbb{G}^{\ell+1}$ after $\ell$ game hops.

For binding, observe that since $\vec{m} \in [-\vec{B}T, \vec{B}T] \subset [-\frac{p-1}{2}, \frac{p-1}{2}]^\ell$, the message $\vec{m}$ is uniquely determined by $c$ and the verification equations. In more detail, if $c = (\vec{C}, F)$ verifies correctly, then we have $r = \log_H(F) \in \mathbb{Z}_p$ and $m_i H = C_i - rG_i$. Thus, we have $m_i \equiv \log_H(C_i - rG_i) \bmod p$. Since for every $x \in \mathbb{Z}_p$, there is exactly one $m_i \in [-\frac{p-1}{2}, \frac{p-1}{2}]$ such that $m_i \equiv x$, the value $m_i$ is uniquely determined. $\square$

Note that we could also set $C \leftarrow rH + \sum_i x_i G_i$ to obtain compact commitments. We choose ElGamal commitments instead of Pedersen commitments as in our applications, we require perfect binding. In our construction, we also require exact integer commitments for some fixed range.

**Definition 6 (Integer commitments with bounded range).** If the range in verification is identical to the message space, we say that the commitment is an (exact) integer commitment with $C_{\text{msg}} = [0, \vec{B}]$ (and $C_{\text{msg}} = C_{\text{rel msg}}^{\text{rel}}$).

## 5.2 Commitments in Arbitrary Cyclic Groups

Let $\hat{\mathbb{G}} = \langle \hat{g} \rangle$ be an arbitrary cyclic group with generator $\hat{g}$. We assume an upper bound $U$ on the order of $\hat{\mathbb{G}}$.

We construct a commitment scheme with message space $C_{\text{msg}} = \hat{\mathbb{G}}$ (i.e., for messages $\hat{x} \in \hat{\mathbb{G}}$). Looking ahead, we cannot rely on computational hardness assumptions in $\hat{\mathbb{G}}$ (as in our construction, this group can be chosen maliciously by the adversary). As secure (non-interactive) commitments require some type of hardness assumption, we need some additional structure. For this, we use an additional relaxed integer commitment scheme $C_{\text{RInt}}^{B,T}$ (with parameters $B, T$ defined below) $^{22}$. To commit to $\hat{x} \in \hat{\mathbb{G}}$, a user first sets $\hat{c} \leftarrow \hat{x}\hat{g}^s$ for $s \leftarrow [0, U \cdot 2^\lambda]$. Note that $\hat{c}$ hides $\hat{x}$ statistically, but is not binding to $\hat{x}$. For example, a user can open $\hat{c} = \hat{g}\hat{g}^2$ to message $\hat{g}$ or $\hat{g}^2$.

To achieve binding, the user additionally commits to its randomness $s$ in a commitment $c$ via $C_{\text{RInt}}^{B,T}$ for $B = U \cdot 2^\lambda$ and $T$ arbitrary. If $s$ is fixed over the integers $\mathbb{Z}$, the user is forced to open the commitment $\hat{c}$ to the message $\hat{x} = \hat{c} \cdot \hat{g}^{-s}$. Note that the commitment $c$ fixes $s$ over a subset of $\mathbb{Z}$ (due to binding of $C_{\text{RInt}}$) which is sufficient $^{23}$. Since $C_{\text{RInt}}$ is hiding, the additional commitment $c$ reveals no information about $s$ and thus, the scheme remains hiding.

Since our instantiation of $C_{\text{RInt}}$ requires a group $\mathbb{G}$ (whose size scales with $B$), we allow $s$ to be split into a vector $\vec{s}$ with $s_i \in [0, B]$. Then, the user commits to $\vec{s} \in [0, \vec{B}]$ via $C_{\text{RInt}}^{\vec{B},T}$ for $\vec{B} = (B, \dots, B)$ and arbitrary $B \in \mathbb{N}$. Let $\ell = \lceil \log(U \cdot 2^\lambda)/\log(B) \rceil$. The commitment scheme $C_{\text{Grp}}$ (which is implicitly parameterized by $C_{\text{RInt}}$) is given below.

- $C_{\text{Grp}}.\text{Setup}(1^\lambda)$: Outputs $pp \leftarrow C_{\text{RInt}}^{\vec{B},T}$. Setup($1^\lambda$).

- $C_{\text{Grp}}.\text{Commit}(pp, \hat{x})$: Takes as input public parameters $pp$ and $\hat{x} \in \hat{\mathbb{G}}$, samples $s \leftarrow [0, U \cdot 2^\lambda]$, sets $\hat{c} \leftarrow \hat{x}\hat{g}^s$. Then, decomposes $s = \sum_{i=1}^\ell s_i B^{i-1}$ with $s_i \in [0, B]$ and commits to $\vec{s} = (s_1, \dots, s_\ell)$ via $(c, r) \leftarrow C_{\text{RInt}}.\text{Commit}(pp, \vec{s})$. Outputs $(c_x, r_x)$ for $c_x = (\hat{c}, c)$ and $r_x = (\hat{s}, r)$.

- $C_{\text{Grp}}.\text{Verify}(pp, c_x, \hat{x}, r_x)$: Parses $c_x, r_x$ as above. Then, sets $s = \sum_{i=1}^\ell s_i B^{i-1}$ and checks that $C_{\text{RInt}}.\text{Verify}(pp, c, \vec{s}, r) = 1$ and $\hat{c} = \hat{x}\hat{g}^s$.

**Theorem 2.** *The scheme $C_{\text{Grp}}$ is correct, hiding and binding under the hiding and binding property of $C_{\text{RInt}}$, respectively.*

<footnote>$^{22}$ If we instantiate $C_{\text{RInt}}$ as in Section 5.1, then the additional structure is a prime order group $\mathbb{G}$ in which DDH is assumed to be hard.</footnote>

<footnote>$^{23}$ Note that for our construction, it is important that $C_{\text{RInt}}$ commits over the integers. For example, a commitment $c$ over $\mathbb{Z}_p$ is not sufficient. To illustrate this, assume that $s \in \mathbb{Z}$ is fixed over $\mathbb{Z}_p$. Then, $\hat{c} = \hat{g}^s \hat{g}^{s^p}$ can be opened to $\hat{g}^s$ or $\hat{g}^{s^p}$ since $s \equiv s^p \bmod p$. But we have $\hat{g}^s = \hat{g}^{s^p}$ only if $\text{ord}(\hat{g}) | s(s^{p-1}-1)$. Since the order is unknown, this does not hold in general and thus, the commitment is not binding.</footnote>
*Proof.* Correctness is straightforward.

Hiding is argued as follows. First, observe that $c \leftarrow C_{\text{RInt}}(\text{pp}, \vec{s}) \stackrel{c}{\approx} C_{\text{RInt}}(\text{pp}, \vec{0})$ under the hiding property of $C_{\text{RInt}}$. Also, the distribution of $\hat{c} = \hat{x} \cdot \hat{g}^s$ for $s \leftarrow [0, U \cdot 2^{2\lambda}]$ has a statistical distance of at most $2^{-\lambda}$ to the uniform distribution $U_{\hat{G}}$ over $\hat{G}$. Thus, we have $\hat{c} \stackrel{s}{\approx} U_G$. In total, $(\hat{c}, c) \stackrel{c}{\approx} (U_{\hat{G}}, C_{\text{RInt}}(\text{pp}, \vec{0}))$ for $(\hat{c}, c) \leftarrow C_{\text{Grp}}.\text{Commit}(\text{pp}, \hat{x})$.

Binding follows from the binding property of $C_{\text{RInt}}$ and since $\hat{x} = \hat{g}^s \hat{c}^{-1}$ is uniquely determined if $s$ is fixed. In more detail, we reduce binding to the binding property of $C_{\text{RInt}}$. Let $\mathcal{A}$ be an adversary on the binding property of $C_{\text{Grp}}$. First, obtain $\text{pp}$ from a challenger of the $C_{\text{RInt}}$ binding property. Set $(c_x, \hat{x}^{(0)}, \hat{x}^{(1)}, r_x^{(0)}, r_x^{(1)}) \leftarrow \mathcal{A}(\text{pp})$. Parse $c_x = (\hat{c}, c)$ and $r_x^{(b)} = (\vec{s}^{(b)}, r^{(b)})$. Output $(c, \vec{s}^{(0)}, \vec{s}^{(1)}, r^{(0)}, r^{(1)})$ to the challenger.

To analyze the success probability, assume that $\mathcal{A}$ is successful. Then, we have $\hat{x}^{(0)} \neq \hat{x}^{(1)} \in \hat{G}$ and $C_{\text{Grp}}.\text{Verify}(\text{pp}, c_x, \hat{x}^{(b)}, r_x^{(b)}) = 1$ for $b \in \{0, 1\}$. Set $s^{(b)} = \sum_{i=1}^{\ell} \vec{s}_i^{(b)} B^{i-1}$. If $s^{(0)} = s^{(1)} := s$, we have that

$$ \hat{c} = \hat{x}^{(0)} \cdot \hat{g}^s = \hat{x}^{(1)} \hat{g}^s. $$

Thus, we have $\hat{x}^{(0)} = \hat{x}^{(1)}$ which contradicts our assumption. Consequently, it holds that $s^{(0)} \neq s^{(1)}$. By construction of $s^{(0)}$ and $s^{(1)}$, it must hold that $\vec{s}^{(0)} \neq \vec{s}^{(1)}$ over $\mathbb{Z}^\ell$. But since $C_{\text{RInt}}.\text{Verify}(\text{pp}, c, \vec{s}^{(b)}, r^{(b)}) = 1$ for $b \in \{0, 1\}$, the values $(c, \vec{s}^{(0)}, \vec{s}^{(1)}, r^{(0)}, r^{(1)})$ form a valid solution for the binding game of $C_{\text{RInt}}$. $\square$

## 5.3 Efficient Opening in Zero-Knowledge

We construct efficient NIZKs $\Pi_{\text{int}}$ and $\Pi_{\text{grp}}$ to open $C_{\text{RInt}}$ and $C_{\text{Grp}}$, respectively, in zero-knowledge. Due to space limitations, we refer to Section 2 for a brief overview. The full schemes are given in Appendix C.1.

# 6 Blind Signature with Malicious Signer Blindness

In this section, we detail our blind signature construction based on the strong RSA assumption and DDH in prime order groups.

## 6.1 Primitives

Before we detail our construction, we prepare the required primitives and related parameters. To see how these primitives fit in the larger picture, we refer to Section 2.

*Remark 2.* In the following, we will define several NIZKs. As the reference string $crs$ of these NIZKs are set up by the signer, we need to be careful with the security guarantees of each NIZK. For cases where the signer takes the role of the prover, we require subversion soundness (i.e., the soundness property should hold even with regard to a maliciously generated $crs$) but standard zero-knowledge is sufficient. If the signer takes on the role of the verifier, we require subversion zero-knowledge (i.e., the zero-knowledge property should still hold even with regard to a maliciously generated $crs$).

**Relaxed integer commitment.** To construct a proof of knowledge of a signature of the scheme $S_{\text{fis}}$, we use a relaxed integer commitment. The scheme is required to be perfectly binding to fix (parts of) the signature before extraction. We describe the choices of parameters and motivate them in the following.

Let $T \in \mathbb{N}$. Let $A = 2^{3\lambda}$, $E = 2^{3\lambda}$, and $\overline{E} \in \mathbb{N}$ such that the following equations hold.

$$ \log(\overline{E}) = \text{poly}(\lambda) \qquad (5) $$

$$ A \cdot T < \overline{E} - ET. \qquad (6) $$

Let $C_{\text{RInt}}^{\vec{B}, T}$ be a relaxed integer commitment scheme with uniform public parameters of length $\ell_{\text{rint}}$, perfect binding and computational hiding (cf. Section 5.1) for $\vec{B} := (A, E)$ and slack $T$. We write $C_{\text{RInt}}$ for short. The choices for these parameters are motivated below.
Recall that $\vec{B}$ defines the message space $[0, \vec{B}]$ and that the slack $T$ dictates the relaxed message space $[-\vec{B}T, \vec{B}T]$, i.e., the message space for verification$^{24}$.

For convenience, let $S_a := [0, A]$ and $S_e := [\bar{E}, \bar{E} + E]$. In our construction, we commit to $a \in S_a$ and $e - \bar{E} \in [0, E]$ for $e \in S_e$ via $C_{\text{RInt}}$. The above parameter choices guarantee that for message $(a, e - \bar{E})$ that passes $C_{\text{RInt}}$ verification, it holds that the values $(a, e)$ pass the range checks in the $S_{\text{fis}}$ signature.

To illustrate this, set $\mathcal{R}_a := [-AT, AT]$ and $\mathcal{R}_e := [\bar{E} - ET, \bar{E} + ET]$. By Eq. (6), we have that for any $a \in \mathcal{R}_a$ and $e \in \mathcal{R}_e$ that $a < e$. Further, verification of $C_{\text{RInt}}$ guarantees that the committed $a$ lies in the interval $a \in S_a$ as desired. Also, since we commit to $e - \bar{E} \in [-ET, ET]$, we have $e \in S_e$.

In our instantiation, we can employ our $C_{\text{RInt}}$ construction from Section 5.1 which can be opened with a simple NIZK $\Pi_{\text{int}}$. This is the core technique that allows us to construct a proof of knowledge of a $S_{\text{fis}}$ signature in an efficient manner$^{25}$.

In the instantiation, we set $\bar{E} = 2^{5\lambda}$. Then, it is guaranteed that the interval $S_e = [\bar{E}, \bar{E} + E]$ contains at least $\Omega(2^{2\lambda})$ primes. This follows from a recent refinement [58] of Huxley's bound [60, 57]. We provide a full proof in Appendix D.1. This is required to avoid collisions in a hash function mapping into $S_e$.

**Proof of Knowledge for $S_{\text{fis}}$ signatures.** We require a NIZK to proof knowledge of a valid $S_{\text{fis}}$ signature $(e, a, y)$ on the hash of a message $\bar{m}$. To prove one-more unforgeability, we require that $(e, a)$ are fixed statistically in the statement. Thus, we add a $C_{\text{RInt}}$ commitment for $(e, a)$ which also enables efficient proofs for range membership (as discussed above). Let $\Pi_{\text{fis}}$ be an NIZK with oracle $H_{\text{fis}}$ for the relation

$$ \mathcal{R}_{\text{fis}} := \left\{ (x, w) \mid y^e \equiv h \cdot h_1^a \cdot h_2^{a+\bar{m}} \bmod N, e \equiv 1 \bmod 2, y \in \langle h_1 \rangle, (c_I, d_I) = \mathcal{C}_{\text{RInt}}.\text{Commit}(\text{pp}_I, (a, e - \bar{E}); r_I), e \in S_e, a \in S_a \right\} $$

for $x = (\text{pp}_I, N, h_1, h_2, h, \bar{m}, c_I), w = (e, a, y, r_I, d_I)$ with subversion zero-knowledge, correctness, and adaptive knowledge soundness for the relation

$$ \tilde{\mathcal{R}}_{\text{fis}} := \left\{ (x, w) \mid y^e \equiv h \cdot h_1^a \cdot h_2^{a+\bar{m}} \bmod N, e \equiv 1 \bmod 2, \mathcal{C}_{\text{RInt}}.\text{Verify}(\text{pp}_I, (a, e - \bar{E}), d_I) = 1 \right\} $$

with $x, w$ as above. Note that the soundness relation $\tilde{\mathcal{R}}_{\text{fis}}$ implies that $a \in \mathcal{R}_a$ and $e \in \mathcal{R}_e$ (cf. Section 6.1) and thus, $(e, a, y)$ form a valid $S_{\text{fis}}$ signature. For zero-knowledge and correctness, there are stronger requirements for the witness (which are fulfilled in our construction). Notably, we require that $a \in S_a, e \in S_e$, and that $y \in \langle h_1 \rangle$. (The latter is required to commit to $y$ via $C_{\text{Grp}}$ in our instantiation.)

**Integer commitment and opening proof for Pedersen.** Let $S \in \mathbb{N}$. Let $C_Z$ be an exact integer commitment scheme with message space $C_Z.C_{\text{msg}} = [0, 2^{\lambda} - 1] \times [0, S]$ with uniform public parameters of length $\ell_Z$, correctness, perfect binding, and computational hiding (cf. Definition 6). We denote by $C_Z.C_{\text{opn}}$ the opening space of $C_Z$. In the blind signature scheme, we will require the user to both the hash $\bar{m}$ as well as the random coins $r$ that it plans to use to derive the Pedersen commitment using the perfectly binding commitment scheme $C_Z$. This first commitment is hashed to obtain the prime $e$ used for signing. Furthermore, the user is required to attach a proof $\pi_{\text{ped}}$ that the Pedersen commitment $c$ is consistent with the hash $\bar{m}$ and the coins $r$. The commitment $c_Z$ along with the proof $\pi_{\text{ped}}$ allows the reduction in the one-more unforgeability proof to obtain the value $\bar{m}$ and the coins $r$ which in turn enables it to generate signatures using the alternate signing algorithms from Appendix B.1. In the proof of blindness, we rely on the zero-knowledge property of $\Pi_{\text{ped}}$ as well as the hiding property of the commitment schemes.

<footnote>$^{24}$ In our instantiation, we have $T = 2^{\lambda+1}L$ with $L = 2^{10}$. It is sufficient to set $\bar{E} = 2^{5\lambda}$ to have $AT = 2^{4\lambda+11} < 2^{5\lambda} - 2^{4\lambda+11} = \bar{E} - ET$ for Eq. (6) if $\lambda \ge 14$.</footnote>

<footnote>$^{25}$ In our construction, the value $\vec{B}$ is large. Our technique allows to avoid the use of exact range proofs whose efficiency scales noticeably with the range $[0, \vec{B}]$.</footnote>
Let $\Pi_{\text{ped}}$ be an NIZK with oracle $H_{\text{ped}}$ for the relation

$$R_{\text{ped}} := \{(x, w) \mid c \equiv h_2^{\overline{m}} \cdot g^{re} \bmod N, \mathbb{C}_Z.\text{Verify}(\text{pp}, c_Z, (\overline{m}, r), d_Z) = 1, \\ \qquad \qquad \qquad \qquad \qquad \overline{m} \in [0, 2^{\lambda} - 1], r \in [0, S]\},$$

for $x = (\text{pp}, N, e, h_2, g, c, c_Z)$, $w = (\overline{m}, r, d_Z)$ with correctness and subversion zero-knowledge. We also require partial online-extraction for $R_{\text{ped}}$, where we split the statement $x$ into $x_0 = \text{pp}$ and $x_1 = (N, e, h_2, g, c)$ and the witness into $w_0 = d_Z$ and $w_1 = (\overline{m}, r)$. (This implicitly defines the partial statement space $X_0 = \{0, 1\}^{\ell_z}$ and the partial witness space $W_1 = \mathbb{C}_Z \cdot \mathbb{C}_{\text{opn}}$.) The user uses the NIZK to ensure that the commitment $c$ is indeed formed with the values committed via $\mathbb{C}_Z$. For the security proof, the reduction “punctures” the verification key in such a way that it can sign messages without knowing the secret key. For this reason, online-extraction is required to extract the messages before signing. As mentioned above, we exclude $d_Z$ from the extracted witness for efficiency (as existence is sufficient). Also, we embed the extraction trapdoor in the public parameters (instead of the crs also for efficiency) $^{26}$.

**NIZKs for group membership.** As the factorization of the RSA modulus $N$ is private, it is hard to check whether a given $g \in \mathbb{Z}_N^*$ generates the entire group $\mathbb{Q}\mathbb{R}_N$. This means that we need to prevent the signer from setting up the signing key for $\mathbb{S}_{\text{fis}}$ in a malicious way that allows the following attack against blindness. Recall that the user sends blinded commitment $c = h_2^{\overline{m}} g^{re}$ to the signer during signing. When $\langle h_2 \rangle \neq \langle g \rangle$, a malicious signer could raise $c$ to the power of $\text{ord}(g)$ to remove the part $g^{re}$ and then check whether the resulting $c^{\text{ord}(g)} = (h_2^{\overline{m_0}})^{\text{ord}(g)}$ or $c^{\text{ord}(g)} = (h_2^{\overline{m_1}})^{\text{ord}(g)}$, and thus breaking blindness.

We carefully design our blind signature such that it actually suffices to check that for some group elements $h$ in the verification key and a generator $g$, it holds that $\langle g \rangle =: \mathbb{G} = \langle h \rangle$.

We describe how the signer can prove this in a NIZK: Since the signer sets up the elements $g$ and $h$ itself, it can set $h = g^x$ for some $x \in \mathbb{Z}_{\text{ord}(g)}$. Knowing $x$, constructing such a proof for $\langle h \rangle =: \mathbb{G}$ is simple. Since the signer sets up multiple such values $h$, we batch the statement for simplicity.

Let $\Pi_{\text{gen}}$ be an NIZK with oracle $H_{\text{gen}}$ satisfying statistical adaptive subversion soundness, zero-knowledge, and correctness for the relation

$$R_{\text{gen}} = \{(x, w) \mid \forall i \in [k] : h_i^{\alpha_i} \equiv h \bmod N, h_i^{\beta_i} \equiv h_i \bmod N\},$$

where $x = (N, k, h, (h_i)_{i \in [k]})$, $w = ((\alpha_i, \beta_i)_{i \in [k]})$. Note that $R_{\text{gen}}$ implies that $\langle h \rangle = \langle h_i \rangle$ for all $i$.

**Hash functions.** We require the following hash functions in our construction. Each hash function is modeled as random oracle in the security proofs.

- $H_{\text{urs}}$: Let $H_{\text{urs}}: \{0, 1\}^* \to \{0, 1\}^{\ell_{\text{ped}}} \times \{0, 1\}^{\ell_{\text{fis}}} \times \{0, 1\}^{\ell_{\text{gen}}}$ be a hash function, where $\ell_{\text{zkp}}$ is the bit-size of the uniform reference string of $\Pi_{\text{zkp}}$. Later, we use $H_{\text{urs}}$ to setup the random part urs of each crs for the above NIZKs.

- $H$: Let $H: \{0, 1\}^* \to [0, 2^{2\lambda} - 1]$ be a hash function. Later, we use $H$ to compute a short digest $\overline{m} = H(m)$ of the message $m \in \{0, 1\}^*$.

- $H_{\mathbb{P}}$: Let $H_{\mathbb{P}}: \{0, 1\}^* \to \mathbb{P}_{S_e}$ be a hash function mapping into the primes in the interval $S_e$.

- $H_{\text{pp}}$: Let $H_{\text{pp}}: \{0, 1\}^* \to \{0, 1\}^{\ell_z} \times \{0, 1\}^{\ell_{\text{int}}} \to \mathbb{Z}_{\text{Z}}$ be a random oracle.

- $H_{\text{prf}}$: Let $H_{\text{prf}}: \{0, 1\}^{\lambda} \times \{0, 1\}^* \to S_a$ be a random oracle. We use this hash function like a PRF to make the signer deterministic.

Note that we can instantiate $H_{\mathbb{P}}: \{0, 1\}^* \to \mathbb{P}_{S_e}$ by picking uniformly random elements in the space $S_e := [\overline{E}, \overline{E} + E]$ until we hit a prime. The distribution of the outputs of $H_{\mathbb{P}}$ is uniform over $\mathbb{P}_{S_e}$, which is the set of primes in the interval $S_e$. Appendix D.1 proves the following lemma.

**Lemma 1.** For $E = 2^{3\lambda}, \overline{E} = 2^{5\lambda}$, there are $\Omega(2^{2\lambda})$ primes in $S_e = [\overline{E}, \overline{E} + E]$.

<footnote>$^{26}$ Roughly, the commitment $\mathbb{C}_Z$ is extractable and we embed the extraction trapdoor into pp. But pp is part of the statement, so we make sure that this part is sampled at random (cf. Definition 25).</footnote>
## 6.2 Construction

Set $S = N \cdot 2^{\lambda}$ which is passed implicitly as parameter in our construction. Also, we set $pp = (pp_I, pp_Z) \leftarrow H_{pp}(0)$. We assume that user and signer compute $pp = H_{pp}(0)$ implicitly. The construction is detailed below. We also detail a signing session in Fig. 1.

- $BS_{fis.KG}(1^{\lambda})$: First, generates the crs for the NIZKs as $crs_{zkp} \leftarrow (srs_{zkp}, urs_{zkp})$, where $srs_{zkp} \leftarrow \Pi_{zkp}.GenSRS(1^{\lambda})$ for $zkp \in \{ped, fis, gen\}$ and $(urs_{ped}, urs_{fis}, urs_{gen}) \leftarrow H_{urs}(0)$. Then, generates a public key for $S_{fis}$ as follows. Sets $(N, P, Q) \leftarrow GenRSA(1^{\lambda})$ and samples $g \in QR_N$. Samples $\alpha_i \leftarrow \mathbb{Z}_{ord(g)}$ and sets $\beta_i \leftarrow \alpha_i^{-1} \mod ord(g)$ for $i \in [3]$. computes $h_1 \leftarrow g^{\alpha_1} \mod N, h_2 \leftarrow g^{\alpha_2} \mod N$ and $h \leftarrow g^{\alpha_3} \mod N$. Note that $h, h_1$ and $h_2$ are generators of $QR_N$ with overwhelming probability. Next, proves that all $QR_N$ elements in $bvk$ key generate the same group via $\pi_{gen} \leftarrow \Pi_{gen}.Prove^{H_{gen}}(crs_{gen}, x_{gen}, w_{gen})$, where $x_{gen} = (N, 3, g, (h, h_1, h_2))$, $w_{gen} = (\alpha_i, \beta_i)_{i \in [3]}$. Then, sample a key $K \leftarrow \{0, 1\}^{\lambda}$ for $H_{prf}$. Finally, output

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

$$bsk = (bvk, P, Q, K).$$

- $BS_{fis.User}(bvk, m)$: Given verification key $bvk$, and message $m$, checks

$$\Pi_{gen}.Verify^{H_{gen}}(crs_{gen}, x_{gen}, \pi_{gen}) = 1$$

for $x_{gen} = (N, 4, (h, h_1, h_2, g))$. Then, sets $\bar{m} \leftarrow H(m)$ and set up a commitment $c$ to $\bar{m}$ as follows. Samples randomness $r \leftarrow [0, S]$ for $c$ and commits to $(\bar{m}, r)$ via $(c_Z, d_Z) \leftarrow C_Z.Commit(pp, (\bar{m}, r))$. Sets $e \leftarrow H_P(c_Z)$ and compute $c = h_2^{\bar{m}} \cdot g^{re} \mod N$. Next, generate a proof $\pi_{ped} \leftarrow \Pi_{ped}.Prove^{H_{ped}}(crs_{ped}, x_{ped}, w_{ped})$ for $x_{ped} = (pp, N, e, h_2, g, c, c_Z)$, $w_{ped} = (\bar{m}, r, d_Z)$. Note that $\pi_{ped}$ proves that the generation of $c$ was performed honestly with respect to $c_Z$. Finally, output

$$\rho_1 = (c, c_Z, \pi_{ped}),$$

$$st_U = (e, r, m).$$

- $BS_{fis.Signer}(bsk, \rho_1)$: Given signing key $bsk = (bvk, P, Q, K)$ and user's output $\rho_1 = (c, c_Z, \pi_{ped})$, checks $\Pi_{ped}.Verify^{H_{ped}}(crs_{ped}, x_{ped}, \pi_{ped}) = 1$ for $x_{ped} = (pp, N, e, h_2, g, c, c_Z)$. Next, computes $e \leftarrow H_P(c_Z)$ and sets $d \leftarrow e^{-1} \mod \phi(N)$. Then, sets $a \leftarrow H_{prf}(K, c \parallel c_Z)$ which it uses as randomness for the signing process. Using $d$ and $a$, computes a presignature $z$ via $z' \leftarrow h \cdot h_1^a \cdot c \cdot h_2^a \mod N$ and $z \leftarrow (z')^d \mod N$. Finally, outputs

$$\rho_2 = (z, a)$$

- $BS_{fis.Derive}(st_U, \rho_2)$: given state $st_U$ and last message $\rho_2 = (z, a)$, sets $z' \leftarrow h \cdot h_1^a \cdot c \cdot h_2^a$, for $a \in S_a$, and checks $z^e \equiv z' \mod N$ given $e$ from $st_U$. Next, computes a $S_{fis}$ signature on $\bar{m}$ from the presignature $z$ via $y \leftarrow z \cdot g^{-r} \mod N$. Then, checks whether $\sigma_{fis} = (e, a, y)$ indeed forms a correct signature on $m$ via $S_{fis}.Verify(vk, m, \sigma_{fis}) = 1$. Next, generates a $BS_{fis}$ signature as follows. Sets $\bar{m} = H(m)$ and $(c_I, d_I) \leftarrow C_{RInt}.Commit(pp_I, (a, e - \bar{E}); r_I)$ for $r_I \leftarrow C_{RInt}.C_{rnd}$. Proves that $\sigma_{fis}$ verifies correctly via $\pi_{fis} \leftarrow \Pi_{fis}.Prove^{H_{fis}}(crs_{fis}, x_{fis}, w_{fis})$ for $x_{fis} = (pp_I, N, h_1, h_2, h, \bar{m}, c_I)$, $w_{fis} = (e, a, y, r_I, d_I)$. Outputs

$$\sigma = (\pi_{fis}, c_I).$$

- $BS_{fis.Verify}(bvk, m, \sigma)$: Given verification key $bvk$, message $m$, and signature $\sigma = (\pi_{fis}, c_I)$, computes $\bar{m} = H(m)$ and checks

$$\Pi_{fis}.Verify^{H_{fis}}(crs_{fis}, x_{fis}, \pi_{fis}),$$

$$\text{for } x_{fis} = (pp, N, h_1, h_2, h, \bar{m}, c_I).$$
<table><caption>Fig. 1: A signing session of BS<sub>fis</sub> for message m. We have (pp<sub>I</sub>, pp<sub>Z</sub>) = H<sub>pp</sub>(0), x<sub>gen</sub> = (N, 4, (h, h<sub>1</sub>, h<sub>2</sub>, g)), x<sub>ped</sub> = (pp, N, e, h<sub>2</sub>, g, c, c<sub>Z</sub>), w<sub>ped</sub> = (m&#773;, r, d<sub>Z</sub>), x<sub>fis</sub> = (pp<sub>I</sub>, N, h<sub>1</sub>, h<sub>2</sub>, h, m&#773;, c<sub>I</sub>), w<sub>fis</sub> = (e, a, y, r<sub>I</sub>, d<sub>I</sub>). If a check fails, the party aborts.</caption><thead><tr><th>Signer(bvk, bsk)</th><th>User(bvk, m)</th></tr></thead><tbody><tr><td></td><td>1: check Π<sub>gen</sub>.Verify<sup>H<sub>gen</sub></sup>(crs<sub>gen</sub>, x<sub>gen</sub>, π<sub>gen</sub>) = 1</td></tr><tr><td></td><td>2: m&#773; ← H(m)</td></tr><tr><td></td><td>3: r ← [0, S]</td></tr><tr><td></td><td>4: (c<sub>Z</sub>, d<sub>Z</sub>) ← C<sub>Z</sub>.Commit(pp<sub>Z</sub>, (m&#773;, r))</td></tr><tr><td></td><td>5: e ← H<sub>P</sub>(c<sub>Z</sub>)</td></tr><tr><td></td><td>6: c = h<sub>2</sub><sup>m&#773;</sup> · g<sup>re</sup> mod N</td></tr><tr><td></td><td>7: π<sub>ped</sub> ← Π<sub>ped</sub>.Prove<sup>H<sub>ped</sub></sup>(crs<sub>ped</sub>, x<sub>ped</sub>, w<sub>ped</sub>)</td></tr><tr><td></td><td>(c, c<sub>Z</sub>, π<sub>ped</sub>)</td></tr><tr><td>8: check Π<sub>ped</sub>.Verify<sup>H<sub>ped</sub></sup>(crs<sub>ped</sub>, x<sub>ped</sub>, π<sub>ped</sub>) = 1</td><td></td></tr><tr><td>9: e ← H<sub>P</sub>(c<sub>Z</sub>)</td><td></td></tr><tr><td>10: d ← e<sup>-1</sup> mod φ(N)</td><td></td></tr><tr><td>11: a ← H<sub>prf</sub>(K, c || c<sub>Z</sub>)</td><td></td></tr><tr><td>12: z' ← h · h<sub>1</sub><sup>a</sup> · c · h<sub>2</sub><sup>a</sup> mod N</td><td></td></tr><tr><td>13: z ← (z')<sup>d</sup> mod N</td><td></td></tr><tr><td></td><td>(z, a)</td></tr><tr><td>14: check z<sup>e</sup> ≡ z' mod N</td><td></td></tr><tr><td>15: check a ∈ S<sub>a</sub></td><td></td></tr><tr><td>16: y ← z · g<sup>-r</sup> mod N</td><td></td></tr><tr><td>17: check S<sub>fis</sub>.Verify(vk, m, (e, a, y)) = 1</td><td></td></tr><tr><td>18: r<sub>I</sub> ← C<sub>RInt</sub>.C<sub>rnd</sub></td><td></td></tr><tr><td>19: (c<sub>I</sub>, d<sub>I</sub>) ← C<sub>RInt</sub>.Commit(pp<sub>I</sub>, (a, e - E&#773;), r<sub>I</sub>)</td><td></td></tr><tr><td>20: π<sub>fis</sub> ← Π<sub>fis</sub>.Prove<sup>H<sub>fis</sub></sup>(crs<sub>fis</sub>, x<sub>fis</sub>, w<sub>fis</sub>)</td><td></td></tr><tr><td>21: return σ = (π<sub>fis</sub>, c<sub>I</sub>)</td><td></td></tr></tbody></table>

## 6.3 Blindness under Malicious Keys

Before proving that our scheme BS<sub>fis</sub> satisfies blindness under malicious keys, we state a lemma and its corollary that will be used in our proof:

**Lemma 2.** Let $\lambda \in \mathbb{N}$ and $N > 3$ be an odd natural number of bitlength polynomially large in $\lambda$. We consider $\mathbb{Z}_N^*$ and fix $\mathcal{G} = \langle g \rangle \subseteq \mathbb{Z}_N^*$ where $g \in \mathbb{Z}_N^*$. Given $e \leftarrow S_e$ where $S_e$ contains at least $\Omega(2^\lambda)$ primes, we have

$$ \Pr[\langle g^e \rangle \neq \mathcal{G} : e \leftarrow S_e] \leq \mathrm{negl}(\lambda) $$

where the probability is taken over the choice of e.

**Corollary 1.** Let $\lambda \in \mathbb{N}$ and $N > 3$ be an odd natural number of bitlength polynomially large in $\lambda$. We consider $\mathbb{Z}_N^*$ and fix $\mathcal{G} = \langle g \rangle \subseteq \mathbb{Z}_N^*$ where $g \in \mathbb{Z}_N^*$. Given $e \leftarrow S_e$ where $S_e$ contains at least $\Omega(2^\lambda)$ primes, with overwhelming probability over the choice of e

$$ \psi : \mathcal{G} \rightarrow \langle g^e \rangle \\ z \mapsto z^e \mod N $$

is a group isomorphism.
We defer the proofs to Appendix D.2. We now state the main theorem for blindness of $BS_{fis}$ followed by an overview. The full proof can be found in Appendix D.3.

**Theorem 3.** The scheme $BS_{fis}$ is blind under malicious keys following the subversion statistical adaptive soundness of $\Pi_{gen}$, the subversion zero-knowledge property of $\Pi_{fis}$, the computational hiding property of $C_{RInt}$, and the subversion zero-knowledge property of $\Pi_{ped}$.

*Proof Overview.* In the proof we use a sequence of games to transition from the blindness game as in Definition 3 with $coin = 0$ to the blindness game with $coin = 1$. To achieve this, we first employ the subversion zero-knowledge property of $\Pi_{fis}$ for simulating the proofs $\pi_{fis}$. Particularly, corollary 1, which ensures that with overwhelming probability the *presignature* $z$ is a unique correct $e$-th root of a masked $S_{fis}$ signature, together with the adaptive soundness of $\Pi_{gen}$ will guarantee that the derived signature $y$ will be a valid $S_{fis}$ signature in order to use the subversion zero-knowledge simulator of $\Pi_{fis}$. This allows us to change the commitment $c_I$ of the signature on $m_0$ to a commitment to 0, under the hiding property of $C_{RInt}$, which makes the signature independent of the signing session's exponents $e$ and $a$. We then to turn to exchanging the CRS of $\Pi_{ped}$ to a simulated one along with simulating the proof $\pi_{ped}$ using the subversion zero-knowledge property of $\Pi_{ped}$. We also rule out that the signer gave us a key with $\langle h_2 \rangle \neq \langle g \rangle$ via the adaptive soundness of $\Pi_{gen}$ as otherwise the Pedersen commitment would not be perfectly hiding. Combining the previous game hop with lemma 2 makes sure that with overwhelming probability over the choices of $e$ the commitment $c$ is Pedersen over $\langle g \rangle$ and its committed values are independent from $\pi_{ped}$. Thus $c$ can be switched to a uniformly random $c \leftarrow \langle g \rangle$ for the session where $m_0$ is getting signed. After the Pedersen commitment is independent of the message, we also switch the commitment $c_Z$ to be independent of the message using the hiding property of $C_Z$. We then use the an analogous series of games in the other direction to end up with the real game for $coin = 1$.

## 6.4 One-more Unforgeability

**Theorem 4.** If the strong RSA problem is hard, $H$, $H_P$, $H_{urs}$, and $H_{pp}$ are random oracles, $\Pi_{ped}$ is a NIZK with partial online-extractability, $C_Z$ is a perfectly binding commitment scheme, PRF is a pseudo-random function, $\Pi_{fis}$ is a NIZK with adaptive knowledge-soundness, and $C_{RInt}$ is a perfectly binding integer commitment scheme then $BS_{fis}$ is one-more unforgeable.

*Proof Overview.* For one-more unforgeability, we want to use similar techniques to generate signatures and solve the strong RSA problem as the scheme in Section 4.1. Our final reduction will do the following: It sets up the verification key for $S_{fis}$ as the reduction for the scheme in Section 4.1. In particular, this means guessing the format of the “forgery”. One guess whether the adversary re-uses a prime $e$ used also in a signing interaction with the signer or whether it picks a new $e$ which may or may not be a prime. This guess we denote by a bit $b$. In the case that the adversary re-uses the prime $e$, more guesses are made. The reduction guesses the index $j$ of which of the primes will be re-used. The other guess $b'$ concerns the choice of the signature randomness $a$, namely whether it holds that $a_j \neq a^*$ or $a_j + \bar{m}_j \neq a^* + \bar{m}^*$ where $\bar{m}$ is the hash of a message $m$. If $\bar{m}_j \neq \bar{m}^*$, at least one of the above will be the case. Analogous to the reduction for plain $S_{fis}$ signatures, the reduction manipulates the signature randomness $a_j$ and verification key in such a way that it can sign using exactly one choice of $a_j$ and solve the strong RSA problem for other choices of $a^*$.

To answer signing queries, it extracts the message and commitment randomness from the NIZK sent by the adversary in the first message of a signing interaction. It then signs the message using the alternate signing key and reapplies the randomness.

To obtain an $S_{fis}$ signature from the adversary, it uses the knowledge soundness extractor of $\Pi_{fis}$. It then solves the sRSA problem using the same strategy as the reduction described in Appendix B.2.
To apply this reduction we do game hops to arrive to a game where:

- The reduction can online-extract the hash of the message $\bar{m}$ and the random blinding factor $r$ used to generate the blinded message $c$. This we achieve by switching to the CRS that allows for extraction and by introducing extraction in a game.

- The reduction can be sure that in signing queries, the adversary uses an exponent $e$ for which the reduction has trapdoored its verification key. This we achieve through programming the hash oracle $H_P$ accordingly (as well as through online-extraction).
- The reduction needs to be able to obtain an actual fresh signature (like in the EUF-CMA game for the adapted Fischlin scheme from Section 4.1). This we achieve by applying the knowledge extractor of $\Pi_{fis}$.

- We need to be sure that the extracted signature is independent of the various signature simulation modes employed by the reduction (i.e. the choices of $b, b', j$). This is provided by employing a perfectly binding commitment to contain the signature.

- We make additional game hops to rule out corner cases such as collisions in the hash functions.

We refer to Appendix D.4 for a detailed proof.

## 6.5 Instantiation

We instantiate the primitives from Section 6.1 required for our blind signature $BS_{fis}$ as follows. For $C_{RInt}$, we use our construction from Section 5.1 which admits efficient opening proofs in zero-knowledge. For $\Pi_{gen}$, we use the construction from Appendix C.1 and for the PRF, an arbitrary choice is sufficient. It remains to instantiate $\Pi_{fis}$ and $\Pi_{ped}$. Our constructions are technically involved. We refer to Section 2 for a brief overview. For detailed constructions, we refer to Appendix E.

For our instantiation, we choose a standard RSA modulus of size 3072 bit for $\lambda = 128$. In total, we obtain blind signatures secure under DDH and sRSA of size 4.28 KB with 10.98 KB communication.

## Acknowledgements

We thank Henry Bambury for insightful comments on the Huxley's bounds of the number of primes in a given interval. We also thank the anonymous reviewers for helpful feedback and suggestions. This work was supported in part by the French ANR Project ANR-19-CE39-0011 PRESTO.

## References

1. Abe, M.: A secure three-move blind signature scheme for polynomially many signatures. In: Pfitzmann, B. (ed.) EUROCRYPT 2001. LNCS, vol. 2045, pp. 136–151. Springer, Heidelberg (May 2001). https://doi.org/10.1007/3-540-44987-6_9

2. Abe, M., Ambrona, M., Bogdanov, A., Ohkubo, M., Rosen, A.: Acyclicity programming for sigma-protocols. In: Nissim, K., Waters, B. (eds.) TCC 2021, Part I. LNCS, vol. 13042, pp. 435–465. Springer, Heidelberg (Nov 2021). https://doi.org/10.1007/978-3-030-90459-3_15

3. Abe, M., Fuchsbauer, G., Groth, J., Haralambiev, K., Ohkubo, M.: Structure-preserving signatures and commitments to group elements. Journal of Cryptology 29(2), 363–421 (Apr 2016). https://doi.org/10.1007/s00145-014-9196-7

4. Abe, M., Jutla, C.S., Ohkubo, M., Roy, A.: Improved (almost) tightly-secure simulation-sound QA-NIZK with applications. In: Peyrin, T., Galbraith, S. (eds.) ASIACRYPT 2018, Part I. LNCS, vol. 11272, pp. 627–656. Springer, Heidelberg (Dec 2018). https://doi.org/10.1007/978-3-030-03326-2_21

5. Abe, M., Ohkubo, M.: A framework for universally composable non-committing blind signatures. In: Matsui, M. (ed.) ASIACRYPT 2009. LNCS, vol. 5912, pp. 435–450. Springer, Heidelberg (Dec 2009). https://doi.org/10.1007/978-3-642-10366-7_26

6. Abe, M., Okamoto, T.: Provably secure partially blind signatures. In: Bellare, M. (ed.) CRYPTO 2000. LNCS, vol. 1880, pp. 271–286. Springer, Heidelberg (Aug 2000). https://doi.org/10.1007/3-540-44598-6_17

7. Agrawal, S., Kirshanova, E., Stehlé, D., Yadav, A.: Practical, round-optimal lattice-based blind signatures. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022. pp. 39–53. ACM Press (Nov 2022). https://doi.org/10.1145/3548606.3560650

8. Amjad, G., Yeo, K., Yung, M.: Rsa blind signatures with public metadata. Cryptology ePrint Archive, Paper 2023/1199 (2023). https://eprint.iacr.org/2023/1199, https://eprint.iacr.org/2023/1199

9. Attema, T., Cramer, R.: Compressed $\Sigma$-protocol theory and practical application to plug & play secure algorithmics. In: Micciancio, D., Ristenpart, T. (eds.) CRYPTO 2020, Part III. LNCS, vol. 12172, pp. 513–543. Springer, Heidelberg (Aug 2020). https://doi.org/10.1007/978-3-030-56877-1_18

10. Attema, T., Fehr, S., Kloos, M.: Fiat-shamir transformation of multi-round interactive proofs. In: Kiltz, E., Vaikuntanathan, V. (eds.) TCC 2022, Part I. LNCS, vol. 13747, pp. 113–142. Springer, Heidelberg (Nov 2022). https://doi.org/10.1007/978-3-031-22318-1_5
11. Barreto, P.S., Lynn, B., Scott, M.: Constructing elliptic curves with prescribed embedding degrees. In: Security in Communication Networks: Third International Conference, SCN 2002 Amalfi, Italy, September 11–13, 2002 Revised Papers 3. pp. 257–267. Springer (2003)

12. Bellare, M., Fuchsbauer, G., Scafuro, A.: NIZKs with an untrusted CRS: Security in the face of parameter subversion. In: Cheon, J.H., Takagi, T. (eds.) ASIACRYPT 2016, Part II. LNCS, vol. 10032, pp. 777–804. Springer, Heidelberg (Dec 2016). https://doi.org/10.1007/978-3-662-53890-6_26

13. Bellare, M., Namprempre, C., Pointcheval, D., Semanko, M.: The one-more-RSA-inversion problems and the security of Chaum’s blind signature scheme. Journal of Cryptology 16(3), 185–215 (Jun 2003). https://doi.org/10.1007/s00145-002-0120-1

14. Bellare, M., Neven, G.: Multi-signatures in the plain public-key model and a general forking lemma. In: Juels, A., Wright, R.N., De Capitani di Vimercati, S. (eds.) ACM CCS 2006. pp. 390–399. ACM Press (Oct / Nov 2006). https://doi.org/10.1145/1180405.1180453

15. Benhamouda, F., Krenn, S., Lyubashevsky, V., Pietrzak, K.: Efficient zero-knowledge proofs for commitments from learning with errors over rings. In: Pernul, G., Ryan, P.Y.A., Weippl, E.R. (eds.) ESORICS 2015, Part I. LNCS, vol. 9326, pp. 305–325. Springer, Heidelberg (Sep 2015). https://doi.org/10.1007/978-3-319-24174-6_16

16. Benhamouda, F., Lepoint, T., Loss, J., Orrù, M., Raykova, M.: On the (in)security of ROS. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 33–53. Springer, Heidelberg (Oct 2021). https://doi.org/10.1007/978-3-030-77870-5_2

17. Blazy, O., Fuchsbauer, G., Pointcheval, D., Vergnaud, D.: Signatures on randomizable ciphertexts. In: Catalano, D., Fazio, N., Gennaro, R., Nicolosi, A. (eds.) PKC 2011. LNCS, vol. 6571, pp. 403–422. Springer, Heidelberg (Mar 2011). https://doi.org/10.1007/978-3-642-19379-8_25

18. Blazy, O., Fuchsbauer, G., Pointcheval, D., Vergnaud, D.: Short blind signatures. Journal of computer security 21(5), 627–661 (2013)

19. Blazy, O., Pointcheval, D., Vergnaud, D.: Compact round-optimal partially-blind signatures. In: Visconti, I., Prisco, R.D. (eds.) SCN 12. LNCS, vol. 7485, pp. 95–112. Springer, Heidelberg (Sep 2012). https://doi.org/10.1007/978-3-642-32928-9_6

20. Boldyreva, A.: Threshold signatures, multisignatures and blind signatures based on the gap-Diffie-Hellman-group signature scheme. In: Desmedt, Y. (ed.) PKC 2003. LNCS, vol. 2567, pp. 31–46. Springer, Heidelberg (Jan 2003). https://doi.org/10.1007/3-540-36288-6_3

21. Brands, S.: Untraceable off-line cash in wallets with observers (extended abstract). In: Stinson, D.R. (ed.) CRYPTO'93. LNCS, vol. 773, pp. 302–318. Springer, Heidelberg (Aug 1994). https://doi.org/10.1007/3-540-48329-2_26

22. Bünz, B., Bootle, J., Boneh, D., Poelstra, A., Wuille, P., Maxwell, G.: Bulletproofs: Short proofs for confidential transactions and more. In: 2018 IEEE Symposium on Security and Privacy. pp. 315–334. IEEE Computer Society Press (May 2018). https://doi.org/10.1109/SP.2018.00020

23. Buser, M., Dowsley, R., Esgin, M., Gritti, C., Kasra Kermanshahi, S., Kuchta, V., Legrow, J., Liu, J., Phan, R., Sakzad, A., Steinfeld, R., Yu, J.: A survey on exotic signatures for post-quantum blockchain: Challenges and research directions. ACM Comput. Surv. 55(12) (mar 2023). https://doi.org/10.1145/3572771, https://doi.org/10.1145/3572771

24. Camenisch, J., Lysyanskaya, A.: A signature scheme with efficient protocols. In: Cimato, S., Galdi, C., Persiano, G. (eds.) SCN 02. LNCS, vol. 2576, pp. 268–289. Springer, Heidelberg (Sep 2003). https://doi.org/10.1007/3-540-36413-7_20

25. Chairattana-Apirom, R., Hanzlik, L., Loss, J., Lysyanskaya, A., Wagner, B.: PI-cut-choo and friends: Compact blind signatures via parallel instance cut-and-choose and more. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part III. LNCS, vol. 13509, pp. 3–31. Springer, Heidelberg (Aug 2022). https://doi.org/10.1007/978-3-031-15982-4_1

26. Chairattana-Apirom, R., Tessaro, S., Zhu, C.: Pairing-free blind signatures from cdh assumptions. Cryptology ePrint Archive, Paper 2023/1780 (2023), https://eprint.iacr.org/2023/1780, https://eprint.iacr.org/2023/1780

27. Chator, A., Green, M., Tiwari, P.R.: Sok: Privacy-preserving signatures. Cryptology ePrint Archive, Paper 2023/1039 (2023), https://eprint.iacr.org/2023/1039, https://eprint.iacr.org/2023/1039

28. Chaum, D.: Blind signatures for untraceable payments. In: Chaum, D., Rivest, R.L., Sherman, A.T. (eds.) CRYPTO'82. pp. 199–203. Plenum Press, New York, USA (1982)

29. Chaum, D.: Security without identification: Transaction systems to make big brother obsolete. Commun. ACM 28(10), 1030–1044 (oct 1985). https://doi.org/10.1145/4372.4373, https://doi.org/10.1145/4372.4373

30. Chaum, D.: Elections with unconditionally-secret ballots and disruption equivalent to breaking RSA. In: Günther, C.G. (ed.) EUROCRYPT'88. LNCS, vol. 330, pp. 177–182. Springer, Heidelberg (May 1988). https://doi.org/10.1007/3-540-45961-8_15

31. Chaum, D., Fiat, A., Naor, M.: Untraceable electronic cash. In: Goldwasser, S. (ed.) CRYPTO'88. LNCS, vol. 403, pp. 319–327. Springer, Heidelberg (Aug 1990). https://doi.org/10.1007/0-387-34799-2_25
32. Couteau, G., Goudarzi, D., Kloos, M., Reichle, M.: Sharp: Short relaxed range proofs. In: Yin, H., Stavrou, A., Cremers, C., Shi, E. (eds.) ACM CCS 2022. pp. 609–622. ACM Press (Nov 2022). https://doi.org/10.1145/3548606.3560628

33. Couteau, G., Kloos, M., Lin, H., Reichle, M.: Efficient range proofs with transparent setup from bounded integer commitments. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part III. LNCS, vol. 12698, pp. 247–277. Springer, Heidelberg (Oct 2021). https://doi.org/10.1007/978-3-030-77883-5_9

34. Couteau, G., Peters, T., Pointcheval, D.: Removing the strong RSA assumption from arguments over the integers. In: Coron, J.S., Nielsen, J.B. (eds.) EUROCRYPT 2017, Part II. LNCS, vol. 10211, pp. 321–350. Springer, Heidelberg (Apr / May 2017). https://doi.org/10.1007/978-3-319-56614-6_11

35. Cramer, R., Shoup, V.: Signature schemes based on the strong RSA assumption. In: Motiwalla, J., Tsudik, G. (eds.) ACM CCS 99. pp. 46–51. ACM Press (Nov 1999). https://doi.org/10.1145/319709.319716

36. Crites, E., Komlo, C., Maller, M., Tessaro, S., Zhu, C.: Snowblind: A threshold blind signature in pairing-free groups. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023. pp. 710–742. Springer Nature Switzerland, Cham (2023)

37. del Pino, R., Katsumata, S.: A new framework for more efficient round-optimal lattice-based (partially) blind signature via trapdoor sampling. In: Dodis, Y., Shrimpton, T. (eds.) CRYPTO 2022, Part II. LNCS, vol. 13508, pp. 306–336. Springer, Heidelberg (Aug 2022). https://doi.org/10.1007/978-3-031-15979-4_11

38. Denis, F., Jacobs, F., Wood, C.A.: RSA Blind Signatures. Internet-Draft draft-irtf-cfrg-rsa-blind-signatures-02, Internet Engineering Task Force (Aug 2021), https://datatracker.ietf.org/doc/draft-irtf-cfrg-rsa-blind-signatures/02/, work in Progress

39. ElGamal, T.: A public key cryptosystem and a signature scheme based on discrete logarithms. In: Blakley, G.R., Chaum, D. (eds.) CRYPTO’84. LNCS, vol. 196, pp. 10–18. Springer, Heidelberg (Aug 1984)

40. Fiat, A., Shamir, A.: How to prove yourself: Practical solutions to identification and signature problems. In: Odlyzko, A.M. (ed.) CRYPTO’86. LNCS, vol. 263, pp. 186–194. Springer, Heidelberg (Aug 1987). https://doi.org/10.1007/3-540-47721-7_12

41. Fischlin, M.: The Cramer-Shoup strong-RSA signature scheme revisited. In: Desmedt, Y. (ed.) PKC 2003. LNCS, vol. 2567, pp. 116–129. Springer, Heidelberg (Jan 2003). https://doi.org/10.1007/3-540-36288-6_9

42. Fischlin, M.: Round-optimal composable blind signatures in the common reference string model. In: Dwork, C. (ed.) CRYPTO 2006. LNCS, vol. 4117, pp. 60–77. Springer, Heidelberg (Aug 2006). https://doi.org/10.1007/11818175_4

43. Fischlin, M., Schröder, D.: On the impossibility of three-move blind signature schemes. In: Gilbert, H. (ed.) EUROCRYPT 2010. LNCS, vol. 6110, pp. 197–215. Springer, Heidelberg (May / Jun 2010). https://doi.org/10.1007/978-3-642-13190-5_10

44. Fuchsbauer, G.: Subversion-zero-knowledge SNARKs. In: Abdalla, M., Dahab, R. (eds.) PKC 2018, Part I. LNCS, vol. 10769, pp. 315–347. Springer, Heidelberg (Mar 2018). https://doi.org/10.1007/978-3-319-76578-5_11

45. Fuchsbauer, G., Hanser, C., Kamath, C., Slamanig, D.: Practical round-optimal blind signatures in the standard model from weaker assumptions. In: Zikas, V., De Prisco, R. (eds.) SCN 16. LNCS, vol. 9841, pp. 391–408. Springer, Heidelberg (Aug / Sep 2016). https://doi.org/10.1007/978-3-319-44618-9_21

46. Fuchsbauer, G., Hanser, C., Slamanig, D.: Practical round-optimal blind signatures in the standard model. In: Gennaro, R., Robshaw, M.J.B. (eds.) CRYPTO 2015, Part II. LNCS, vol. 9216, pp. 233–253. Springer, Heidelberg (Aug 2015). https://doi.org/10.1007/978-3-662-48000-7_12

47. Fuchsbauer, G., Plouviez, A., Seurin, Y.: Blind schnorr signatures and signed ElGamal encryption in the algebraic group model. In: Canteaut, A., Ishai, Y. (eds.) EUROCRYPT 2020, Part II. LNCS, vol. 12106, pp. 63–95. Springer, Heidelberg (May 2020). https://doi.org/10.1007/978-3-030-45724-2_3

48. Fuchsbauer, G., Wolf, M.: Concurrently secure blind schnorr signatures. Cryptology ePrint Archive, Pa-per 2022/1676 (2022), https://eprint.iacr.org/2022/1676, https://eprint.iacr.org/2022/1676

49. Fujioka, A., Okamoto, T., Ohta, K.: A practical secret voting scheme for large scale elections. In: Seberry, J., Zheng, Y. (eds.) AUSCRYPT’92. LNCS, vol. 718, pp. 244–251. Springer, Heidelberg (Dec 1993). https://doi.org/10.1007/3-540-57220-1_66

50. Garg, S., Gupta, D.: Efficient round optimal blind signatures. In: Nguyen, P.Q., Oswald, E. (eds.) EUROCRYPT 2014. LNCS, vol. 8441, pp. 477–495. Springer, Heidelberg (May 2014). https://doi.org/10.1007/978-3-642-55220-5_27

51. Garg, S., Rao, V., Sahai, A., Schröder, D., Unruh, D.: Round optimal blind signatures. In: Rogaway, P. (ed.) CRYPTO 2011. LNCS, vol. 6841, pp. 630–648. Springer, Heidelberg (Aug 2011). https://doi.org/10.1007/978-3-642-22792-9_36

52. Ghadafi, E.: Efficient round-optimal blind signatures in the standard model. In: Kiayias, A. (ed.) FC 2017. LNCS, vol. 10322, pp. 455–473. Springer, Heidelberg (Apr 2017)
53. Google: VPN Google One. https://one.google.com/about/vpn/howitworks

54. Hanzlik, L., Loss, J., Wagner, B.: Rai-choo! evolving blind signatures to the next level. EUROCRYPT 2023 (2023), https://eprint.iacr.org/2022/1350, https://eprint.iacr.org/2022/1350

55. Hauck, E., Kiltz, E., Loss, J.: A modular treatment of blind signatures from identification schemes. In: Ishai, Y., Rijmen, V. (eds.) EUROCRYPT 2019, Part III. LNCS, vol. 11478, pp. 345–375. Springer, Heidelberg (May 2019). https://doi.org/10.1007/978-3-030-17659-4_12

56. Hazay, C., Katz, J., Koo, C.Y., Lindell, Y.: Concurrently-secure blind signatures without random oracles or setup assumptions. In: Vadhan, S.P. (ed.) TCC 2007. LNCS, vol. 4392, pp. 323–341. Springer, Heidelberg (Feb 2007). https://doi.org/10.1007/978-3-540-70936-7_18

57. Heath-Brown, D.: The number of primes in a short interval. Journal für die reine und angewandte Mathematik **389**, 22–63 (1988), http://eudml.org/doc/153047

58. Heath-Brown, R.: The Differences Between Consecutive Primes, V. International Mathematics Research Notices **2021**(22), 17514–17562 (12 2019). https://doi.org/10.1093/imrn/rnz295, https://doi.org/10.1093/imrn/rnz295

59. Hendrickson, S., Iyengar, J., Pauly, T., Valdez, S., Wood, C.A.: Private Access Tokens. Internet-Draft draft-private-access-tokens-01, Internet Engineering Task Force (Oct 2021), https://datatracker.ietf.org/doc/draft-private-access-tokens/01/, work in Progress

60. Huxley, M.: On the difference between consecutive primes. Inventiones mathematicae **15**, 164–170 (1971/72), http://eudml.org/doc/142126

61. Juels, A., Luby, M., Ostrovsky, R.: Security of blind digital signatures (extended abstract). In: Kaliski Jr., B.S. (ed.) CRYPTO’97. LNCS, vol. 1294, pp. 150–164. Springer, Heidelberg (Aug 1997). https://doi.org/10.1007/BFb0052233

62. Kastner, J., Loss, J., Xu, J.: The abe-okamoto partially blind signature scheme revisited. In: Agrawal, S., Lin, D. (eds.) ASIACRYPT 2022, Part IV. LNCS, vol. 13794, pp. 279–309. Springer, Heidelberg (Dec 2022). https://doi.org/10.1007/978-3-031-22972-5_10

63. Kastner, J., Loss, J., Xu, J.: On pairing-free blind signature schemes in the algebraic group model. In: Hanaoka, G., Shikata, J., Watanabe, Y. (eds.) PKC 2022, Part II. LNCS, vol. 13178, pp. 468–497. Springer, Heidelberg (Mar 2022). https://doi.org/10.1007/978-3-030-97131-1_16

64. Katsumata, S., Lai, Y.F., LeGrow, J.T., Qin, L.: Csi-otter: Isogeny-based (partially) blind signatures from the class group action with a twist. In: Handschuh, H., Lysyanskaya, A. (eds.) Advances in Cryptology – CRYPTO 2023. pp. 729–761. Springer Nature Switzerland, Cham (2023)

65. Katsumata, S., Nishimaki, R., Yamada, S., Yamakawa, T.: Round-optimal blind signatures in the plain model from classical and quantum standard assumptions. In: Canteaut, A., Standaert, F.X. (eds.) EUROCRYPT 2021, Part I. LNCS, vol. 12696, pp. 404–434. Springer, Heidelberg (Oct 2021). https://doi.org/10.1007/978-3-030-77870-5_15

66. Katsumata, S., Reichle, M., Sakai, Y.: Practical round-optimal blind signatures in the rom from standard assumptions. to appear in Asiacrypt (2023), https://eprint.iacr.org/2023/1447, https://eprint.iacr.org/2023/1447

67. Katz, J., Loss, J., Rosenberg, M.: Boosting the security of blind signature schemes. In: Tibouchi, M., Wang, H. (eds.) ASIACRYPT 2021, Part IV. LNCS, vol. 13093, pp. 468–492. Springer, Heidelberg (Dec 2021). https://doi.org/10.1007/978-3-030-92068-5_16

68. Lindell, Y.: Lower bounds and impossibility results for concurrent self composition. Journal of Cryptology **21**(2), 200–249 (Apr 2008). https://doi.org/10.1007/s00145-007-9015-5

69. Lysyanskaya, A.: Security analysis of rsa-bssa (2023), https://eprint.iacr.org/2023/895

70. Meiklejohn, S., Shacham, H., Freeman, D.M.: Limitations on transformations from composite-order to prime-order groups: The case of round-optimal blind signatures. In: Abe, M. (ed.) ASIACRYPT 2010. LNCS, vol. 6477, pp. 519–538. Springer, Heidelberg (Dec 2010). https://doi.org/10.1007/978-3-642-17373-8_30

71. Naor, M.: On cryptographic assumptions and challenges (invited talk). In: Boneh, D. (ed.) CRYPTO 2003. LNCS, vol. 2729, pp. 96–109. Springer, Heidelberg (Aug 2003). https://doi.org/10.1007/978-3-540-45146-4_6

72. Nishimaki, R.: Equipping public-key cryptographic primitives with watermarking (or: A hole is to watermark). In: Pass, R., Pietrzak, K. (eds.) TCC 2020, Part I. LNCS, vol. 12550, pp. 179–209. Springer, Heidelberg (Nov 2020). https://doi.org/10.1007/978-3-030-64375-1_7

73. Okamoto, T.: Provably secure and practical identification schemes and corresponding signature schemes. In: Brickell, E.F. (ed.) CRYPTO’92. LNCS, vol. 740, pp. 31–53. Springer, Heidelberg (Aug 1993). https://doi.org/10.1007/3-540-48071-4_3

74. Okamoto, T., Ohta, K.: Universal electronic cash. In: Feigenbaum, J. (ed.) CRYPTO’91. LNCS, vol. 576, pp. 324–337. Springer, Heidelberg (Aug 1992). https://doi.org/10.1007/3-540-46766-1_27

75. Pass, R.: Limits of provable security from standard assumptions. In: Fortnow, L., Vadhan, S.P. (eds.) 43rd ACM STOC. pp. 109–118. ACM Press (Jun 2011). https://doi.org/10.1145/1993636.1993652
76. Pointcheval, D.: Strengthened security for blind signatures. In: Nyberg, K. (ed.) EUROCRYPT'98. LNCS, vol. 1403, pp. 391-405. Springer, Heidelberg (May / Jun 1998). https://doi.org/10.1007/BFb0054141

77. Pointcheval, D., Stern, J.: Security arguments for digital signatures and blind signatures. Journal of Cryptology 13(3), 361-396 (Jun 2000). https://doi.org/10.1007/s001450010003

78. Schnorr, C.P.: Security of blind discrete log signatures against interactive attacks. In: Qing, S., Okamoto, T., Zhou, J. (eds.) ICICS 01. LNCS, vol. 2229, pp. 1-12. Springer, Heidelberg (Nov 2001)

79. Seo, J.H., Cheon, J.H.: Beyond the limitation of prime-order bilinear groups, and round optimal blind signatures. In: Cramer, R. (ed.) TCC 2012. LNCS, vol. 7194, pp. 133-150. Springer, Heidelberg (Mar 2012). https://doi.org/10.1007/978-3-642-28914-9_8

80. Tessaro, S., Zhu, C.: Short pairing-free blind signatures with exponential security. In: Dunkelman, O., Dziembowski, S. (eds.) EUROCRYPT 2022, Part II. LNCS, vol. 13276, pp. 782-811. Springer, Heidelberg (May / Jun 2022). https://doi.org/10.1007/978-3-031-07085-3_27

81. Wagner, D.: A generalized birthday problem. In: Yung, M. (ed.) CRYPTO 2002. LNCS, vol. 2442, pp. 288-303. Springer, Heidelberg (Aug 2002). https://doi.org/10.1007/3-540-45708-9_19

82. Nist announces additional digital signature candidates for the pqc standardization process. https://csrc.nist.gov/projects/pqc-dig-sig (2023), accessed: 2023-10-06

83. mcl-wasm library for pairings. https://github.com/herumi/mcl-wasm (2023), accessed: 2023-10-02

84. PCM: Click fraud prevention and attribution sent to advertiser. https://webkit.org/blog/11940/pcm-click-fraud-prevention-and-attribution-sent-to-advertiser/ (2022), accessed: 2023-10-06

85. Supported ssh algorithms. https://privx docs.ssh.com/docs/supported-ssh-key-exchange-algorithms (2022), accessed: 2023-10-06

86. Yi, X., Lam, K.Y.: A new blind ECDSA scheme for bitcoin transaction anonymity. In: Galbraith, S.D., Russello, G., Susilo, W., Gollmann, D., Kirda, E., Liang, Z. (eds.) ASIACCS 19. pp. 613-620. ACM Press (Jul 2019). https://doi.org/10.1145/3321705.3329816
# Supplementary Material

## A Full Preliminaries

### A.1 Notation

Let $\lambda \in \mathbb{N}$ be the security parameter. A probabilistic polynomial time (PPT) algorithm $\mathcal{A}$ runs in time polynomial in the (implicit) security parameter $\lambda$. We write $\text{Time}(\mathcal{A})$ for the runtime of $\mathcal{A}$. A function $f(\lambda)$ is negligible in $\lambda$ if it is $O(\lambda^{-c})$ for every $c \in \mathbb{N}$. We write $f = \text{negl}(\lambda)$ for short. Similarly, we write $f = \text{poly}(\lambda)$ if $f(\lambda)$ is a polynomial with variable $\lambda$. If $D$ is a probability distribution, $x \leftarrow D$ means that $x$ is sampled from $D$ and if $S$ is a set, $x \leftarrow S$ means that $x$ is sampled uniformly and independently at random from $S$. We also write $|S|$ for the cardinality of set $S$. Further, we write $D_0 \stackrel{c}{\approx} D_1$ for distributions $D_0, D_1$, if for all PPT adversaries $\mathcal{A}$, we have $|\text{Pr}[x_0 \leftarrow D_0 : \mathcal{A}(1^{\lambda}, x_0) = 1]| - \text{Pr}[x_1 \leftarrow D_1 : \mathcal{A}(1^{\lambda}, x_1) = 1]| = \text{negl}(\lambda)$. Similarly, we write $D_0 \stackrel{s}{\approx} D_1$ if the above holds even for unbounded adversaries. For some PPT algorithm $\mathcal{A}$, we write $\mathcal{A}^{\mathcal{O}}$ if $\mathcal{A}$ has oracle access to the oracle $\mathcal{O}$. If $\mathcal{A}$ performs some check, and the check fails, we assume that $\mathcal{A}$ outputs $\perp$ immediately. Generally, we assume that adversaries are implicitly stateful.

We denote with $[n]$ the set $\{1, \dots, n\}$ for $n \in \mathbb{N}$. We write $\mathbb{P}$ for the set of primes and $\mathbb{P}_I$ for the set of primes in the interval $I$. For some odd prime $p$, we use the representatives $\{-\frac{p-1}{2}, \dots, \frac{p-1}{2}\}$ for $\mathbb{Z}_p$. For a group $\mathbb{G}$ we write $\text{ord}(\mathbb{G})$ to denote the order of $\mathbb{G}$ and unless stated otherwise we write $\mathbb{G}$ with additive notation. We denote by $\text{QR}_N = \{a \in \mathbb{Z}_N^* : \exists b \in \mathbb{Z}_N^*, b^2 \equiv a \bmod N\}$ the quadratic residues $\bmod N$. For some $N \in \mathbb{N}$, the group $\text{QR}_N$ is a cyclic subgroup of $\mathbb{Z}_N^*$ and we denote by $\text{Gen}(\text{QR}_N)$ the set of generators of $\text{QR}_N$. We recall some properties of $\text{QR}_N$.

**Lemma 3 (Proposition 1, [34]).** Let $\lambda \in \mathbb{N}$ and $(N, P, Q) \leftarrow \text{GenRSA}(1^{\lambda})$. Considering $\text{QR}_N$, the following holds:

- The group $\text{QR}_N$ is cyclic of order $P'Q'$ where $P = 2P' + 1$ and $Q = 2Q' + 1$.

- $-1 \notin \text{QR}_N$.

- Any square $h \in \text{QR}_N$ has excatly four roots, among which there is exactly one square.

- For any element $h \in \text{QR}_N$, finding roots of $h$ is equivalent to factoring $N$.

- For $g, h \leftarrow \text{QR}_N$, finding $a, b \in \mathbb{N} \setminus \{0\}$ such that $g^a \equiv h^b \bmod N$ is equivalent to factoring $N$.

- For any $e \in \mathbb{N}$ coprime with $\phi(N)$ and $y \in \mathbb{Z}_N^*$, finding $x, e' \in \mathbb{N}$ such that $x^e \equiv y^{e'} \bmod N$ is equivalent to finding an $e$-th root of $y$ in $\mathbb{Z}_N^*$.

### A.2 Probability

**Rejection Sampling.** Let $V, L \in \mathbb{N}$. We define uniform rejection sampling for the interval $[0, V]$ with masking overhead $L$ as in [32]. Let $v \in [0, V]$. To mask $v$ additively with a mask $\mu$ via rejection sampling, perform the following steps.

1. Draw a random mask $\mu \leftarrow [0, (V+1)L]$.

2. Abort if $v + \mu \notin [V, (V+1)L]$.

3. Output $w = v + \mu$.

The value $w$ is uniform over $[V, (V+1)L]$ conditioned on no abort and the abort probability is at most $1/L$. This is easy to see as it is a requirement for the abort that either

**Noise Flooding.** Let $V, L \in \mathbb{N}$. We define noise flooding for the interval $[-V, V]$ with masking overhead $L = 2^{\lambda}$. Let $v \in [-V, V]$. To mask $v$ additively with a mask $\mu$ via noise flooding, output $w = v + \mu$, where $\mu \leftarrow [0, VL]$ is sampled at random. The value $w$ is distributed close to uniform over $[0, VL]$ with statistical distance at most $1/L = \text{negl}(\lambda)$.
**Forking Lemma.** We state here a version of Forking Lemma [77, 14] that fits our usage of it.

**Lemma 4 (Lemma 1, [2]).** Let $H$ be a set and let $F: H^q \to [q]$ be a possibly random function. For every $\vec{h} \in H^q$, let $E(\vec{h})$ be a probability event. The probability that when sampling $k$ vectors $\vec{h}_1, \dots, \vec{h}_k$ uniformly and independently at random (conditioned that vectors are identical on their first $F(\vec{h}_1)$ components), $E(\vec{h}_i)$ happens for all $i \in [k]$ and $F(\vec{h}_1) = F(\vec{h}_2) = \dots = F(\vec{h}_k)$, is at least $\delta(E)^k/q^{k-1}$, where $\delta(E) := \Pr[\vec{h} \leftarrow H^q : E(\vec{h})]$.

### A.3 Assumptions

**Groups and RSA.** Let $\text{GenG}$ be a PPT algorithm that on input $1^\lambda$ and prime order $p$, outputs (a description of) a group $G \leftarrow \text{GenG}(1^\lambda)$ of order $p$. We generally use additive notations for prime order groups and capital letters for elements. Also, we assume that given the description, group operations and membership tests are efficient. We write $g \leftarrow G$ for drawing elements from some group $G$ at random. In the following, we assume that prime order groups are setup with $\text{GenG}$ implicitly.

Let $\text{GenRSA}$ be a PPT algorithm that on input $1^\lambda$ outputs $(N, P, Q) \leftarrow \text{GenRSA}(1^\lambda)$ such that $N = P \cdot Q$ with $P, Q \in \mathbb{P}$, where $P = 2P' + 1$ and $Q = 2Q' + 1$ are strong primes (i.e., $P', Q'$ are also primes). We assume that $P', Q' > 2^{\lambda+1}$.

Before recalling some standard hardness assumptions, let us recall the following well-known lemma.

**Lemma 5.** Given $x, y \in \mathbb{Z}_N^*$ with $a, b \in \mathbb{Z}$ such that $x^a = y^b$ and $\gcd(a, b) = 1$, one can efficiently compute $\bar{x} \in \mathbb{Z}_N^*$ such that $\bar{x}^a = y$.

**Remark 3.** We need the following well-known fact. Let $G$ be a group and let $G \leftarrow G$ be a random element from $G$. Let $S \in \mathbb{N}$. We consider the problem of distinguishing $zG$, where $z \leftarrow [0, S]$, from $\tilde{z}G$ where $\tilde{z} \leftarrow \mathbb{Z}_{\text{ord}(G)}$.

If the order $p$ of the group $G$ is known, then the distinguishing probability is 0 for $S = p - 1$. If only an upper bound $U$ on the order is known, then the distinguishing probability is upper bounded by $1/L$ for $S = L \cdot U$. For the latter, we set $L = 2^\lambda$ throughout to obtain negligible distinguishing probability.

Next, we recall the definition of a relaxed DLOG-relation from [32] (for the hidden order group $QR_N$).

**Definition 7 ((D, ℓ)-relaxed DLOG-relation).** Let $(N, P, Q) \leftarrow \text{GenRSA}(1^\lambda)$, $D, \ell \in \mathbb{N}$, and $\vec{g} = (g_0, \dots, g_\ell) \in QR_N^{\ell+1}$. Define the $(D, \ell)$-relaxed DLOG relation with regards to $\vec{g}$ as

$$R_{D,\ell}(\vec{g}) = \left\{ (c, d, \{x_i\}_{i=1}^\ell) \mid \begin{array}{l} c^d = \prod_{i=0}^\ell g_i^{x_i} \wedge \exists i: \frac{x_i}{d} \notin \mathbb{Z} \\ \wedge d \in [0, D] \wedge x_i \in \mathbb{Z} \end{array} \right\}$$

We define the advantage of $\mathcal{A}$ against the hardness of the $(D, \ell)$-relaxed DLOG-relation as

$$\text{Adv}_{(D, \ell), \mathcal{A}}^{\text{rel-dlog}}(\lambda) := \Pr \left[ \begin{array}{l} (N, P, Q) \leftarrow \text{GenRSA}(1^\lambda); g_0, \dots, g_\ell \leftarrow \text{Gen}(QR_N); \\ (c, d, x_0, \dots, x_\ell) \leftarrow \mathcal{A}(N, g_0, \dots, g_\ell): \\ (c, d, x_0, \dots, x_\ell) \in R_{D, \ell}(\vec{g}) \end{array} \right].$$

The following lemma is a simplification of Lemma A.13 of [32] sufficient for our purpose. Note that $\text{ord}(QR_N) = P'Q'$ and we assume that $P', Q' > 2^{\lambda+1}$.

**Lemma 6.** Let $D \le 2^{\lambda+1}$ and $\ell = \text{poly}(\lambda)$. For every PPT adversary $\mathcal{A}$ we have that $\text{Adv}_{(D, \ell), \mathcal{A}}^{\text{rel-dlog}}(\lambda) = \text{negl}(\lambda)$ under the strong RSA assumption.

**Definition 8 (Decisional Diffie-Hellman).** In a cyclic group $G$ of prime order $p$, which are set up w.r.t a security parameter $\lambda \in \mathbb{N}$, the Decisional Diffie-Hellman (DDH) assumption in $G$ holds if for all PPT adversary $\mathcal{A}$ the advantage

$$|\Pr[G \leftarrow G; a, b \leftarrow \mathbb{Z}_p : \mathcal{A}(G, aG, bG, abG) = 1| \\ - \Pr[G \leftarrow G; a, b, c \leftarrow \mathbb{Z}_p : \mathcal{A}(G, aG, bG, cG) = 1|$$

is negligible in $\lambda$.
**Definition 9 (Strong RSA).** Let $\lambda \in \mathbb{N}$. The strong RSA (sRSA) assumption holds if for all PPT $\mathcal{A}$ the advantage

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{s-rsa}}(\lambda) := \Pr \left[ \begin{array}{l} (N, P, Q) \leftarrow \mathrm{GenRSA}(1^{\lambda}); y \leftarrow \mathbb{Z}_N^* \\ (e, z) \leftarrow \mathcal{A}(N, y) : z^e \equiv y \quad \mathrm{mod} \quad N \end{array} \right] $$

is negligible in $\lambda$.

### A.4 Explaining Random Group Elements as Random Strings

For our framework, we require commitments with uniform public parameters $pp$. For readability, we allow $pp$ (and also uniform random strings $urs$ of NIZKs) to contain (uniform) group elements $g$ of prime-order groups $\mathbb{G}$ with known order $p$. This is without loss of generality because with explainable sampling, we can explain $g \leftarrow \mathbb{G}$ as a random bitstring.

### A.5 Commitment Scheme

**Definition 10 (Commitment Scheme).** A commitment scheme is a tuple of algorithms $C = (C.\mathrm{Commit}, C.\mathrm{Verify})$ such that

- $C.\mathrm{Setup}(1^{\lambda})$: generates the public parameters $pp$,

- $C.\mathrm{Commit}(pp, m)$: given the public parameters $pp$, message $m \in C_{\mathrm{msg}}$, computes a commitment $c \in C_{\mathrm{com}}$ with opening randomness $d$, and outputs the pair $(c, d)$,

- $\mathrm{Verify}(pp, c, m, d)$: given the public parameters $pp$, message $m \in C_{\mathrm{msg}}$, and opening randomness $d$, outputs a bit $b \in \{0, 1\}$ which depends on the validity of the opening $(m, d)$ with respect to the commitment $c$.

Here, $C_{\mathrm{msg}}$, $C_{\mathrm{rnd}}$, $C_{\mathrm{com}}$, are message, randomness, and commitment spaces, respectively. If the public parameters are uniform or explainable as per Appendix A.4 (i.e., $\mathrm{Setup}$ outputs some $pp \leftarrow \{0, 1\}^{\ell}$ for $\ell \in \mathbb{N}$) we omit $\mathrm{Setup}$ without loss of generality.

Below, we define the correctness, hiding and binding properties of a commitment scheme.

**Definition 11 (Correctness).** A commitment scheme is correct, if for all $pp \leftarrow \mathrm{Setup}(1^{\lambda})$, $m \in C_{\mathrm{msg}}$, $r \in C_{\mathrm{rnd}}$, $(c, d) \leftarrow \mathrm{Commit}(pp, m; r)$, it holds that $\mathrm{Verify}(pp, c, m, d) = 1$.

**Definition 12 (Hiding).** A commitment scheme is hiding if for any PPT adversary $\mathcal{A}$, we have

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{hide}}(\lambda) = \left| \Pr \left[ \begin{array}{l} \mathrm{pp} \leftarrow \mathrm{Setup}(1^{\lambda}), (m_0, m_1) \leftarrow \mathcal{A}(\mathrm{pp}), \\ m_0, m_1 \in C_{\mathrm{msg}}, \mathrm{coin} \leftarrow \{0, 1\} \\ (c, d) \leftarrow \mathrm{Commit}(\mathrm{pp}, m_{\mathrm{coin}}), \end{array} \quad : \mathrm{coin} = \mathcal{A}(c) \right] - \frac{1}{2} \right| = \mathrm{negl}(\lambda). $$

**Definition 13 (Binding).** A commitment scheme is binding if for any PPT adversary $\mathcal{A}$, we have

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{bind}}(\lambda) = \Pr \left[ \begin{array}{l} \mathrm{pp} \leftarrow \{0, 1\}^{\ell c}, \\ (c, m_0, m_1, d_0, d_1) \leftarrow \mathcal{A}(\mathrm{pp}) \quad : \quad \begin{array}{l} m_0 \neq m_1 \in C_{\mathrm{msg}} \\ \mathrm{Verify}(\mathrm{pp}, c, m_b, d_b) = 1, b \in \{0, 1\} \end{array} \end{array} \right] = \mathrm{negl}(\lambda). $$

*Remark 4.* A commitment scheme is said to be perfectly binding if for any (possibly unbounded) $\mathcal{A}$, it holds that $\mathrm{Adv}_{\mathcal{A}}^{\mathrm{bind}}(\lambda) = 0$.

**(Bounded) Integer Commitments.** We refer to a commitment scheme with message space $[A, B] \subseteq \mathbb{N}$ as a (bounded) integer commitment scheme. We often omit the term bounded if the message space is clear by context.
**ElGamal commitments.** We recall ElGamal (EG) over a group $\mathbb{G}$ of prime order $p$ with message space $\mathbb{Z}_p$ [39]. We use additive notation for prime order groups.

- EG.GenPP(1$^{\lambda}$): set $(G, H) \leftarrow \mathbb{G} \setminus \{0\}$ and output $pp = (G, H)$.

- EG Comitt(pp, m): sample $r \leftarrow \mathbb{Z}_p$ and set $c = (mG + rH, rG)$, and output $(c, r)$.

- EG.Verify(pp, c, m, r): check if $c = (mG + rH, rG)$.

Note that the public parameters are uniform and we can sample them via a random oracle to avoid trusted setup. EG commitments are correct, hiding under DDH and perfectly binding.

*Remark 5.* If in verification of EG, we check that $m \in [0, M]$ for $M < p$, then $m$ is fixed over the integers and we can interpret the commitment as an integer commitment with message space $[0, M] \subseteq \mathbb{N}$.

**Pedersen Commitments in QRN** We recall Pedersen multi-commitments (MPed) over QRN with message space $\mathbb{Z}^\ell$ for some $\ell \in \mathbb{N}$ [34].

- MPed.GenPP(1$^{\lambda}$): set $(N, P, Q) \leftarrow \text{Gen}(1^{\lambda})$ and sample $\ell$ random generators $g_i$ of QRN, and output $pp = (N, h, g_1, \cdots, g_\ell)$. Note that with $(P, Q)$, we can check whether $g_i$ generates QRN.

- MPed.Commit(pp, $\vec{m}$): sample $r \leftarrow [0, N \cdot 2^\lambda]$, set $c \leftarrow h^r \cdot \prod_{i=1}^\ell g_i^{m_i} \bmod N$, and output $(c, r)$.

- MPed.Verify(pp, c, $\vec{m}$, r): check if $c = \pm h^r \cdot \prod_{i=1}^\ell g_i^{m_i} \bmod N$.

MPed commitments are correct, statistically hiding and binding under the factoring assumption (which is implied by sRSA). Throughout this work, we use MPed commitments in QRN to enforce in security proofs that values extracted from NIZKs are integers via lemma 6.

## A.6 Signature Scheme

**Definition 14 (Signature Scheme).** A signature scheme is a tuple of PPT algorithms $S = (\text{KeyGen}, \text{Sign}, \text{Verify})$ such that

- $\text{KeyGen}(1^{\lambda})$: generates a verification key vk and a signing key sk,

- $\text{Sign}(sk, m)$: given a signing key sk and a message $m \in S_{\text{msg}}$, outputs a signature $\sigma$,

- $\text{Verify}(vk, m, \sigma)$: given a verification key pk and a signature $\sigma$ on message m, deterministically outputs a bit $b \in \{0, 1\}$.

Here, $S_{\text{msg}}$ is the message space.

We define the standard notion of correctness and euf-cma security

**Definition 15 (Correctness).** A signature scheme is correct, if for all $(vk, sk) \leftarrow \text{KeyGen}(1^{\lambda})$, $m \in S_{\text{msg}}$, and $\sigma \leftarrow \text{Sign}(sk, m)$, it holds that $\text{Verify}(vk, m, \sigma) = 1$.

**Definition 16 (EUF-CMA).** A signature scheme is euf-cma if for any PPT adversary $\mathcal{A}$, we have

$$ \text{Adv}_{\mathcal{A}}^{\text{euf}}(\lambda) = \Pr \left[ \begin{array}{l} (vk, sk) \leftarrow \text{KeyGen}(1^{\lambda}) \\ (m, \sigma) \leftarrow \mathcal{A}^{\text{Sign}(sk, \cdot)}(vk) \end{array} : m \notin L \land \text{Verify}(vk, m, \sigma) = 1 \right] = \text{negl}(\lambda), $$

where L is the list of messages A queried to the Sign-oracle.

## A.7 $\Sigma$-Protocol

Let $\mathcal{R}$ be an NP relation with statements $x$ and witnesses $w$. We denote by $\mathcal{L}_{\mathcal{R}} = \{x \mid \exists w \text{ s.t. } (x, w) \in \mathcal{R}\}$ the language induced by $\mathcal{R}$. A $\Sigma$-protocol for an NP relation $\mathcal{R}$ for language $\mathcal{L}_{\mathcal{R}}$ is a tuple of PPT algorithms $\Sigma = (\text{Init}, \text{Chall}, \text{Resp}, \text{Verify})$ such that

- $\text{Init}(x, w)$: given a statement $x \in \mathcal{L}_{\mathcal{R}}$, and a witness $w$ such that $(x, w) \in \mathcal{R}$, outputs a first flow message (i.e., commitment) $\Omega$ and a state st, where we assume st includes $x, w$,
- Chall(): samples a challenge $\gamma \leftarrow CH$ (without taking any input),

- Resp(st, $\gamma$): given a state st and a challenge $\gamma \in CH$, outputs a third flow message (i.e., response) $\tau$,

- Verify($x, \Omega, \gamma, \tau$): given a statement $x \in \mathcal{L}_R$, a commitment $\Omega$, a challenge $\gamma \in CH$, and a response $\tau$, outputs a bit $b \in \{0, 1\}$.

**Definition 17 (Correctness).** A $\Sigma$-protocol is correct, if for all $(x, w) \in R$, $(\Omega, \text{st}) \leftarrow \text{Init}(x, w)$, $\gamma \in CH$, and $\tau \leftarrow \text{Resp}(\text{st}, \gamma)$, it holds that $\text{Verify}(x, \Omega, \gamma, \tau) = 1$.

**Definition 18 (High Min-Entropy).** A $\Sigma$-protocol has high min-entropy if for all $(x, w) \in R$ and (possibly unbounded) adversary $\mathcal{A}$, it holds that

$$ \Pr[(\Omega, \text{st}) \leftarrow \text{Init}(x, w), \Omega' \leftarrow \mathcal{A}(1^{\lambda}) : \Omega = \Omega'] = \text{negl}(\lambda). $$

**Definition 19 (Non-abort HVZK).** A $\Sigma$-protocol is non-abort honest-verifier zero-knowledge (HVZK), if there exists a PPT zero-knowledge simulator $\text{Sim}$ such that the distributions of $\text{Sim}(x, \gamma)$ and the honestly generated transcript with $\text{Init}$ initialized with $(x, w)$ are statistically indistinguishable for any $x \in \mathcal{L}_R$, and $\gamma \in CH$, where the honest execution is conditioned on $\gamma$ being used as the challenge and no abort occurring.

We write HVZK for short if the $\Sigma$-protocol never aborts.

**Definition 20 (k-Special Soundness).** A $\Sigma$-protocol is k-special sound, if there exists a deterministic PT extractor $\text{Ext}$ such that given k valid transcripts $\{(\Omega, \gamma_i, \tau_i)\}_{i \in [k]}$ for statement $x$ with pairwise distinct challenges $(\gamma_i)_{i}$, outputs a witness $w$ such that $(x, w) \in R$.

## A.8 Non-Interactive Zero Knowledge

Let $\mathcal{URS} = \{0, 1\}^\ell$ be a set of uniform random strings for some $\ell \in \mathbb{N}$ and $\mathcal{SRS}$ be some set of structured random strings with efficient membership test $^{27}$. An NIZK for a relation $R$ with common reference string space $\mathcal{CRS} = \mathcal{SRS} \times \mathcal{URS}$ is a tuple of PPT algorithms ($\text{GenSRS}$, $\text{Prove}^H$, $\text{Verify}^H$), where the latter two are oracle-calling, such that:

- $\text{GenSRS}(1^\lambda)$: outputs a structured reference string $\text{srs} \in \mathcal{SRS}$,

- $\text{Prove}^H(\text{crs}, x, w)$: receives a $\text{crs} = (\text{srs}, \text{urs}) \in \mathcal{CRS}$, a statement $x$ and a witness $w$, and outputs a proof $\pi$,

- $\text{Verify}^H(\text{crs}, x, \pi)$: receives a $\text{crs} = (\text{srs}, \text{urs}) \in \mathcal{CRS}$, a statement $x$ and a proof $\pi$, and outputs a bit $b \in \{0, 1\}$.

We recall that $\mathcal{L}_R = \{x \mid \exists w : (x, w) \in R\}$ denotes the language induced by $R$. If there is no $\text{crs}$ needed, i.e. $\mathcal{CRS} = \emptyset$, we then omit $\text{crs}$ as an input to Prove and Verify.

**Definition 21 (Correctness).** An NIZK is correct if for any $\text{crs} = (\text{srs}, \text{urs})$ with $\text{srs} \leftarrow \text{GenSRS}(1^\lambda)$ and $\text{urs} \leftarrow \mathcal{URS}$, $(x, w) \in R$, and $\pi \leftarrow \text{Prove}^H(\text{crs}, x, w)$, it holds that $\text{Verify}^H(\text{crs}, x, \pi) = 1$.

**Definition 22 (Zero-Knowledge).** An NIZK is zero-knowledge (ZK) if there exists a PPT simulator $\text{Sim} = (\text{Sim}_{\text{crs}}, \text{Sim}_H, \text{Sim}_\pi)$ such that for any PPT adversary $\mathcal{A}$, it holds that

$$ \text{Adv}_{\mathcal{A}}^{\text{zk}}(\lambda) = \left| \Pr \left[ \begin{array}{l} \text{srs} \leftarrow \text{GenSRS}(1^{\lambda}), \\ \text{crs} = (\text{srs}, \text{urs}), \\ \mathcal{A}^{\text{H,P}}(\text{crs}) = 1 \end{array} \right] - \Pr \left[ \begin{array}{l} \text{crs} \leftarrow \text{Sim}_{\text{crs}}(1^{\lambda}), \\ \text{crs} = (\text{srs}, \text{urs}), \\ \mathcal{A}^{\text{Sim}_H, \mathcal{S}}(\text{crs}) = 1 \end{array} \right] \right| = \text{negl}(\lambda), $$

where $\mathcal{P}$ and $\mathcal{S}$ are oracles that on input $(x, w)$ return $\perp$ if $(x, w) \notin R$, and else output $\text{Prove}^H(\text{crs}, x, w)$ or $\text{Sim}_\pi(\text{crs}, x)$ respectively. Note that the probability is taken over the randomness of $\text{Sim}$ and $\mathcal{A}$, and the random choices of $\text{H}$ and $\text{urs}$. Also, $\text{Sim}_{\text{crs}}$, $\text{Sim}_H$ and $\text{Sim}_\pi$ have a shared state.

<footnote>$^{27}$ This membership test is required for our definition of subversion zero-knowledge. Note that in general it is difficult to check that some $\text{srs}$ was generated via $\text{GenSRS}$. (We allow that $\mathcal{SRS}$ is not equal to the output space of $\text{GenSRS}$.)</footnote>
We also define a notion of subversion zero-knowledge, inspired by the notion introduced in [12]. Informally, it guarantees that zero-knowledge holds even for a malicious crs.

**Definition 23 (Subversion Zero-Knowledge).** An NIZK is subversion zero-knowledge (Sub-ZK) if there exists a PPT simulator $Sim = (Sim_H, Sim_π)$ such that for any PPT adversary $A$, it holds that

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{sub-zk}}(\lambda) = \left| \Pr \left[ \begin{array}{l} \text{urs} \leftarrow \mathcal{URS}, \\ (\mathrm{srs}, \mathrm{st}) \leftarrow \mathcal{A}^{\mathrm{H}}(\text{urs}), \\ \mathrm{crs} = (\mathrm{srs}, \text{urs}), \\ \mathcal{A}^{\mathrm{H}, \mathcal{P}}(\mathrm{st}) = 1 \wedge \text{srs} \in \mathrm{SRS} \end{array} \right] - \Pr \left[ \begin{array}{l} \text{urs} \leftarrow \mathcal{URS}, \\ (\mathrm{srs}, \mathrm{st}) \leftarrow \mathcal{A}^{\mathrm{Sim}_H}(\text{urs}), \\ \mathrm{crs} = (\mathrm{srs}, \text{urs}), \\ \mathcal{A}^{\mathrm{Sim}_H, \mathcal{S}}(\mathrm{st}) = 1 \wedge \text{srs} \in \mathrm{SRS} \end{array} \right] \right| = \mathrm{negl}(\lambda), $$

where $\mathcal{P}$ and $\mathcal{S}$ are oracles that on input $(x, w)$ return $\perp$ if $(x, w) \notin \mathbb{R}$, and else output $\mathrm{Prove}^{\mathrm{H}}(\mathrm{crs}, x, w)$ or $Sim_π(\mathrm{crs}, x)$, respectively. Note that the probability is taken over the randomness of $Sim$ and $A$, and the random choices of $H$ and $urs$. Also, both $Sim_H$ and $Sim_π$ have a shared state.

We define different notions of soundness. We remark that the soundness relation $\tilde{\mathbb{R}}$ can be different from the (correctness) relation $\mathbb{R}$. If $\tilde{\mathbb{R}}$ is not explicitly defined, we implicitly set $\tilde{\mathbb{R}} = \mathbb{R}$.

**Definition 24 (Adaptive Knowledge Soundness).** An NIZK is adaptively knowledge sound for relation $\tilde{\mathbb{R}}$ if there exists PPT simulator $SimCRS$ and extractor $Ext$ such that

**CRS Indistinguishability.** For any PPT adversary $A$, we have

$$ \mathrm{Adv}_{\mathcal{A}}^{\mathrm{crs}}(\lambda) = \left| \Pr \left[ \begin{array}{l} \text{srs} \leftarrow \mathrm{GenSRS}(1^{\lambda}), \text{urs} \leftarrow \mathcal{URS}, \\ \text{crs} = (\text{srs}, \text{urs}) : \mathcal{A}^{\mathrm{H}}(\text{crs}) = 1 \end{array} \right] - \Pr \left[ \begin{array}{l} (\overline{\mathrm{crs}}, \mathrm{td}) \leftarrow \mathrm{SimCRS}(1^{\lambda}) : \\ \mathcal{A}^{\mathrm{H}}(\overline{\mathrm{crs}}) = 1 \end{array} \right] \right| = \mathrm{negl}(\lambda), $$

**Knowledge Soundness.** There exists positive polynomials $p_T, p_P$ and a constant $c$ such that given oracle access to any PPT adversary $A$ (with explicit random tape $\rho$) that makes $Q_H = \mathrm{poly}(\lambda)$ random oracle queries with

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

we have

$$ \mathrm{Pr} \left[ \begin{array}{l} (\overline{\mathrm{crs}}, \mathrm{td}) \leftarrow \mathrm{SimCRS}(1^{\lambda}), \\ (x, \pi) \leftarrow \mathcal{A}^{\mathrm{H}}(\overline{\mathrm{crs}}; \rho), \\ w \leftarrow \mathrm{Ext}(\overline{\mathrm{crs}}, \mathrm{td}, x, \pi, \rho, \vec{h}) \end{array} : (x, w) \in \tilde{\mathbb{R}} \right] \geq \frac{\mu(\lambda)^c - \mathrm{negl}(\lambda)}{p_P(\lambda, Q_H)}, $$

where $\vec{h}$ are the outputs of $H$, and the probability is over the random tape $\rho$ of $A$, the random tape of $SimCRS$, and the random choices of $H$. Also, we require that the runtime of $Ext$ is bounded by $p_T(\lambda, Q_H) \cdot \mathrm{Time}(A)$.

We also adapt the standard notion of online-extractability in two ways. Instead of embedding the online-extraction trapdoor $\mathrm{td}$ into $\mathrm{crs}$, we allow that the extractor embeds it into specific parts of statement. Also, we relax the requirements in the sense that only a partial witness $w_1$ is extracted. For extraction, we require that there exists a witness $w_0$ such that $(x, (w_0, w_1)) \in \tilde{\mathbb{R}}$.

**Definition 25 (Partial Online Extractability).** An NIZK is partially online-extractable for relation $\tilde{\mathbb{R}}$ with statements $x = (x_0, x_1)$ and witnesses $w = (w_0, w_1)$, where $w_0 \in W_0$ and $x_0 \in X_0$ for some sets $W_0, X_0$, if for all PPT adversaries $A$, there exists a stateful PPT extractor $Ext = (\mathrm{Ext}_1, \mathrm{Ext}_2)$, such that

1. $x_0$ is distributed uniform over $X_0$ for $(x_0, \mathrm{td}) \leftarrow \mathrm{Ext}_1(1^{\lambda})$ and

2. there exists positive polynomials $p_T, p_P$ such that for any $Q_H = \mathrm{poly}(\lambda)$ and PPT adversary $A$ that makes at most $Q_H$ random oracle queries with

$$ \mathrm{Pr} \left[ \begin{array}{l} (x_0, \mathrm{td}) \leftarrow \mathrm{Ext}_1(1^{\lambda}), \mathrm{crs} \leftarrow \mathrm{GenSRS}(1^{\lambda}), \\ \{ (x_{1,i}, \pi_i) \}_{i \in [Q_S]} \leftarrow \mathcal{A}^{\mathrm{H}}(\mathrm{crs}, x_0), x_i \leftarrow (x_0, x_{1,i}) : \\ \forall i \in [Q_S] : \mathrm{Verify}^{\mathrm{H}}(\mathrm{crs}, x_i, \pi_i) = 1 \end{array} \right] \geq \mu(\lambda), $$
Corresponding to these alternate key generation algorithms, we describe how to use the internal state for generating signatures on hashes of messages $\overline{m}$ where $k$ is a counter for the number of signing queries.

S$_{fis}$.Sign$_{0,0}$(β, v, w, e$_{1}$, ..., e$_{Q_S}$, j, k, $\overline{m}$) If $k \neq j$, sample $a_k \leftarrow S_a$. Compute

$$ 
\begin{aligned}
y_k &:= w^2 \prod_{i \neq k} e_i \cdot \left( z^{\sum_{\substack{i \neq j \\ i \neq k}} e_i} \right)^{a_k - \beta} \left( v^2 \prod_{i \neq k} e_i \right)^{a_k + \overline{m}} \\
&= \left( h \cdot h_1^{a_k} \cdot h_2^{a_k + \overline{m}} \right)^{\frac{1}{e_k}}
\end{aligned}
$$

For $k = j$, it sets $a_k = \beta$ and computes

$$ 
\begin{aligned}
y_k &:= w^2 \prod_{i \neq k} e_i \cdot \left( v^2 \prod_{i \neq k} e_i \right)^{a_k + \overline{m}} \\
&= \left( h \cdot h_1^{a_k} \cdot h_2^{a_k + \overline{m}} \right)^{\frac{1}{e_k}}
\end{aligned}
$$

Output $\sigma_k = (e_k, a_k, y_k)$.

S$_{fis}$.Sign$_{0,1}$(β, v, w, e$_{1}$, ..., e$_{Q_S}$, j, k, $\overline{m}$) For any $k \neq j$, sample $a_k \leftarrow S_a$ and compute

$$ 
\begin{aligned}
y_k &:= w^2 \prod_{i \neq k} e_i \cdot \left( z^{\sum_{\substack{i \neq j \\ i \neq k}} e_i} \right)^{a_k + \overline{m} - \beta} \left( v^2 \prod_{i \neq k} e_i \right)^{a_k} \\
&= \left( h \cdot h_1^{a_k} \cdot h_2^{a_k + \overline{m}} \right)^{\frac{1}{e_k}}
\end{aligned}
$$

For $k = j$, it sets $a_k = \beta - \overline{m}$ and computes

$$ 
\begin{aligned}
y_k &:= w^2 \prod_{i \neq k} e_i \cdot \left( v^2 \prod_{i \neq k} e_i \right)^{a_k + \overline{m}} \\
&= \left( h \cdot h_1^{a_k} \cdot h_2^{a_k + \overline{m}} \right)^{\frac{1}{e_k}}
\end{aligned}
$$

S$_{fis}$.Sign$_1(a, a', e_1, ..., e_{Q_S}, k, \overline{m})$ Sample $a_k \leftarrow S_a$ and compute

$$ 
\begin{aligned}
y_k &:= z^{2 \cdot (a + a_k \cdot a' + (a_k + \overline{m}))} \prod_{i \neq k} e_i \\
&= \left( h \cdot h_1^{a_k} \cdot h_2^{a_k + \overline{m}} \right)^{\frac{1}{e_k}}
\end{aligned}
$$

## B.2 Proof of security

**Theorem 6.** If the sRSA assumption holds and the hash function $H$ is a random oracle mapping from $\{0, 1\}^*$ to $\{0, 1\}^{2\lambda}$ then the scheme described above is EUF-CMA secure.

*Proof.* Let $\mathcal{A}$ be an adversary against the EUF-CMA security of the scheme that runs in time $t'$ and has advantage $\epsilon'$ and makes $Q_S$ queries to the signing oracle.

We denote by $m_i$ the $i$th message queried to the signing oracle by $\mathcal{A}$, by $\sigma_i = (e_i, a_i, y_i)$ the $i$th signature output by the signing oracle to $\mathcal{A}$, and by $m^*, \sigma^* = (e^*, a^*, y^*)$ we denote $\mathcal{A}$'s forgery. We show security through a series of games.

*Game 1:* Game 1 is the original EUF-CMA game.

*Game 2:* In Game 2 the game aborts if for any $i, j, m_i \neq m_j$ it holds that $H(m_i) = H(m_j)$ or if $H(m_i) = H(m^*)$. We can bound the abort probability by bounding the number of collisions in $H$, namely,

$$ |\Pr[\text{Game 2} = 1] - \Pr[\text{Game 1} = 1]| \leq \frac{Q_H^2}{2 \cdot 2^{2\lambda}} $$
**Game 3:** In Game 3, we introduce an abort condition in which our reduction will not be able to simulate. At the end of the game, the game samples a bit $b$ and aborts if $b = 0$ and $e^* \notin \{e_1, \dots, e_{Q_S}\}$ or if $b = 1$ and $e^* \in \{e_1, \dots, e_{Q_S}\}$. It is easy to see that

$$ \Pr[\text{Game 3} = 1] \geq \frac{1}{2} \Pr[\text{Game 2} = 1]. $$

**Game 4:** In Game 4, if $b = 0$, the Game samples an index $j \in \{1, \dots, Q_S\}$. It aborts if $e^* \neq e_j$. It holds that

$$ \Pr[\text{Game 4} = 1] \geq \frac{1}{Q_S} \Pr[\text{Game 3} = 1] $$

**Game 5:** In Game 5, if $b = 0$, the Game samples a bit $b'$. If $b' = 0$ and $a_j = a^*$ (where $j$ is as defined in Game 4), the game aborts. If $b' = 1$ and $a_j + H(m_j) = a^* + H(m^*)$, the game aborts. We argue why the abort probability is $\frac{1}{2}$. As the adversary is not allowed to re-sign a previously signed message, it holds that $m_j \neq m^*$. This, along with the abort condition induced in Game 2, implies that $H(m^*) \neq H(m_j)$. Thus, if the adversary chooses $a^* = a_j$, it must be the case that $a_j + H(m_j) \neq a^* + H(m^*)$. Otherwise it holds that $a^* \neq a_j$. The bit $b$ is chosen independently of this choice of the adversary regarding his forgery and therefore,

$$ \Pr[\text{Game 5} = 1] \geq \frac{1}{2} \Pr[\text{Game 4} = 1]. $$

**Game 6:** In Game 6, we sample $b, b', j$ at the beginning of the game. This is a purely conceptual change, thus

$$ \Pr[\text{Game 6} = 1] = \Pr[\text{Game 5} = 1] $$

**Game 7:** In Game 7 we change how the values $a_j$ are sampled during signature generation. If $b = 0$, $b' = 0$, instead of sampling $a_j \leftarrow S_a$, it first samples $\beta \leftarrow S_a$ and then sets $a_j = \beta$. If $b = 1$ and $b' = 1$, it samples $\beta \leftarrow S_a$ and sets $a_j = \beta - H(m_j)$. A simple argument shows that the distribution of $a_j$ in Game 7 has statistical distance at most $1/2^\lambda$ from the distribution of $a$ in Game 6.

Thus, we get that $|\Pr[\text{Game 7} = 1] - \Pr[\text{Game 6} = 1]| \leq \frac{1}{2^\lambda}$.

**The Reduction:** We now provide a reduction that simulates Game 7 and breaks the strong RSA assumption.

On input $(N, z \in \mathbb{Z}_N^*)$, the reduction behaves as follows:

First, it samples a bit $b, b'$ and an index $j$. If $b = 0$ (recall that in this case Game 7 aborts if $e^* \notin \{e_1, \dots, e_{Q_S}\}$), the reduction works as follows:

**Setup.** Runs $\text{S}_{\text{fis.}}$.$\text{KeyGen}_{0,b'}(1^\lambda, N, z)$ to obtain $vk, \text{sk}_{0,b'}$ It passes the public key $(N, h, h_1, h_2)$ to the adversary.

**Signing Queries.** For the $k$th signing query it runs $\text{S}_{\text{fis.}}$.$\text{Sign}_{0,b'}(\text{sk}_{0,b'}, k, H(m))$ to obtain $\sigma_k = (e_k, a_k, y_k)$ and outputs $\sigma_k$.

**Output Determination.** When the adversary outputs a forgery $m^*, \sigma^* = (e^*, a^*, y^*)$, the reduction can compute an $e_j$th root of $z$. As Game 7 aborts unless $e^* = e_j$, the reduction obtains

$$ h_1^{-a_j} h_2^{-(a_j+H(m_j))} \cdot y_j^{e_j} = h = h_1^{-a^*} h_2^{-(a^*+H(m^*))} y^{e_j} $$

If $b' = 0$, solving for $z$ using the preselected values from the public key yields:

$$ z^2 \prod_{i \neq j} e_i \cdot (a^* - a_j) = \left( v^2 \prod_{i \neq j} e_i \cdot (a_j + H(m_j) - a^* - H(m^*)) \right)^{e_j} (y^* y_j^{-1})^{e_j} $$

Which we can solve for a $e_j$th root of $z$ if $\gcd(e_j, 2 \prod_{i \neq j} e_i \cdot (a^* - a_j)) = 1$ using lemma 5. It holds that the gcd is 1 as $a_j < e$ and $a^* < e$ by virtue of the range checks, and thus also their
difference is smaller than $e_j$. As $e_j$ is prime this immediately implies coprimality. Furthermore, all the other $e_i$ are coprime to $e_j$, and $e_j$ is odd, so it is also coprime with 2. Analogously, if $b' = 1$, we swap the roles of $h_1$ and $h_2$ and get

$$z^2 \prod_{i \neq j} e_i \cdot (\bar{m}^* + a^* - (\bar{m}_j + a_j)) = (v^2 \prod_{i \neq j} e_i \cdot (a_j - a^*))^{e_j} (y^* y_j^{-1})^{e_j}.$$

Again, using the same reasoning as above, we can solve for an $e_j$th root of $z$ using lemma 5.

For the case that $b = 1$, the reduction simulates as follows:

**Setup.** Given $N$ and $z \in \mathbb{Z}_N$, the reduction runs $\text{S}_{\text{fis}}.\text{KeyGen}_1(1^{\lambda}, N, z)$ to obtain $\text{vk} = (N, h, h_1, h_2)$ and $\text{sk}_1$. It outputs the public key $\text{vk}$ to the adversary.

**Signaling Queries.** The reduction responds to the $k$th signing query by running $\text{S}_{\text{fis}}.\text{Sign}_1(\text{sk}_1, k, \mathbf{H}(m))$ to obtain $\sigma_k$. It outputs the signature $\sigma_k$.

**Output Determination.** When the adversary outputs its forgery $m^*, \sigma^* = e^*, a^*, y^*$), the reduction can learn the following

$$y^{*e^*} = h h_1^{a^*} h_2^{a^* + \mathbf{H}(m^*)} = z^{2 \cdot (a + a^* \cdot a' + (a^* + \mathbf{H}(m^*)) \prod_{i \neq k} e_i}$$

Computing a root of $z$ follows as in [41] where the probability of success is $(1 - 1/r)$ where $r$ is the smallest prime factor dividing $e^*$. As $e^*$ is odd, $r$ is at least 3. Putting this together yields

$$ \begin{align*} \text{Adv}_{\text{B}}^{\text{sRSA}} &\ge \frac{2}{3} \Pr[\text{Game } 7 = 1] \\ &\ge \frac{2}{3} \left( \Pr[\text{Game } 6 = 1] - \frac{1}{2^{\lambda}} \right) \\ &\ge \frac{2}{3} \left( \frac{1}{4Q_S} \Pr[\text{Game } 2 = 1] - \frac{1}{2^{\lambda}} \right) \\ &\ge \frac{2}{3} \left( \frac{1}{4Q_S} \left( \Pr[\text{Game } 1 = 1] - \frac{Q_H^2}{2 \cdot 2^{2\lambda}} \right) - \frac{1}{2^{\lambda}} \right) \\ &= \frac{1}{6Q_S} \text{Adv}_{\text{A}}^{\text{euf-cma}} - \frac{1}{6Q_S} \frac{Q_H^2}{2 \cdot 2^{2\lambda}} - \frac{1}{3 \cdot 2^{\lambda-1}} \end{align*} $$

# C Deferred Content from Section 5

## C.1 Efficient Opening in Zero-Knowledge

We construct efficient NIZKs $\Pi_{\text{int}}$ and $\Pi_{\text{grp}}$ to open $C_{\text{RInt}}$ and $C_{\text{Grp}}$, respectively, in zero-knowledge.

**Proof for Public Parameters.** Before we detail both NIZKs, we construct an additional NIZK $\Pi_{\text{gen}}$ to prove that MPed is statistically hiding under public parameters $pp = (N, h, \vec{g})$ for MPed and $\vec{g} = (g_1, \dots, g_\ell)$. This is the case if $\langle h \rangle = \langle g_i \rangle \subseteq \mathbb{Z}_N^*$ for all $i \in [\ell]$. More generally, we construct an NIZK $\Pi_{\text{gen}}$ with oracle $\mathbf{H}_{\text{gen}}$ for the relation

$$R_{\text{gen}} = \{ (x, w) \mid \forall i \in [\ell] : g_i^{\alpha_i} \equiv h \bmod N, h^{\beta_i} \equiv g_i \bmod N \},$$

where $x = (N, \ell, h, (g_i)_{i \in [\ell]})$ and $w = ((\alpha_i, \beta_i)_{i \in [\ell]})$ for some $\ell \in \mathbb{N}$. Note that we also use $\Pi_{\text{gen}}$ in Section 6. It is based on the $\Sigma$-protocol $\Sigma_{\text{gen}}$ given in Fig. 2 with challenge space $[0, C]$ for $C = 2^{\lambda} - 1$, compiled into a NIZK via Fiat-Shamir. The random oracle is denoted by $\mathbf{H}_{\text{gen}}$. Note that no crs is required (i.e., $\text{SRS} = \text{URS} = \{\perp\}$).

- $\Pi_{\text{gen}}.\text{GenSRS}(1^{\lambda})$: Outputs $\perp$.

- $\Pi_{\text{gen}}.\text{Prove}^{\mathbf{H}_{\text{gen}}}(\text{crs}, x, w)$: On input crs, statement $x$, and witness $w$, outputs the proof $\pi$ computed as follows

$$ \begin{align*} (\Omega_{\Sigma}, \text{st}) &\leftarrow \Sigma_{\text{gen}}.\text{Init}(x, w), \\ \gamma_{\Sigma} &\leftarrow \mathbf{H}_{\text{gen}}(x, \Omega_{\Sigma}), \\ \tau_{\Sigma} &\leftarrow \Sigma_{\text{gen}}.\text{Resp}(x, \text{st}, \gamma_{\Sigma}), \\ \pi &\leftarrow (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}). \end{align*} $$
— $\Pi_{\text{gen}}.\text{Verify}^{\text{H}_{\text{gen}}}(\text{crs}, x, \pi)$: On input crs, statement $x$, and proof $\pi$, checks

$$ \begin{aligned} \text{H}_{\text{gen}}(x, \Omega_{\Sigma}) &= \gamma_{\Sigma}, \\ \Sigma_{\text{ped}}.\text{Verify}(x, \Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}) &= 1, \end{aligned} $$

where $\pi = (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma})$, and outputs 1 iff all checks succeed.

<figure><img src="image_2.png" /><figcaption>Fig. 2: Description of $\Sigma_{\text{gen}}$ for $x = (N, \ell, h, \vec{g})$ and $w = (\alpha_i, \beta_i)_{i \in [\ell]}$ with $\vec{g} = (g_1, \dots, g_\ell)$. We denote the Hadamard product by $\circ$.</figcaption></figure>

We first show that the $\Sigma$-protocol $\Sigma_{\text{gen}}$ given in Fig. 2 satisfies desired properties for the Fiat-Shamir transform.

**Theorem 7.** *The $\Sigma$-protocol $\Sigma_{\text{gen}}$ given in Fig. 2 satisfies correctness, 2-special soundness, honest-verifier zero-knowledge, and has high min-entropy.*

*Proof.* For the commitment vectors $\vec{\Omega}_g, \vec{\Omega}_h$ and the response vectors $\vec{\tau}_\alpha, \vec{\tau}_\beta$, their $i$-th element is denoted by $\vec{\Omega}_{g,i}, \vec{\Omega}_{h,i}, \vec{\tau}_{\alpha,i}, \vec{\tau}_{\beta,i}$. First of all, we recall that $\Sigma$-protocol $\Sigma_{\text{gen}}$ is used for $N$ comes from the $pp = (N, h, \vec{g})$ for the Pedersen commitment MPed in $QR_N$. (Since membership in $QR_N$ cannot be efficiently tested without factorization of $N$, the MPed commitment is formally defined over $\mathbb{Z}_N^*$.) Later, $N$ and $pp$ are given in the crs, and $pp$ are generators of $QR_N$ else we find witness of some relaxed DLOG relation as per Definition 7.) Thus as long as $h, g_i \neq 1$ for $i \in [\ell]$, the groups $\langle h \rangle, \langle g_i \rangle$ are of exponentially large orders in $\lambda$. Therefore, using the fact that the space $([0, N \cdot 2^{2\lambda}]^\ell)^\lambda$ is exponentially large in $\lambda$, $\Sigma_{\text{gen}}$ has high min-entropy. Next, correctness is straightforward, noting that by construction, for $x = (N, \ell, h, \vec{g})$ and $w = (\alpha_i, \beta_i)_{i \in [\ell]}$, for all $i \in [\ell]$

$$ \vec{\Omega}_{g,i} \circ h^{\vec{\gamma}} = g_i^{\vec{\mu}_{\alpha,i}} \circ g_i^{\alpha_i \cdot \vec{\gamma}} = g_i^{\vec{\tau}_{\alpha,i}}; \quad \vec{\Omega}_{h,i} \circ g_i^{\vec{\gamma}} = h^{\vec{\mu}_{\beta,i}} \circ h^{\beta_i \vec{\gamma}} = h_i^{\vec{\tau}_{\beta,i}}. $$

For 2-special soundness, given two valid transcripts $(\vec{\Omega}_g, \vec{\Omega}_h), \vec{\gamma}^b, \vec{\tau}_\alpha^b, \vec{\tau}_\beta^b$ where $b \in \{0, 1\}$ and $\vec{\gamma}^0 \neq \vec{\gamma}^1$, a deterministic polynomial-time extractor Ext can executes as follows: First, identify an index $j$ s.t. $\gamma_j^0 \neq \gamma_j^1$

1. For each $i \in [\ell]$, Ext sets $\alpha_i := \frac{\vec{\tau}_{\alpha,i}^0 - \vec{\tau}_{\alpha,i}^1}{\gamma_j^0 - \gamma_j^1}$.

2. For each $i \in [\ell]$, Ext sets $\beta_i := \frac{\vec{\tau}_{\beta,i}^0 - \vec{\tau}_{\beta,i}^1}{\gamma_j^0 - \gamma_j^1}$.

3. Outputs $w := (\alpha_i, \beta_i)_{i \in [\ell]}$ as a witness for $x = (N, \ell, h, \vec{g})$.
The output $w$ by $\mathrm{Ext}$ is well defined and indeed a witness of $x$ because $\gamma^0 \neq \gamma^1$, $\gamma_j^0 - \gamma_j^1 \in \{-1, 1\}$ (and thus has an efficiently computable multiplicative inverse) and

$$ \left\{ \begin{array}{l} \vec{\Omega}_{g,i} \cdot h^{\gamma_j^0} = g_i^{\vec{\tau}_{\alpha,i}^0} \\ \vec{\Omega}_{g,i} \cdot h^{\gamma_j^1} = g_i^{\vec{\tau}_{\alpha,i}^1} \end{array} \right. ; \quad \left\{ \begin{array}{l} \vec{\Omega}_{h,i} \cdot g_i^{\gamma_j^0} = h^{\vec{\tau}_{\beta,i}^0} \\ \vec{\Omega}_{h,i} \cdot g_i^{\gamma_j^1} = h^{\vec{\tau}_{\beta,i}^1} \end{array} \right. \quad \Rightarrow \quad \left\{ \begin{array}{l} h^{\gamma_j^0 - \gamma_j^1} = g_i^{\vec{\tau}_{\alpha,i}^0 - \vec{\tau}_{\alpha,i}^1} \\ g_i^{\gamma_j^0 - \gamma_j^1} = h^{\vec{\tau}_{\beta,i}^0 - \vec{\tau}_{\beta,i}^1} \end{array} \right. . $$

A PPT simulator $\mathrm{Sim}$ for honest-verifier zero-knowledge works as follows:

1. For each $i \in [\ell]$

- $\mathrm{Sim}$ samples the challenge $\vec{\gamma} \leftarrow \{0, 1\}^{\lambda}$ as well as the $i$-th responses $\vec{\tau}_{\alpha,i}, \vec{\tau}_{\beta,i} \leftarrow ([0, N \cdot 2^{2\lambda}])^{\lambda}$.

- $\mathrm{Sim}$ computes $\vec{\Omega}_{g,i} := g_i^{\vec{\tau}_{\alpha,i}}(h^{\vec{\gamma}})^{-1}$ and $\vec{\Omega}_{h,i} := h^{\vec{\tau}_{\beta,i}} \circ (g_i^{\vec{\gamma}})^{-1}$. The commitments are defined $\vec{\Omega}_g := (\vec{\Omega}_{g,i})_{i \in [\ell]}, \vec{\Omega}_h := (\vec{\Omega}_{h,i})_{i \in [\ell]}$.

- Output $(\vec{\Omega}_g, \vec{\Omega}_h, \gamma, \vec{\tau}_\alpha, \vec{\tau}_\beta)$.

For any $x \in \mathcal{L}_R$, i.e. $\langle h \rangle = \langle g_i \rangle \subseteq \mathbb{Z}_N^*$ for all $i \in [\ell]$, the simulator $\mathrm{Sim}(x, C)$ outputs a valid transcript that follows a distribution statistically close to that of the honestly generated transcript with $\mathrm{Init}$ initialized with $(x, w)$. First we argue the distribution of the commitments $\vec{\Omega}_g, \vec{\Omega}_h$. We use the fact that because $\langle h \rangle = \langle g_i \rangle$, it holds that $\vec{\Omega}_{g,i} := \frac{g_i^{\vec{\tau}_{\alpha,i}}}{h^{\vec{\gamma}}} \in \langle g_i \rangle$ and $\vec{\Omega}_{h,i} := \frac{h^{\vec{\tau}_{\beta,i}}}{g_i^{\vec{\gamma}}} \in \langle h \rangle$ having the statistically close distributions thanks to Noise Flooding recalled in Appendix A.2. Indeed, $\vec{\tau}_\alpha, \vec{\tau}_\beta \leftarrow ([0, N \cdot 2^{2\lambda}]^\lambda)$, where each $i$-th responses $\vec{\tau}_{\alpha,i}, \vec{\tau}_{\beta,i} \leftarrow ([0, N \cdot 2^{2\lambda}])^\lambda$, act as masks for the given values $\vec{\gamma} \circ \vec{\alpha}, \vec{\gamma} \circ \vec{\beta} \in ([0, N]^\lambda)$. By noise flooding the induced $\vec{\mu}_\alpha \leftarrow -\vec{\gamma} \circ \vec{\alpha} + \vec{\tau}_\alpha$, $\vec{\mu}_\beta \leftarrow -\vec{\gamma} \circ \vec{\beta} + \vec{\tau}_\beta$ are distributed close to uniform within distance $1/2^{2\lambda}$. Next we argue that the distribution of the real responses $\vec{\tau}_\alpha, \vec{\tau}_\beta$ in the real protocol are statistically close to uniform over $([0, N \cdot 2^{2\lambda}]^\lambda)$.

$$ \vec{\tau}_{\alpha} \leftarrow \vec{\gamma} \circ \vec{\alpha} + \vec{\mu}_{\alpha}, \vec{\tau}_{\beta} \leftarrow \vec{\gamma} \circ \vec{\beta} + \vec{\mu}_{\beta} $$

where $\vec{\mu}_\alpha, \vec{\mu}_\beta \leftarrow ([0, N \cdot 2^{2\lambda}]^\lambda)$ act as masks for $\vec{\gamma} \circ \vec{\alpha}, \vec{\gamma} \circ \vec{\beta} \in ([0, N]^\lambda)$. Then similarly noise flooding concludes that the induced $\vec{\tau}_\alpha, \vec{\tau}_\beta$ are distributed close to uniform within distance $1/2^{2\lambda}$. This means the way of simulating $\vec{\tau}_\alpha, \vec{\tau}_\beta \leftarrow ([0, N \cdot 2^{2\lambda}])^\lambda$ is statistically close to the real responses and the proof is completed. $\square$

We now show that the $\Pi_{\mathrm{gen}}$ satisfies statistical adaptive subversion soundness, zero-knowledge, and correctness.

**Theorem 8.** $\Pi_{\mathrm{gen}}$ satisfies statistical adaptive subversion soundness, zero-knowledge, and correctness.

*Proof.*

*Correctness.* Correctness directly follows from the correctness of the underlying $\Sigma$-protocol.

*Soundness.* As the CRS of this protocol is empty, it suffices to consider an adversary $\mathcal{A}$ that outputs a pair $(x, \pi)$ for $x \notin \mathcal{L}_R$. Consider an arbitrary $x \notin \mathcal{L}_R$, i.e. $\langle h \rangle \neq \langle g_i \rangle$ for some $i \in [\ell]$. W.l.o.g. we consider the case that $\langle h \rangle \not\subseteq \langle g_i \rangle$ (the argument for the other direction is symmetrical). This in particular means $h \notin \langle g_i \rangle$. Thus, for any value $\Omega_{g,i,j} \in \mathbb{Z}_N^*$ it cannot hold that both $\Omega_{g,i,j} \cdot h \in \langle g_i \rangle$ as well as $\Omega_{g,i,j} \in \langle g_i \rangle$. We consider a hash query made by the statistical soundness adversary. The adversary submits vectors $\vec{\Omega}_g, \vec{\Omega}_h$ to the random oracle. By what we saw above, for each entry $\vec{\Omega}_{g,i,j}$, it holds that either $\Omega_{g,i,j} \cdot h \in \langle g_i \rangle$ or $\Omega_{g,i,j} \in \langle g_i \rangle$ (if neither is the case the adversary cannot output a proof using this hash query). As the hash oracle is a random oracle, with probability $\leq \frac{1}{2}$, the $j$-th entry of the hash response is $b_j$ such that $\Omega_{g,i,j} \cdot h^b \in \langle g_i \rangle$. As the $b_j$ are sampled uniformly at random by the random oracle, it follows that the probability that for all $j \in [\lambda]$, $\Omega_{g,i,j} \cdot h^b \in \langle g_i \rangle$ is $\leq \frac{1}{2^\lambda}$. Union bounding over all $\mathcal{Q}_{\mathrm{H}_{\mathrm{gen}}}$ hash queries made by the adversary yields that $\mathrm{Adv}_{\mathcal{A}}^{\mathrm{snd}}(\lambda) \leq \frac{\mathcal{Q}_{\mathrm{H}_{\mathrm{gen}}}}{2^\lambda}$.

*Zero-knowledge.* The Zero-Knowledge property directly follows from the honest verifier zero-knowledge property of the $\Sigma$-protocol and the Fiat-Shamir transform.
**Efficient Proof of Opening for $C_{RInt}$.** We construct a NIZK $\Pi_{int}$ that allows to open $C_{RInt}^{\vec{B},T}$ in zero-knowledge for arbitrary $B \in \mathbb{N}$ and slack $T = 2^{\lambda+1}L$, where $L \in \mathbb{N}$ is the masking overhead for rejection sampling. Note that the size of $T$ and $\vec{B}$ impact the size of the underlying group $\mathbb{G}$.

To construct $\Pi_{int}$, we compile a Schnorr-style $\Sigma$-protocol with challenge space $[0, C]$ for $C := 2^{\lambda}-1$ using Fiat-Shamir with abort. To ensure (relaxed) range membership we use techniques from [33, 32]. Roughly, we add an MPed commitment $\bar{c}$ to $\vec{m}$ that in conjunction with a size check ensures that the extracted integers are in the relaxed range $[-\vec{B}T, \vec{B}T]$. The public parameters $pp_{MPed} = (N, h, g_1, \dots, g_\ell)$ for MPed constitute the srs. To obtain subversion zero-knowledge, we add a proof $\pi_{gen}$ generated via $\Pi_{gen}$ that $\langle h \rangle = \langle g_i \rangle$ for all $i \in [\ell]$ to ensure that MPed is hiding even for a malicious $pp_{MPed}$. We denote by $H_{gen}$ the hash function for $\Pi_{gen}$.

Formally, the zero-knowledge relation is

$$R = \{(x, w) | (c, d) = C_{RInt}.\text{Commit}(\vec{m}; r), \vec{m} \in [0, \vec{B}]\}$$

for $x = (pp, c)$ with $c = (\vec{C}, F)$ and $w = (\vec{m}, r)$, where $d = r \in \mathbb{Z}_p$. The soundness relation is

$$\tilde{R} = \{(x, w) | C_{RInt}.\text{Verify}(pp, c, \vec{m}, r)\}.$$

The underlying $\Sigma$-protocol $\Sigma_{int}$ is given in Fig. 3. Note that the crs is included in the statement of $\Sigma_{int}$ for technical reasons. The NIZK $\Pi_{int}$ with hash function $H_{int}: \{0, 1\}^* \to [0, C]$, urs length $\ell_{int} = 0$ and

$$\mathcal{SRS} = \{(pp_{MPed}, \pi_{gen}) | pp_{MPed} = (N, h, \vec{g}) \in \mathbb{N} \times (\mathbb{Z}_N^*)^{\ell+1}, \\ \qquad \Pi_{gen}.\text{Verify}^{H_{gen}}(x_{gen}, \pi_{gen}), x_{gen} = (N, \ell, h, \vec{g})\}$$

is defined as follows. Note that membership checks for $\mathcal{SRS}$ are efficient by design.

- $\Pi_{int}.\text{GenCRS}(1^{\lambda})$: On input $1^{\lambda}$, samples $pp_{MPed} = (N, h, \vec{g}) \leftarrow \text{MPed}\text{.Setup}(1^{\lambda})$. Then, sets $\pi_{gen} \leftarrow \Pi_{gen}.\text{Prove}^{H_{gen}}(w_{gen}, x_{gen})$ for $x_{gen} = (N, \ell, h, \vec{g})$ and appropriate $w_{gen}$ (which can be computed explicitly during MPed. Setup). Outputs the structured reference string srs = $(pp_{MPed}, \pi_{gen})$.

- $\Pi_{int}.\text{Prove}^{H_{int}}(crs, x, w)$: Complies a proof $\pi$ as follows for $x_{\sigma} = (x, crs)$.

$$\begin{align*}
(\Omega_{\Sigma}, \text{st}) &\leftarrow \Sigma_{\text{int}}.\text{Init}(x, w), \\
\gamma_{\Sigma} &\leftarrow H_{\text{int}}(x_{\Sigma}, \Omega_{\Sigma}), \\
\tau_{\Sigma} &\leftarrow \Sigma_{\text{int}}.\text{Resp}(x_{\Sigma}, \text{st}, \gamma_{\Sigma}), \\
\pi &\leftarrow (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}).
\end{align*}$$

Restarts if $\Sigma_{int}.\text{Resp}$ aborted, else outputs $\pi$.

- $\Pi_{int}.\text{Verify}^{H_{gen}}(crs, x, \pi)$: On input crs, statement $x$, and proof $\pi$, sets $x_{\Sigma} = (x, crs)$ and checks

$$\begin{align*}
H_{\text{int}}(x_{\Sigma}, \Omega_{\Sigma}) &= \gamma_{\Sigma}, \\
\Sigma_{\text{ped}}.\text{Verify}(x_{\Sigma}, \Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma}) &= 1,
\end{align*}$$

where $\pi = (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma})$, and outputs 1 iff all checks succeed.

We show that $\Pi_{int}$ is secure. We give a brief sketch. Correctness is clear (if the abort probability is sufficiently low). For soundness, we use the forking lemma to obtain 2 accepting transcripts. Then, we compute openings for $C_{RInt}$ as usual. Due to lemma 6 and the shortness checks, the opening is in the right interval. For subversion zero-knowledge, observe that for any srs $\in \mathcal{SRS}$, the commitment $\bar{c}$ is hiding (under soundness of $\Pi_{gen}$).

**Theorem 9.** The NIZK is correct if $(1 - \frac{1}{L})^{-\ell} = \text{poly}(\lambda)$, adaptively knowledge sound for $\tilde{R}$ and subversion zero-knowledge.

*Proof.* We give a proof sketch for correctness and subversion zero-knowledge (as the proofs are straightforward) and give a detailed proof for soundness.

*Correctness.* Note that a single run succeeds with probability $(1 - \frac{1}{L})^{\ell}$ because $1/L$ is the abort probability of the size check in line 10 per coordinate (cf. Appendix A.2). Thus, proof generation
<table><caption>Fig. 3: Description of $\Sigma_{\text{int}}$, an efficient $\Sigma$-protocol for opening $C_{\text{RInt}}$. Here, $x = (\text{pp}, \vec{C}, F, \text{crs})$ and $w = (\vec{m}, r)$. Also, $\text{crs} = (N, h, \vec{g}, \pi_{\text{gen}})$ for $\vec{g} = (g_1, \dots, g_\ell)$. If a check fails, the party aborts.</caption><thead><tr><th>Prover(x; w)</th><th>Verifier(x)</th></tr></thead><tbody><tr><td>1: $\bar{c} \leftarrow h^{\bar{r}} \cdot \prod_{i=1}^{\ell} g_i^{m_i} \bmod N$ for $\bar{r} \leftarrow [0, N \cdot 2^{\lambda}]$</td><td></td></tr><tr><td>2: $\mu_r \leftarrow \mathbb{Z}_p, \mu_{\bar{r}} \leftarrow [0, CN \cdot 2^{2\lambda}]$</td><td></td></tr><tr><td>3: $\bar{\mu}_m \leftarrow [0, (\bar{B}C + 1)L]$</td><td></td></tr><tr><td>4: $\Omega_F \leftarrow \mu_r H, \bar{\Omega}_C \leftarrow \bar{\mu}_x H + \mu_r \bar{G}$</td><td></td></tr><tr><td>5: $\Omega_{\bar{c}} \leftarrow h^{\mu_r} \cdot \prod_{i=1}^{\ell} g_i^{(\mu_m)_i} \bmod N$</td><td></td></tr><tr><td></td><td>$\bar{c}, \Omega_F, \bar{\Omega}_C, \Omega_{\bar{c}}$</td></tr><tr><td></td><td>6: $\gamma \leftarrow [0, C]$</td></tr><tr><td></td><td>$\gamma$</td></tr><tr><td>7: $\bar{\tau}_m \leftarrow \gamma \bar{m} + \bar{\mu}_m$</td><td></td></tr><tr><td>8: check $\bar{\tau}_m \in [\bar{B}C, (\bar{B}C + 1)L]$</td><td></td></tr><tr><td>9: $\tau_r \leftarrow \gamma r + \mu_r \bmod p, \tau_{\bar{r}} \leftarrow \gamma \bar{r} + \mu_{\bar{r}}$</td><td></td></tr><tr><td></td><td>$\bar{\tau}_m, \tau_r, \tau_{\bar{r}}$</td></tr><tr><td></td><td>10: check $\bar{\tau}_m \in [0, (\bar{B}C + 1)L]$</td></tr><tr><td></td><td>11: check $\Omega_F + \gamma F = \tau_r H$</td></tr><tr><td></td><td>12: check $\Omega_C + \gamma \bar{C} = \bar{\tau}_m H + \tau_r \bar{G}$</td></tr><tr><td></td><td>13: check $\Omega_{\bar{c}} \cdot (\bar{c})^{\gamma} = h^{\bar{\tau}_r} \cdot \prod_{i=1}^{\ell} g_i^{(\bar{\tau}_m)_i} \bmod N$</td></tr></tbody></table>

runs in time $O((1 - \frac{1}{L})^{-\ell})$ in expectation. In case of no abort, the verification equations verify by construction.

**Subversion zero-knowledge.** This follows with standard arguments. We sketch the zero-knowledge simulator below. The simulator samples a challenge $\gamma_{\Sigma} \leftarrow [0, C]$ and $\bar{\tau}_m \leftarrow [\bar{B}C, (\bar{B}C+1)L]$, $\tau_r \leftarrow \mathbb{Z}_p$ and $\tau_{\bar{r}} \leftarrow [0, (\bar{B}C+1)L]$. It is easy to check that the response follows the honest distribution (conditioned on no abort due to Appendix A.2). Next, the simulator an MPed commitment $\bar{c}$ to zero. Because for any $\text{srs} \in \text{SRS}$, the scheme MPed is statistically hiding (under soundness of $\Pi_{\text{gen}}$), this commitment also follows the distribution of honestly generated $\bar{c}$ with negligible statistical distance. Finally, the simulator samples $\Omega_F, \bar{\Omega}_C, \Omega_{\bar{c}}$ according to the verification equations, and sets

$$- \Omega_{\Sigma} = (\bar{c}, \Omega_F, \bar{\Omega}_C, \Omega_{\bar{c}}),$$

$$- \tau_{\Sigma} = (\bar{\tau}_m, \tau_r, \tau_{\bar{r}}).$$

Before the simulator outputs the proof $\pi = (\Omega_{\Sigma}, \gamma_{\Sigma}, \tau_{\Sigma})$, it programs the random oracle $H_{\text{int}}$ accordingly. Observe that the underlying $\Sigma$-protocol has high min-entropy (since $\Omega_F$ is distributed uniform over $\mathbb{G}$), thus $H_{\text{int}}$ is not defined at input $(x_{\Sigma}, \bar{c}, \Omega_F, \bar{\Omega}_C, c_Z \bar{c})$ yet with overwhelming probability. As discussed above, conditioned on no abort, the proof $\pi$ is identically distributed to honestly generated proofs. Repetitions due to aborts are only noticeable if the adversary observes $H_{\text{int}}$ queries for aborted transcripts. Due to high min-entropy, this occurs only with negligible probability.
**Adaptive knowledge soundness.** For soundness, we obtain two valid transcripts $tr = (\alpha, \gamma, \omega)$, $tr' = (\alpha, \gamma', \omega')$ with shared $\alpha = (\bar{c}, \Omega_F, \bar{\Omega}_C, \Omega_{\bar{c}})$ but distinct challenges $\gamma \neq \gamma'$ via the forking lemma (cf. Appendix A.2). Parse $\omega = (\vec{\tau}_m, \tau_r, \tau_{\bar{r}})$ and $\omega' = (\vec{\tau}_{m'}, \tau_{r'}, \tau_{\bar{r}'})$. Let us denote $\Delta \vec{m} = \vec{\tau}_m - \vec{\tau}_{m'}$, $\Delta r = \tau_r - \tau_{r'}$, $\Delta \bar{r} = \tau_{\bar{r}} - \tau_{\bar{r}'}$, and $\Delta \gamma = \gamma - \gamma' \neq 0$. Without loss of generality, we have $\Delta \gamma \in [0, C]$. Since both transcripts are valid (with shared $\alpha = \alpha'$), we have

$$ \Omega_F = \tau_r H - \gamma F = \tau_{r'} H - \gamma' F $$

Rearranging both terms yields

$$ \begin{aligned} \tau_r H - \tau_{r'} H &= -\gamma' F + \gamma F \\ \implies \Delta \gamma F &= \Delta r H \\ \implies F &= \frac{\Delta r}{\Delta \gamma} H \end{aligned} $$

Similarly, we obtain

$$ \vec{C} = \frac{\Delta \vec{m}}{\Delta \gamma} H + \frac{\Delta r}{\Delta \gamma} \vec{G} $$

Thus, $\vec{m} := \frac{\Delta \vec{m}}{\Delta \gamma}$ and $r = \frac{\Delta r}{\Delta \gamma}$ form a valid opening for $c$ if $\vec{m} \in [-\vec{B}T, \vec{B}T]$. For this, we use the properties of $\bar{c}$. As above, we obtain

$$ \begin{aligned} & h^{\tau_{\bar{r}}} \cdot \prod_{i=1}^{\ell} g_i^{(\tau_m)_i} \cdot (\bar{c})^{-\gamma} = h^{\tau_{\bar{r}'}} \cdot \prod_{i=1}^{\ell} g_i^{(\tau_{m'})_i} \cdot (\bar{c})^{-\gamma'} \mod N \\ \implies & h^{\Delta \bar{r}} \cdot \prod_{i=1}^{\ell} g_i^{(\Delta m)_i} = (\bar{c})^{\Delta \gamma} \mod N \end{aligned} $$

Recall that $\Delta \gamma \in [0, C]$ with $C = 2^{\lambda} - 1$. Under lemma 6, we have $\Delta \bar{r}/\Delta \gamma$, $(\Delta m)_i/\Delta \gamma \in \mathbb{Z}$. Also, since $(\tau_m)_i, (\tau_{m'})_i \in [0, (B_iC+1)L]$ we have that $|(\Delta m)_i/\Delta \gamma| \le 2(B_iC+1)L$. Since $2(B_iC+1)L \le 2^{\lambda+1}B_iL = T_iL$, we have $\vec{m} \in [-\vec{B}T, \vec{B}T]$ as desired.

**Efficient Proof of Opening for $C_{Grp}$.** A commitment of $C_{Grp}$ consists of a Pedersen commitment (in $\hat{G}$) and a $C_{RInt}$ commitment. If $C_{RInt}$ is instantiated as in Section 5.1, it is straightforward to obtain a NIZK for opening $C_{Grp}$ in zero-knowledge using the techniques from Appendix C.1 (since the decomposition of $s$ is linear). An example of this NIZK is given within the NIZK provided in Appendix E.2.

# D Deferred content from Section 6

## D.1 Number of primes in $[2^{5\lambda}, 2^{5\lambda} + 2^{3\lambda}]$

**Lemma 1.** For $E = 2^{3\lambda}, \bar{E} = 2^{5\lambda}$, there are $\Omega(2^{2\lambda})$ primes in $S_e = [\bar{E}, \bar{E} + E]$.

*Proof.* We prove that there are $\Omega(2^{2\lambda})$ in the interval $[2^{5\lambda}, 2^{5\lambda} + 2^{3\lambda}]$. In the following we denote by $\pi(x)$ the number of primes at most $x$, for any $x \in \mathbb{R}$ is a function of $\lambda$. In the following we use $\sim$ to write the limit as $\lambda \to \infty$. We want to estimate

$$ \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) \qquad (7) $$

which is the number of primes in $[2^{5\lambda}, 2^{5\lambda} + 2^{3\lambda}]$. First, from a recent result [58], which refines the celebrated Huxley's bound [60, 57], we have

$$ \pi(x + y) - \pi(x) \sim y/\log x $$
for Huxley's range $x^{7/12} \le y \le x$. Setting $x = 2^{5\lambda}$ and $y = 2^{3\lambda}$, while noticing that $7/12 < 3/5$ yields

$$ \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) \sim \frac{2^{3\lambda}}{5\lambda}. \qquad (8) $$

The approximation Eq. (8) means that for any $\epsilon > 0$, there exists $\lambda_0 \in \mathbb{R}_{>0}$ such that for sufficiently large $\lambda > \lambda_0$, the number of primes between $2^{5\lambda}$ and $2^{5\lambda} + 2^{3\lambda}$ satisfies

$$ \left| \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) - \frac{2^{3\lambda}}{5\lambda} \right| \le \epsilon. \qquad (9) $$

We choose $\epsilon := \frac{1}{5} > 0$ and (9) implies: for sufficiently large $\lambda$

$$ \begin{aligned} \left| \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) - \frac{2^{3\lambda}}{5\lambda} \right| &\le \frac{1}{5} \Rightarrow \frac{2^{3\lambda}}{5\lambda} - \frac{1}{5} \le \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) \\ &\Rightarrow \frac{2^{3\lambda} - \lambda}{5\lambda} \le \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) . \end{aligned} $$

In other words, we have

$$ \pi(2^{5\lambda} + 2^{3\lambda}) - \pi(2^{5\lambda}) = \Omega\left(\frac{2^{3\lambda} - \lambda}{\lambda}\right) = \Omega(2^{2\lambda}) $$

and the claim is proved. $\square$

## D.2 Proof of lemma 2 and Corollary 1

**Lemma 2.** Let $\lambda \in \mathbb{N}$ and $N > 3$ be an odd natural number of bitlength polynomially large in $\lambda$. We consider $\mathbb{Z}_N^*$ and fix $\mathbb{G} = \langle g \rangle \subseteq \mathbb{Z}_N^*$ where $g \in \mathbb{Z}_N^*$. Given $e \leftarrow S_e$ where $S_e$ contains at least $\Omega(2^\lambda)$ primes, we have

$$ \mathrm{Pr} [\langle g^e \rangle \neq \mathbb{G} : e \leftarrow S_e] \leq \mathrm{negl}(\lambda) $$

where the probability is taken over the choice of $e$.

*Proof.* We write $N = \prod_{i=1}^k p_i^{\nu_i}$ for some $k \in \mathbb{N}$ and $p_i \in S_e$ where $p_i > 2$ as $N$ is odd. We denote by $\ell(\lambda) : \mathbb{N} \to \mathbb{N}$ a polynomial dictating the bit length of $N$. Then, since $3 < N$ it holds that

$$ \begin{aligned} 2^{\ell(\lambda)} > N > \phi(N) &= \prod_{i=1}^{k} p_i^{\nu_i - 1} (p_i - 1) \\ &> \prod_{i=1}^{k} 2 > 2^k \end{aligned} \qquad (10) $$

and thus $k < \ell(\lambda)$, i.e. the number of distinct prime factors of $\phi(N)$ is at most $\ell(\lambda)$.

Moreover, we have $\langle g^e \rangle \subseteq \langle g \rangle$ if and only if $e \mid \mathrm{ord}(g)$. Because $\mathbb{G} = \langle g \rangle \subseteq \mathbb{Z}_N^*$, we have $\mathrm{ord}(g) \mid \phi(N)$ and from (10) it follows that the number of distinct prime factors of $\mathrm{ord}(g)$ is also at most $\ell(\lambda)$. Consequently, this implies

$$ \begin{aligned} \mathrm{Pr} [\langle g^e \rangle \subseteq \langle g \rangle : e \leftarrow S_e] &\le \mathrm{Pr} [e \mid \mathrm{ord}(g) : e \leftarrow S_e] \\ &\le \frac{k}{|S_e|} = O\left(\frac{\ell(\lambda)}{2^\lambda}\right) = \mathrm{negl}(\lambda) \end{aligned} $$

by the fact that $k < \ell(\lambda)$, $S_e$ contains at least $\Omega(2^\lambda)$, as well as $\ell(\lambda)$ is a polynomial in $\lambda^{28}$. The proof is completed. $\square$

<footnote n="28">28 In our blind signature scheme $\mathbf{BS}_{\text{fis}}$ (Fig. 1) we set $\ell(\lambda) := 2\lambda$.</footnote>
**Corollary 1.** Let $\lambda \in \mathbb{N}$ and $N > 3$ be an odd natural number of bitlength polynomially large in $\lambda$. We consider $Z_N^*$ and fix $\mathbb{G} = \langle g \rangle \subseteq Z_N^*$ where $g \in Z_N^*$. Given $e \leftarrow S_e$ where $S_e$ contains at least $\Omega(2^\lambda)$ primes, with overwhelming probability over the choice of $e$

$$ \psi : \mathbb{G} \to \langle g^e \rangle \\ z \mapsto z^e \mod N $$

is a group isomorphism.

*Proof.* Suppose $\langle g^e \rangle = \mathbb{G}$, we will prove that

$$ \psi : \mathbb{G} \to \langle g^e \rangle \\ z \mapsto z^e \mod N $$

which is a group isomorphism. For $a, b \in \mathbb{G}$, $\psi(ab^{-1}) = (ab^{-1})^e = \psi(a) \cdot \psi(b)^{-1} \mod N$ by arithmetic in $Z_N^*$. As a consequence $\psi$ is a group homomorphism. We now show that $\psi$ is surjective. Thanks to the hypothesis $\langle g^e \rangle = \mathbb{G}$, it holds that $\gcd(e, \mathrm{ord}(\mathbb{G})) = 1$, $\mathrm{ord}(\mathbb{G}) = \mathrm{ord}(\langle g^e \rangle)$, and $e^{-1} \mod \mathrm{ord}(\langle g^e \rangle)$ is well defined. Therefore, for any $z' \in \langle g^e \rangle$, we define $d := e^{-1} \mod \mathrm{ord}(\langle g^e \rangle)$, and $z := (z')^d \mod N$. It can be verified that

$$ \psi(z) = (z')^{ed} = z' \mod N $$

as $ed \equiv 1 \mod \mathrm{ord}(\langle g^e \rangle)$. Next, $\psi$ is injective if and only if $\ker(\psi) = \{1\}$. The inclusion $\{1\} \subseteq \ker(\psi)$ is clear. Suppose for the sake of contradiction that there exists $1 \neq z \in \mathbb{G}$ so that $\psi(z) = 1$. This implies $z^e \equiv 1 \mod N$ and thus $\mathrm{ord}(z) \mid e$. Moreover, from $1 \neq z \in \mathbb{G}$ it holds that $1 < \mathrm{ord}(z) \mid \mathrm{ord}(\mathbb{G})$ thanks to Larange. Combiningly we obtain $1 < \mathrm{ord}(z) \mid \gcd(e, \mathrm{ord}(\mathbb{G}))$, which contradicts the hypothesis that $\langle g^e \rangle = \mathbb{G}$. Therefore $\ker(\psi) = \{1\}$ and $\psi$ is injective.

Finally, with overwhelming probability over the choice of $e \leftarrow S_e$, lemma 2 concludes that $\langle g^e \rangle = \mathbb{G}$ and this finishes the proof. $\square$

### D.3 Blindness under Malicious Keys of BSfis - Proof of Theorem 3

**Theorem 3.** The scheme BSfis is blind under malicious keys following the subversion statistical adaptive soundness of $\Pi_{gen}$, the subversion zero-knowledge property of $\Pi_{fis}$, the computational hiding property of $C_{RInt}$, and the subversion zero-knowledge property of $\Pi_{ped}$.

*Proof.* We proceed by a sequence of hybrids. We denote by $\mathrm{Adv}_{A, \mathrm{Game}\ i}^{\mathrm{blind}}(\lambda)$ the probability that a PPT adversary $A$ outputs 1 in Game $i$. We assume that all the **check** steps are passed during the execution. This is not without loss of generality, but for the ease of presentation. In Remark 6 we elaborate on the cases when some **check** steps are not passed.

*Game 1:* We start with the game following Definition 3 where $\mathrm{coin} = 0$.

*Game 2:* This hybrid is the same as Game 1, except that we use the subversion zero-knowledge simulator $\mathrm{Sim}_{\mathrm{fis}} = (\mathrm{Sim}_{\mathrm{H}, \mathrm{fis}}, \mathrm{Sim}_{\pi, \mathrm{fis}})$ of $\Pi_{\mathrm{fis}}$ to simulate $\pi_{\mathrm{fis}}$ in the derived signature $\sigma = (\pi_{\mathrm{fis}}, c_I)$. Game 2 differs from Game 1 in the following details. We program the unstructured reference string $\mathrm{urs}_{\mathrm{fis}}$ in $(\mathrm{urs}_{\mathrm{ped}}, \mathrm{urs}_{\mathrm{fis}}, \mathrm{urs}_{\mathrm{gen}}) \leftarrow \mathrm{H}_{\mathrm{urs}}(0)$ together with honest $\mathrm{urs}_{\mathrm{ped}}, \mathrm{urs}_{\mathrm{gen}} \in \mathcal{URS}$. The blindness adversary $A$ also sets up $\mathrm{srs}_{\mathrm{zkp}}$ for $\mathrm{zkp} \in \{\mathrm{ped}, \mathrm{fis}, \mathrm{gen}\}$. The common reference strings are defined, in particular $\mathrm{crs}_{\mathrm{fis}} = (\mathrm{srs}_{\mathrm{fis}}, \mathrm{urs}_{\mathrm{fis}})$ along with $\mathrm{crs}_{\mathrm{ped}}, \mathrm{crs}_{\mathrm{gen}}$ in bvk. We program $\mathrm{H}_{\mathrm{fis}}$ by $\mathrm{Sim}_{\mathrm{H}, \mathrm{fis}}$ for further RO queries. Then, run $\pi_{\mathrm{fis}} \leftarrow \mathrm{Sim}_{\pi, \mathrm{fis}}(\mathrm{crs}_{\mathrm{fis}}, x_{\mathrm{fis}})$. The following lemma 7 argues that Game 2 and Game 1 are indistinguishable. In particular, for any blindness adversary $A$, there exist PPT $B_1, B_2, B_3$ so that

$$ |\mathrm{Adv}_{A, \mathrm{Game}\ 2}^{\mathrm{blind}}(\lambda) - \mathrm{Adv}_{A, \mathrm{Game}\ 1}^{\mathrm{blind}}(\lambda)| \leq \mathrm{Adv}_{B_2, \Pi_{gen}}^{\mathrm{rnd}}(\lambda) + \mathrm{Adv}_{B_3, \Pi_{\mathrm{fis}}}^{\mathrm{sub-zk}}(\lambda) + \mathrm{negl}(\lambda) . $$

and is negligible in $\lambda$.
**Lemma 7.** Under the subversion zero-knowledge of $\Pi_{fis}$ as well as the subversion adaptive soundness $\Pi_{gen}$, the games Game 2 and Game 1 are indistinguishable. For any blindness adversary $\mathcal{A}$, there exist PPT $\mathcal{B}_2, \mathcal{B}_3$ so that

$$|\text{Adv}_{\mathcal{A}, \text{Game } 2}^{\text{blind}}(\lambda) - \text{Adv}_{\mathcal{A}, \text{Game } 1}^{\text{blind}}(\lambda)| \le \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).$$

*Proof.* By construction, with respect to the relation $\mathbb{R}_{fis}$, the values $e, (c_I, d_I), r_I$ determined by the user satisfy:

$$\left\{ \begin{array}{l} e \equiv 1 \bmod 2 \\ (c_I, d_I) = \mathbb{C}_{\text{RInt}} \cdot \text{Commit}(\text{pp}_I, (a, e - \bar{E}); r_I) = 1, \\ e \in \mathcal{S}_e \end{array} \right. .$$

We also recall that $c = h_2^{\overline{m}} \cdot g^r \bmod N$ in the first message to the blindness adversary $\mathcal{A}$ and $y \leftarrow z \cdot g^{-r} \bmod N$ during the signature derivation are both computed by the user. Moreover, we suppose that all the **check** steps are passed during the execution, it holds $a \in \mathcal{S}_a$ as a part in the relation $\mathbb{R}_{fis}$. Now, using the simulation as described in Game 2, there are three cases to treat as follows:

**Case 1:** Suppose that $x_{fis} \notin \mathcal{L}_{\mathbb{R}_{fis}}$ and $y^e \neq h \cdot h_1^a \cdot h_2^{a+\overline{m}} \bmod N$. This implies

$$\begin{array}{l@{\qquad}l}
\begin{array}{@{}l@{}}
  \begin{array}{@{}l@{}}
    y^e \\
    \Rightarrow z^e \cdot g^{-re}
  \end{array}
\end{array}
&
\begin{array}{@{}l@{}}
  \begin{array}{@{}l@{}}
    \neq h \cdot h_1^a \cdot h_2^{a+\overline{m}} \bmod N \\
    \neq h \cdot h_1^a \cdot h_2^{a+\overline{m}} \bmod N
  \end{array} \\
  \begin{array}{@{}l@{}}
    \neq h \cdot h_1^a \cdot h_2^{\overline{m}} \cdot g^r \cdot h_2^a \bmod N \\
    \neq h \cdot h_1^a \cdot c \cdot h_2^a \bmod N
  \end{array} \\
  \begin{array}{@{}l@{}}
    (\dagger) \\
    \neq z' \bmod N
  \end{array}
\end{array}
\end{array}$$

From Corollary 1, with overwhelming probability over the choice of $e \leftarrow \mathcal{S}_e$, raising to the power of $e$ is a bijection. Therefore, except with negligible probability, inequality (†) contradicts the fact that during **Derive** it is set $z' \leftarrow h \cdot h_1^a \cdot c \cdot h_2^a$ and the hypothesis that the **check** $z^e \equiv z' \bmod N$ holds. Equivalently, this current case with the inequality (†) happens only with negligible probability.

**Case 2:** Suppose that $x_{fis} \notin \mathcal{L}_{\mathbb{R}_{fis}}$ and $y^e \equiv h \cdot h_1^a \cdot h_2^{a+\overline{m}} \bmod N$ but $y \notin \langle h_1 \rangle$. Due to the hypotheses that $y^e \equiv h \cdot h_1^a \cdot h_2^{a+\overline{m}} \bmod N$ and $y \notin \langle h_1 \rangle$, we have $\langle h_1 \rangle \neq \langle h \rangle$ or $\langle h_1 \rangle \neq \langle h_2 \rangle$. Recalling that without loss of generality we are supposing all the **check** steps are passed during the execution, in particular $\Pi_{gen}$. **Verify}^{\text{H}_{\text{gen}}}(\text{crs}_{\text{gen}}, x_{\text{gen}}, \pi_{\text{gen}}) = 1$. This means we obtain an instance $(N, 3, g, (h, h_1, h_2))$ that breaks the subversion soundness of $\Pi_{gen}$.

We provide a PPT adversary $\mathcal{B}_2$ breaking the subversion soundness of $\Pi_{gen}$ as follows:

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

- The blindness adversary $\mathcal{A}$ sets up $\text{srs}_{zkp}$ for $zkp \in \{\text{ped}, \text{fis}, \text{gen}\}$. The common reference strings are defined, in particular $\text{crs}_{fis} = (\text{srs}_{fis}, \text{urs}_{fis})$ along with $\text{crs}_{ped}, \text{crs}_{gen}$ in $\text{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}_2$ outputs the instance $(N, 3, g, (h, h_1, h_2))$ to its challenger against the subversion soundness of $\Pi_{gen}$.

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

**Case 3:** Finally, suppose that $x_{fis} \in \mathcal{L}_{\mathbb{R}_{fis}}$. The adversary $\mathcal{A}$ can be used to construct a PPT $\mathcal{B}_3$ against the subversion zero-knowledge (S-ZK) game of $\Pi_{fis}$ as below:

- $\mathcal{B}_3$ receives $\text{urs}_{fis}$ from the S-ZK challenger and program $\text{urs}_{fis}$ intp the output of $\mathbb{H}_{urs}(0)$, together with honest $\text{urs}_{ped}, \text{urs}_{gen} \in \mathcal{URS}$.

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