Blind signatures, introduced by Chaum (Crypto’82), are a fundamental cryptographic primitive with various applications such as e-voting, e-cash, anonymous credentials, and more. Although blind signatures inherently require interaction between both parties, Hanzlik (Eurocrypt’23) introduced the notion of non-interactive blind signatures ( \(\textsf{NIBS}\) ), which allow signatures on random messages to be issued blindly without interaction. While Hanzlik’s \(\textsf{NIBS}\) constructions are provably secure in the random oracle model, instantiating a provably secure \(\textsf{NIBS}\) in the plain model remains an open problem. In this paper, we introduce a non-interactive blind signature scheme in the plain model based on complexity leveraging. The key to our construction is the use of the non-uniform reductions employed by Garg et al. (Crypto’11), which enables us to instantiate a provably secure \(\textsf{NIBS}\) without relying on a trusted setup. Furthermore, we investigate whether our construction can avoid the use of complexity leveraging by applying the idea proposed by Kalai and Khurana (Crypto’19), wherein complexity leveraging can be replaced with classical and quantum assumptions. We introduce a weaker blindness notion called non-adaptive blindness and show that this property allows our construction to avoid using complexity leveraging. Of independent interest, we provide separation results demonstrating the existence of a \(\textsf{NIBS}\) construction that satisfies nonce blindness but not recipient blindness, and vice versa. This result implies that any \(\textsf{NIBS}\) construction should be proven to satisfy both nonce blindness and recipient blindness.