Cryptology ePrint Archive: Report 2020/1071

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

Julia Kastner and Julian Loss and Michael Rosenberg and Jiayu Xu

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, group-based schemes either 1) rely on (very strong) number theoretic hardness assumptions and computationally expensive pairing operations over bilinear groups or 2) support only a polylogarithmic number of \emph{concurrent} (i.e., arbitrarily interleaved) signing sessions per public key. Following the recent work of Fuchsbauer et al. (EUROCRYPT `20), we revisit the security of two \emph{pairing-free} blind signature schemes in the algebraic group model (AGM) + Random Oracle Model (ROM). First, we prove that the popular blind Schnorr scheme is secure under the one-more discrete logarithm assumption if (polynomially many) signatures are issued \emph{sequentially}. This stands in stark contrast to the results of Fuchsbauer et al. and Benhamouda et al. (EPRINT `20). Under the same assumptions, their (combined) results imply security against a polynomial time attacker iff the signer opens at most polylogarithmically many \emph{concurrent} signing sessions. We then reconsider the security of Abe's scheme (EUROCRYPT `01), which is known to have a flawed proof in the plain ROM. We give a proof under the discrete logarithm assumption in the AGM+ROM, even for (polynomially many) \emph{concurrent} signing sessions. Finally, we demonstrate that these pairing-free signature schemes are immediately usable in a real-world setting. Using a cryptocurrency tumbling service as a model, we benchmark the Schnorr and Abe schemes under different workloads and degrees of parallelism and conclude that they can both handle large workloads at reasonable security levels, and have distinct optimal use cases.

Category / Keywords: public-key cryptography / anonymity, implementation, agm, cryptographic models, protocols

Date: received 3 Sep 2020, last revised 13 Sep 2020

Contact author: julia kastner at inf ethz ch,lossjulian@gmail com,micro@cs umd edu,jxu27@gmu edu

Available format(s): PDF | BibTeX Citation

Version: 20200913:235640 (All versions of this report)

Short URL:

[ Cryptology ePrint archive ]