Blind Signatures from Arguments of Inequality

Abstract. Blind signatures are an important tool for privacy-preserving applications with a long history dating back to Chaum’s seminal work in Crypto’82. In this work, we present the first pairing-free blind signature in the random oracle model that is concurrently-secure under the discrete logarithm assumption (without the algebraic group model). On a technical level, our work extends the recent proofs of inequality technique (Klooß and Reichle, Crypto’25) to arguments of inequality. The original technique relies on puncturing the verification key to make forgeries statistically impossible. We show how computational puncturing can be used, which opens the possibilities of applying the technique under weaker assumptions, at the cost of requiring a rewinding-based security reduction. In particular, this demonstrates that (notoriously difficult) rewinding-based techniques are still a viable path to Fiat–Shamir-based blind signatures.