Paper 2022/007

PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More

Rutchathon Chairattana-Apirom, Lucjan Hanzlik, Julian Loss, Anna Lysyanskaya, and Benedikt Wagner


Blind signature schemes are one of the best-studied tools for privacy-preserving authentication. Unfortunately, known constructions of provably secure blind signatures either rely on non-standard hardness assumptions, or require parameters that grow linearly with the number of concurrently issued signatures, or involve prohibitively inefficient general techniques such as general secure two-party computation. Recently, Katz, Loss and Rosenberg (ASIACRYPT'21) gave a technique that, for the security parameter n transforms blind signature schemes secure for O(log n) concurrent executions of the blind signing protocol into ones that are secure for any poly(n) concurrent executions. This transform has two drawbacks that we eliminate in this paper: 1) the communication complexity of the resulting blind signing protocol grows linearly with the number of signing interactions; 2) the resulting schemes inherit a very loose security bound from the underlying scheme and, as a result, require impractical parameter sizes. In this work, we give an improved transform for obtaining a secure blind signing protocol tolerating any poly(n) concurrent executions from one that is secure for O(log n) concurrent executions. While preserving the advantages of the original transform, the communication complexity of our new transform only grows logarithmically with the number of interactions. Under the CDH and RSA assumptions, we improve on this generic transform in terms of concrete efficiency and give (1) a BLS-based blind signature scheme over a standard-sized group where signatures are of size roughly 3 KB and communication per signature is roughly 120 KB; and (2) an Okamoto-Guillou-Quisquater-based blind signature scheme with signatures and communication of roughly 9 KB and 8 KB, respectively.

Note: This article is a merge of eprint article 2022/003 and the previous version of this article.

Available format(s)
Publication info
Preprint. MINOR revision.
Blind SignaturesStandard AssumptionsRandom Oracle ModelCut-and-Choose.
Contact author(s)
rutchathon_chairattana-apirom @ brown edu
anna_lysyanskaya @ brown edu
hanzlik @ cispa de
loss @ cispa de
benedikt wagner @ cispa de
2022-03-15: revised
2022-01-07: received
See all versions
Short URL
Creative Commons Attribution


      author = {Rutchathon Chairattana-Apirom and Lucjan Hanzlik and Julian Loss and Anna Lysyanskaya and Benedikt Wagner},
      title = {PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More},
      howpublished = {Cryptology ePrint Archive, Paper 2022/007},
      year = {2022},
      note = {\url{}},
      url = {}
Note: In order to protect the privacy of readers, does not use cookies or embedded third party content.