Security of ordinary digital signature schemes relies on a computational assumption. Fail-stop signature schemes provide security for a sender against a forger with unlimited computational power by enabling the sender to provide a proof of forgery, if it occurs. In this paper, we give an efficient fail-stop signature scheme that uses two hard problems, discrete logarithm and factorisation, as the basis of receiver's security. We show that the scheme has provable security against adaptively chosen message attack and is the most efficient scheme with respect to the ratio of the message length to the signature length. The scheme provides an efficient solution to signing messages up to 1881 bits.