International Association
for Cryptologic Research

Non-interactive blind signatures (NIBS), introduced by Hanzlik (Eurocrypt'23), enable the issuance of blind signatures on random messages without requiring interaction and have found applications in a variety of privacy-preserving protocols. Despite recent progress, all known constructions of NIBS rely on the random oracle model and/or the common reference string model, or on complexity-leveraging techniques. As a result, constructing such schemes in the plain model under standard assumptions remains an open problem. In this work, we present new results showing that it is hard to construct NIBS in the plain model from standard assumptions, as long as the adversary is used in a black-box manner. Specifically, we first focus on black-box reductions for basing the security of statistically blind NIBS on any non-interactive assumption. We then extend this limitation to the computationally blind setting under conditions inspired by the known impossibility results for standard blind signatures, introduced by Fischlin and Schröder (Eurocrypt'10). As an independent contribution, we study the relationship between two strong notions of blindness—strong recipient blindness and strong nonce blindness—recently introduced by Baldimtsi et al. (Asiacrypt'24). We show the separation result by constructing schemes that satisfy strong recipient blindness but not strong nonce blindness, and vice versa. Our results suggest that both notions are independently necessary for the provable security of NIBS schemes.