cispa_all_3693.pdf (964.9 kB)

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

Download (964.9 kB)
conference contribution
posted on 2023-11-29, 18:21 authored by Rutchathon Chairattana-Apirom, Benedikt WagnerBenedikt Wagner, Lucjan HanzlikLucjan Hanzlik, Julian LossJulian Loss, Anna Lysyanskaya
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.


Preferred Citation

Rutchathon Chairattana-Apirom, Benedikt Wagner, Lucjan Hanzlik, Julian Loss and Anna Lysyanskaya. PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More. In: Advances in Cryptology (CRYPTO). 2022.

Primary Research Area

  • Algorithmic Foundations and Cryptography

Name of Conference

Advances in Cryptology (CRYPTO)

Legacy Posted Date


Open Access Type

  • Unknown


@inproceedings{cispa_all_3693, title = "PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More", author = "Chairattana-Apirom, Rutchathon and Wagner, Benedikt and Hanzlik, Lucjan and Loss, Julian and Lysyanskaya, Anna", booktitle="{Advances in Cryptology (CRYPTO)}", year="2022", }

Usage metrics


    No categories selected


    Ref. manager