A signcryption scheme allows a sender to produce a ciphertext for a receiver so that both confidentiality and non-repudiation can be ensured. It is built to be more efficient and secure, for example, supporting insider security, when compared with the conventional sign-then-encrypt approach. In this paper, we propose a new notion called heterogeneous signcryption in which the sender has an identity-based secret key while the receiver is holding a certificate-based public key pair. Heterogeneous signcryption is suitable for practical scenarios where an identity-based user, who does not have a personal certificate or a public key, wants to communicate securely with a server which has a certificate with its public key. We propose two constructions and show their security under the model we define in the random oracle model. The model we define captures the insider security for both confidentiality and unforgeability. Both of the schemes also support public verifiability and key privacy, that is, an adversary cannot find out who the sender and receiver are from a ciphertext in the insider security model. The second scheme is the most efficient one computationally among all key-privacy-preserving signcryption schemes even when compared with schemes in an identity-based cryptographic setting or certificate-based public key setting.