It seems that all existing on-line/offline (threshold) signature schemes based on ShamirTauman's paradigm suffer from the key exposure problemof chameleon hashing. In this paper, we firstly proposea new effcient generic on-line/off-line threshold signaturescheme without key exposure. Compared with Crutchfieldet al.'s scheme, the advantages of our scheme are the lowercomputation and storage cost in off-line phase and lowercommunication cost in on-line phase. Meanwhile, we proveour scheme can achieve the desired security notions.