Three-Move Blind Signatures in Pairing-Free Groups

We propose the first blind signature scheme that simultaneously achieves the following properties:

• It uses a pairing-free group and random oracles in a black-box manner;
• It provably achieves concurrent security based on standard assumptions (DDH) without the algebraic group model (AGM);
• It requires only three moves. Moreover, the public key, signature, and communication of our scheme all consist of only a constant number of group/field elements.

Prior to our work, black-box, three-move pairing-free schemes were only known in the AGM. A recent line of work proposed and optimized schemes without the AGM, but they all require at least four moves.