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

. 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.