This paper presents a formal model for fair blind signature schemes and a provably secure scheme based on bilinear maps. A blind signature scheme is a protocol for obtaining a signature on a message which is unknown from the signer. Furthermore, the signer cannot link his transcript of a protocol to the resulting message-signature pair. Fair blind signatures were introduced by Stadler et al. at Eurocrypt’95 in [37]. A fair blind signature scheme is a blind signature scheme allowing two types of blindness revocation: link a signature to the session which conducted this signature (Session Tracing) or, conversely, identify a signature knowing a signing session (Signature Tracing). Various fair blind signature schemes have been proposed in the past years, but none of them presents a secure fair blind signature scheme that allows polynomially many signatures to be securely issued, even if Abe et al.’s claimed it in [3]. In this paper, we first show a flaw in the blindness of most (fair) blind signature schemes where the signer is able to link signatures if he chooses his keys in an appropriate way. Then, we show a flaw in the proof of unforgeability of Abe et al.’ scheme and propose a stronger security model than theirs. It possesses all the needed properties for fair blind signature schemes: blindness, traceability and non frameability for both revocations (the one-more unforgeability is implied by these properties). Finally, we describe a new fair blind signature scheme based on bilinear maps. This scheme thwarts the flaw against previous blind signatures and is proved secure in the random oracle model with respect to our model.