How to Make Efficient Fail-stop Signatures

Fail-stop signatures (introduced in [WP89]) have the very nice property that the signer is secure against unlimited powerful forgers. However, the known fail-stop signatures require very long keys, and they are quite inefficient, because messages are signed bit-wise. This paper presents a fail-stop signature scheme, in which signing a message block requires two modular multiplications and verification requires less than two modular exponentiations. Furthermore a construction is shown of an undeniable signature scheme, which is unconditionally secure for the signer, and which allows the signer to convert undeniable signatures into fail-stop signatures. This is the first published undeniable signature having this property.