Security of ordinary digital signature schemes relies on a computational assumption. Fail-Stop Signature (FSS) 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, first we propose a new FSS scheme whose security is based on discrete logarithm modulo a composite number, and integer factorization. We provide a security proof of the scheme, and show that it is as efficient as the most efficient previously known FSS scheme. Next, we construct a Threshold FSS that requires collaboration of t out of n participants to generate a signature and to prove forgery if it occurs. The scheme is equipped with cheater detection (incorrect partial signature) which is essential for an effiective proof of forgery in Threshold FSS and only requires trusted authority during pre-key generation.