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; Benedikt Wagner

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

Benedikt Wagner

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.

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

Metadata

Available format(s): PDF
Publication info: A minor revision of an IACR publication in CRYPTO 2022
Keywords: Blind Signatures Standard Assumptions Random Oracle Model Cut-and-Choose.
Contact author(s): rutchathon_chairattana-apirom @ alumni brown edu
hanzlik @ cispa de
loss @ cispa de
anna_lysyanskaya @ brown edu
benedikt wagner @ cispa de
History: 2022-07-25: last of 2 revisions; 2022-01-07: received; See all versions
Short URL: https://ia.cr/2022/007
License: CC BY

BibTeX

@misc{cryptoeprint:2022/007,
      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{https://eprint.iacr.org/2022/007}},
      url = {https://eprint.iacr.org/2022/007}
}