On the Impossibility of Round-Optimal Pairing-Free Blind Signatures in the ROM

Blind signatures play a central role in cryptographic protocols for privacy-preserving authentication and have attracted substantial attention in both theory and practice. A major line of research, dating back to the 1990s, has focused on constructing blind signatures from pairing-free groups. However, all known constructions in this setting require at least three moves of interaction between the signer and the user. These schemes treat the underlying group as a black box and rely on the random oracle in their security proofs. While computationally efficient, they suffer from the drawback that the signer must maintain state during a signing session. In contrast, round-optimal solutions are known under other assumptions and structures (e.g., RSA, lattices, and pairings), or via generic transformations such as Fischlin's method (CRYPTO '06), which employ non-black-box techniques. This paper investigates whether the three-round barrier for pairing-free groups is inherent. We provide the first negative evidence by proving that, in a model combining the Random Oracle Model (ROM) with Maurer's Generic Group Model, no blind signature scheme can be secure if it signs sufficiently long messages while making at most a logarithmic number of random oracle queries. Our lower-bound techniques are novel in that they address the interaction of both models (generic groups and random oracles) simultaneously.

round trip between a user and the issuer. This is beneficial, as the issuer does not need to maintain any state associated with a particular signing session.

Round optimal blind signatures can also be obtained from pairing-friendly groups (e.g., [16,34,40]) and from lattices (e.g., [7,49,15]). The former can be very efficient, but require pairing support and are often avoided in practice, as pairings are not as widely supported by libraries and standards. The latter, while generally post-quantum secure, are still significantly less efficient than pairingand RSA-based counterparts. Another option is a generic construction by Fischlin [30], based on a commitment scheme, a (standard) signature scheme, and NIZKs, where the signer (non-blindly) signs a commitment to a message to be signed (rather than the message) itself, and the user then produces a proof of knowledge of a signature on a commitment to the message as the actual blind signature. Instantiations are however expensive.

Absent from our discussion above are constructions from pairing-free groups, typically obtained from standard elliptic curves. In some sense, these are most attractive, as very efficient signatures (such as Schnorr signatures [51], EdDSA [14], and ECDSA [8]) solely rely on these curves and it is advantageous to come with blind signing protocols for these (or similar) signatures. And furthermore, pairing-free constructions are equally likely to be implementable from existing libraries. Such constructions have been extensively studied (e.g., [24,52,47,50,6,32,37,54,26,20,43,42,17]), yet all of them to date require at least three moves. This not only forces the issuer to maintain state (hence making them less appealing for practice), but it also leads to challenges in proving their concurrent security, such as those surfaced by ROS attacks [52,55,13].

This paper: Round-optimal pairing-free blind signatures. We stress that in principle one could obtain a pairing-free blind signature by instantiating Fischlin's construction, but the use of non-black box techniques would increase the computational and communication costs substantially. All aforementioned blind signatures with at least three rounds, in contrast, make black box use of the underlying group and of a hash function, and this makes them very lightweight. We will capture the class of such schemes within a combination of Maurer's generic group model (GGM) [45] and the random oracle model (ROM) [12], which we formalize, and refer to generically as GGM+ROM. The class of blind signatures in the GGM+ROM prevents for example the use of generic zero-knowledge proofs (as required by Fischlin's construction) that represent a signature scheme as a circuit. It does not exclude Σ-protocol type proofs that are fully algebraic. We stress here that we do not rely on Shoup's GGM [53], as it allows for non-algebraic constructions which in particular make use of the generic-group encodings (such as what has been done in [25] to prove security of Schnorr signatures without relying on the random oracle model).

At the core of our paper is the following question:

Can we design round-optimal blind signatures from pairing-free groups in the GGM+ROM?

An informal folklore intuition says that this should not be possible. Namely, the standard known way towards a round optimal construction is to efficiently instantiate Fischlin's construction using an algebraic non-generic NIZK that leverages the algebraic structure of a signature scheme. However, such fully algebraic signature schemes are known not to exist in pairi