Paper 2020/1071

On Pairing-Free Blind Signature Schemes in the Algebraic Group Model

Julia Kastner, Julian Loss, and Jiayu Xu


Studying the security and efficiency of blind signatures is an important goal for privacy sensitive applications. In particular, for large-scale settings (e.g., cryptocurrency tumblers), it is important for schemes to scale well with the number of users in the system. Unfortunately, all practical schemes either 1) rely on (very strong) number theoretic hardness assumptions and/or computationally expensive pairing operations over bilinear groups, or 2) support only a polylogarithmic number of concurrent (i.e., arbitrarily interleaved) signing sessions per public key. In this work, we revisit the security of two pairing-free blind signature schemes in the Algebraic Group Model (AGM) + Random Oracle Model (ROM). Concretely, 1. We consider the security of Abe’s scheme (EUROCRYPT ‘01), which is known to have a flawed proof in the plain ROM. We adapt the scheme to allow a partially blind variant and give a proof of the new scheme under the discrete logarithm assumption in the AGM+ROM, even for (polynomially many) concurrent signing sessions. 2. We then prove that the popular blind Schnorr scheme is secure under the one-more discrete logarithm assumption if the signatures are issued sequentially. While the work of Fuchsbauer et al. (EUROCRYPT ‘20) proves the security of the blind Schnorr scheme for concurrent signing sessions in the AGM+ROM, its underlying assumption, ROS, is proven false by Benhamouda et al. (EUROCRYPT‘21) when more than polylogarithmically many signatures are issued. Given the recent progress, we present the first security analysis of the blind Schnorr scheme in the slightly weaker sequential setting. We also show that our security proof reduces from the weakest possible assumption, with respect to known reduction techniques.

Note: full version of PKC paper

Available format(s)
Public-key cryptography
Publication info
A major revision of an IACR publication in PKC 2022
anonymityimplementationagmcryptographic modelsprotocols
Contact author(s)
julia kastner @ inf ethz ch
lossjulian @ gmail com
jxu27 @ gmu edu
jiayux @ uci edu
2022-01-13: last of 3 revisions
2020-09-09: received
See all versions
Short URL
Creative Commons Attribution


      author = {Julia Kastner and Julian Loss and Jiayu Xu},
      title = {On Pairing-Free Blind Signature Schemes in the Algebraic Group Model},
      howpublished = {Cryptology ePrint Archive, Paper 2020/1071},
      year = {2020},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.