You are looking at a specific version 20200913:235640 of this paper. See the latest version.

Paper 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.

Metadata
Available format(s)
PDF
Category
Public-key cryptography
Publication info
Preprint. MINOR revision.
Keywords
anonymityimplementationagmcryptographic modelsprotocols
Contact author(s)
julia kastner @ inf ethz ch,lossjulian @ gmail com,micro @ cs umd edu,jxu27 @ gmu edu
History
2022-01-13: last of 3 revisions
2020-09-09: received
See all versions
Short URL
https://ia.cr/2020/1071
License
Creative Commons Attribution
CC BY
Note: In order to protect the privacy of readers, eprint.iacr.org does not use cookies or embedded third party content.