A deniable authentication can be used to provide secure negotiation on the Internet. Although many deniable authentication protocols have been proposed, most of them are vulnerable to various cryptanalytic attacks. Recently, a new deniable authentication protocol was proposed by Lee et al. However, Lee et al.’s protocol is not flawless yet due to its susceptibility to KCI attack. Then, based on ElGamal signature scheme, by signing a random number and a time stamp and exchanging the signature, an improved protocol is proposed. In the new protocol, the random is used to generate the session secret. The new protocol not only has the properties deniability and completeness but also has the enhanced security. The new scheme is secure against forgery attack, impersonation attack, compromised session secret attack and KCI attack.