Paper 2022/007

PI-Cut-Choo! Parallel Instance Cut and Choose for Practical Blind Signatures

Benedikt Wagner and Lucjan Hanzlik and Julian Loss

Abstract

Known constructions of (efficient) blind signatures either rely on non-standard hardness assumptions or require parameters that grow linearly with the number of concurrently issued signatures. This holds true even in the random oracle model. Katz, Loss and Rosenberg (ASIACRYPT 2021) presented a generic construction that boosts a scheme supporting logarithmically many concurrent signing sessions to a scheme that supports polynomially many. Unfortunately, this construction has two drawbacks: 1) the communication between the signer and the user still grows linearly with the number of issued signatures 2) their schemes inherit a very loose security bound from the underlying scheme and, as a result, require impractical parameter sizes. In this paper, we eliminate these two drawbacks by proposing two highly practical blind signature schemes from the CDH and RSA assumptions. Our resulting schemes have communication which grows only logarithmically in the number of issued signatures. In addition, we introduce new techniques to mitigate the large security loss in the construction of Katz et al. Overall, we obtain the following parameter sizes (providing 128 bits of security): - Our main scheme PIKA is based on the BLS blind signature scheme (Boldyreva, PKC 2003) and is secure under the \cdh assumption over a standard-sized group. Signatures are of size roughly 3KB and communication per signature is roughly 150KB. - Our RSA-based scheme is based on the Okamoto-Guillou-Quisquater blind signature scheme (Okamoto, CRYPTO 1992). It has signatures and communication of roughly 9KB and 8KB, respectively.