Rai-Choo! Evolving Blind Signatures to the Next Level

Lucjan Hanzlik; Julian Loss; Benedikt Wagner

Paper 2022/1350

Rai-Choo! Evolving Blind Signatures to the Next Level

Lucjan Hanzlik, CISPA Helmholtz Center for Information Security

Julian Loss

, CISPA Helmholtz Center for Information Security

Benedikt Wagner

, CISPA Helmholtz Center for Information Security, Saarland University

Abstract

Blind signatures are a fundamental tool for privacy-preserving applications. Known constructions of concurrently secure blind signature schemes either are prohibitively inefficient or rely on non-standard assumptions, even in the random oracle model. A recent line of work (ASIACRYPT `21, CRYPTO `22) initiated the study of concretely efficient schemes based on well-understood assumptions in the random oracle model. However, these schemes still have several major drawbacks: 1) The signer is required to keep state; 2) The computation grows linearly with the number of signing interactions, making the schemes impractical; 3) The schemes require at least five moves of interaction. In this paper, we introduce a blind signature scheme that eliminates all of the above drawbacks at the same time. Namely, we show a round-optimal, concretely efficient, concurrently secure, and stateless blind signature scheme in which communication and computation are independent of the number of signing interactions. Our construction also naturally generalizes to the partially blind signature setting. Our scheme is based on the CDH assumption in the asymmetric pairing setting and can be instantiated using a standard BLS curve. We obtain signature and communication sizes of 9KB and 36KB, respectively. To further improve the efficiency of our scheme, we show how to obtain a scheme with better amortized communication efficiency. Our approach batches the issuing of signatures for multiple messages.

Note: minor editorial revision

Metadata

Available format(s): PDF
Category: Public-key cryptography
Publication info: A minor revision of an IACR publication in EUROCRYPT 2023
Keywords: Blind Signatures Standard Assumptions Random Oracle Model Cut-and-Choose Computation Complexity Round Complexity
Contact author(s): hanzlik @ cispa de
loss @ cispa de
benedikt wagner @ cispa de
History: 2023-02-24: last of 2 revisions; 2022-10-10: received; See all versions
Short URL: https://ia.cr/2022/1350
License: CC BY

BibTeX

@misc{cryptoeprint:2022/1350,
      author = {Lucjan Hanzlik and Julian Loss and Benedikt Wagner},
      title = {Rai-Choo! Evolving Blind Signatures to the Next Level},
      howpublished = {Cryptology ePrint Archive, Paper 2022/1350},
      year = {2022},
      note = {\url{https://eprint.iacr.org/2022/1350}},
      url = {https://eprint.iacr.org/2022/1350}
}