Paper 2022/003

Compact Cut-and-Choose: Boosting the Security of Blind Signature Schemes, Compactly

Rutchathon Chairattana-Apirom and Anna Lysyanskaya

Abstract

Blind signature schemes are one of the best and best-studied tools for privacy-preserving authentication. It has a blind signing protocol in which a signer learns nothing about the message being signed or the resulting signature; thus such a signature can serve as an anonymous authentication token. Thus, constructing efficient blind signatures secure under realistic cryptographic assumptions is an important goal. A recent paper by Benhamouda, Lepoint, Loss, Orr\`u, and Raykova (Eurocrypt '21) showed that a large class of blind signature schemes secure in the stand-alone setting are no longer secure when multiple instances of the blind signing protocol are executed concurrently. The best known technique to salvage the security of such blind signatures was recently proposed by Katz, Loss, and Rosenberg (Asiacrypt '21). For the security parameter $\kappa$, their technique transforms blind signature schemes that are secure for $\mathcal{O}(\log \kappa)$ concurrent executions of the blind signing protocol into ones that are secure for any $N = \mathsf{poly}(\kappa)$ concurrent executions. The resulting, transformed blind signing protocol needs $\mathcal{O}(N)$ times more computation and communication than the original one. In this paper, we give an improved transform for obtaining a secure blind signing protocol tolerating $N = \mathsf{poly}(\kappa)$ concurrent executions from one that is secure for $\mathcal{O}(\log \kappa)$ concurrent executions. Our technique still needs $\mathcal{O}(N)$ times more computation, but only $\mathcal{O}(\log N)$ more communication than the original blind signature.