FAIL-STOP SIGNATURES

Fail-stop signatures can briefly be characterized as digital signature s that allow the signer to prove that a given forged signature is inde ed a forgery. After such a proof has been published, the system can be stopped. This type of security is strictly stronger than that achieva ble with ordinary digital signatures as introduced by Diffie and Hellm an in 1976 and formally defined by Goldwasser, Micali, and Rivest in 1 988, which was widely regarded as the strongest possible definition. T his paper formally defines fail-stop signatures and shows their relati on to ordinary digital signatures. A general construction and actual s chemes derived from it follow. They are efficient enough to be used in practice. Next, we prove lower bounds on the efficiency of any fail-s top signature scheme. In particular, we show that the number of secret random bits needed by the signer, the only parameter where the comple xity of all our constructions deviates from ordinary digital signature s by more than a small constant factor, cannot be reduced significantl y.