International Association
for Cryptologic Research

This paper presents new blind signatures for which concurrent security, in the random oracle model, can be proved from variants of the computational Diffie-Hellman (CDH) assumption in pairing-free groups without relying on the algebraic group model (AGM). With the exception of careful instantiations of generic non-black box techniques following Fischlin's paradigm (CRYPTO '06), prior works without the AGM in the pairing-free regime have only managed to prove security for a-priori bounded concurrency.

Our most efficient constructions rely on the chosen-target CDH assumption, which has been used to prove security of Blind BLS by Boldyreva (PKC '03), and can be seen as blind versions of signatures by Goh and Jarecki (EUROCRYPT '03) and Chevallier-Mames (CRYPTO'05). We also give a less efficient scheme with security based on (plain) CDH which builds on top of a natural pairing-free variant of Rai-Choo (Hanzlik, Loss, and Wagner, EUROCRYPT '23). Our schemes have signing protocols that consist of four (in order to achieve regular unforgeability) or five moves (for strong unforgeability).

The blindness of our schemes is either computational (assuming the hardness of the discrete logarithm problem), or statistical in the random oracle model.