International Association for Cryptologic Research

International Association
for Cryptologic Research

CryptoDB

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

Authors:
Rutchathon Chairattana-Apirom , Brown University
Lucjan Hanzlik , CISPA Helmholtz Center for Information Security
Julian Loss , CISPA Helmholtz Center for Information Security
Anna Lysyanskaya , Brown University
Benedikt Wagner , CISPA Helmholtz Center for Information Security
Download:
Search ePrint
Search Google
Presentation: Slides
Conference: CRYPTO 2022
Abstract: 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.
Video from CRYPTO 2022
BibTeX
@inproceedings{crypto-2022-32180,
  title={PI-Cut-Choo and Friends: Compact Blind Signatures via Parallel Instance Cut-and-Choose and More},
  publisher={Springer-Verlag},
  author={Rutchathon Chairattana-Apirom and Lucjan Hanzlik and Julian Loss and Anna Lysyanskaya and Benedikt Wagner},
  year=2022
}