Homomorphic Encryption (HE) has become a wellknown tool for privacy-preserving recognition in biometric systems. Despite some important advantages of HE (such as preservation of recognition accuracy), there are two main drawbacks in the application of HE to biometric recognition systems: first, the security of the system solely depends on the secrecy of the private (decryption) key; second, the computational costs of the operations on the ciphertexts are expensive. To address these challenges, in this paper we propose a hybrid scheme for the protection of biometric templates, which combines cancelable biometrics (CB) methods and HE. Applying CB prior to HE enhances both the security and privacy of the overall system, since the protected templates remain irreversible even if the secret keys are leaked (commonly referred to as the full disclosure scenario). In addition, we can reduce the dimensionality of templates using CB before applying HE, which speeds up the computation over the ciphertexts. We use BioHashing, Multi-Layer Perceptron (MLP) hashing, and Index-ofMaximum (IoM) hashing as different CB methods, and for each of these schemes, we propose a method for computing scores between hybrid-protected templates in the encrypted domain. We evaluate our proposed hybrid scheme using different state-of-the-art face recognition models (ArcFace, ElasticFace, and FaceNet) on the MOBIO and LFW datasets. The source code of our experiments is publicly available, so our work can be fully reproduced.