Paper 2022/003

Merged with 2022/007

Rutchathon Chairattana-Apirom and Anna Lysyanskaya


Blind signature schemes are one of the best and best-studied tools for privacy-preserving authentication. It has a blind signing protocol in which a signer learns nothing about the message being signed or the resulting signature; thus such a signature can serve as an anonymous authentication token. Thus, constructing efficient blind signatures secure under realistic cryptographic assumptions is an important goal. A recent paper by Benhamouda, Lepoint, Loss, Orr\`u, and Raykova (Eurocrypt '21) showed that a large class of blind signature schemes secure in the stand-alone setting are no longer secure when multiple instances of the blind signing protocol are executed concurrently. The best known technique to salvage the security of such blind signatures was recently proposed by Katz, Loss, and Rosenberg (Asiacrypt '21). For the security parameter $\kappa$, their technique transforms blind signature schemes that are secure for $\mathcal{O}(\log \kappa)$ concurrent executions of the blind signing protocol into ones that are secure for any $N = \mathsf{poly}(\kappa)$ concurrent executions. The resulting, transformed blind signing protocol needs $\mathcal{O}(N)$ times more computation and communication than the original one. In this paper, we give an improved transform for obtaining a secure blind signing protocol tolerating $N = \mathsf{poly}(\kappa)$ concurrent executions from one that is secure for $\mathcal{O}(\log \kappa)$ concurrent executions. Our technique still needs $\mathcal{O}(N)$ times more computation, but only $\mathcal{O}(\log N)$ more communication than the original blind signature.

Note: Merged with

Available format(s)
Public-key cryptography
Publication info
Preprint. MINOR revision.
blind signaturesdigital signaturesanonymity
Contact author(s)
rutchathon c @ gmail com
anna @ cs brown edu
2022-03-15: revised
2022-01-01: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rutchathon Chairattana-Apirom and Anna Lysyanskaya},
      title = {Merged with 2022/007},
      howpublished = {Cryptology ePrint Archive, Paper 2022/003},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.