Most existing fully homomorphic encryption (FHE) security models cannot resist attacks from a malicious server that can arbitrarily replace the ciphertexts and evaluation functions used during homomorphic evaluation and obtain the decryption results of the evaluated ciphertexts. To address this security issue of FHE caused by the breakdown of computational integrity, we proposed two new primitives, called tagged-FHE and \(\hbox {tagged}^*\) -FHE with corresponding security notions IND-TAG-CCA and IND- \(\hbox {TAG}^*\) -CCA. Unlike the verifiable FHE, which also focuses on preserving computational integrity, the new primitives and security concepts still require the compactness of ciphertexts. The size of the output of the evaluation algorithm must be independent of the complexity of the function during evaluation. Tagged-FHE enables users to detect whether a server has replaced the input ciphertexts of evaluation. While \(\hbox {tagged}^*\) -FHE additionally enables users to detect whether a server has replaced the evaluation function. We present generic constructions for these two primitives with corresponding security notions. The IND-TAG-CCA tagged-FHE is achievable in the standard model using IND-CPA multi-key FHE and IND-CCA2 public-key encryption. The IND- \(\hbox {TAG}^*\) -CCA \(\hbox {tagged}^*\) -FHE additionally uses NIZK and SNARG and requires a heuristic assumption related to hash function collision resistance. These notions provide enhanced protection for FHE in the presence of malicious third-party servers.
