International Association for Cryptologic Research

International Association
for Cryptologic Research


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

Julia Kastner , Department of Computer Science, ETH Zurich, Zurich, Switzerland
Julian Loss , CISPA Helmholtz Center for Information Security, Saarbrücken, Germany
Jiayu Xu , Algorand, Boston, MA, USA
Search ePrint
Search Google
Presentation: Slides
Conference: PKC 2022
Abstract: 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 hard- ness 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 un- der the one-more discrete logarithm assumption if the signatures are issued sequentially. While the work of Fuchsbauer et al. (EURO- CRYPT ‘20) proves the security of the blind Schnorr scheme for con- current signing sessions in the AGM+ROM, its underlying assump- tion, 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.
Video from PKC 2022
  title={On Pairing-Free Blind Signature Schemes in the Algebraic Group Model},
  author={Julia Kastner and Julian Loss and Jiayu Xu},