Enforcing strong authentication is an option to mitigate phishing. However, existing authentication methods, like traditional digital signatures, require unrealistic full deployment of public key infrastructure(PKI) and destroy email users ’ privacy in that the identity of an email sender is automatically revealed to the public. There have been some works in the literature, where the technology of deniable authentication is adopted and sender’s privacy can be protected. However, the additional computation introduced into the system is obviously a drawback. In this paper, we introduce the notion of online/offline authentication into anti-phishing, in order to construct an efficient and secure anti-phishing scheme. It is commonly known that a generic online/offline signature can be constructed with a traditional chameleon function. Nevertheless, a standard chameleon function suffers from so-called key-exposure attacks. To tackle this issue, we propose an efficient chameleon function without key-exposure, which is especially suitable for constructing efficient online/offline signatures that are applicable to mitigating phishing. We also demonstrate how to apply our novel scheme to a traditional email system.