The key substitution property is introduced by Blake-Wilson and Menezes and formalized 
by Menezes and Smart as attacks. The key substitution property is as follow: another 
person other than true signer can produce another public (and secret) key such that 
a message and signature pair created by the signer is valid under the public key. 
The research of the key substitution attacks is only to attack a certain signature 
scheme or only to detect the attacks so far. In this paper, we introduce key-substitutable 
signature scheme. In the key-substitutable signature scheme, it is basically infeasible to 
produce a substitute public key, however, an user can create a substituted key pair by 
interaction with the original signer. We propose the formal model of the key-substitutable 
signature scheme and formalize the security requirements, unforgeability and non-substitutability. 
We also propose a construction of key-substitutable signature scheme based on ElGamal signature 
scheme and  prove that the construction satisfies the all security requirements. Furthermore, 
we construct a new certified-signature scheme achieving higher security based on key-substitutable 
signature schemes. We also show that the ``traditional'' certified-signature scheme in does not 
satisfy this higher security.