International Association
for Cryptologic Research

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond $\ccai$. Towards this, we propose a new notion, called security against \textit{verified chosen-ciphertext attack} ($\nvcca$). The idea behind it is to ascertain the integrity of the ciphertext by imposing a strong control on the evaluation algorithm. Essentially, we require that a ciphertext obtained by the use of homomorphic evaluation must be "linked" to the original input ciphertexts. We precisely formalize the $\nvcca$ notion in two equivalent formulations; the first is in the indistinguishability paradigm, the second follows the non-malleability simulation-based approach, and is a generalization of the targeted malleability introduced by Boneh et al in 2012. We strengthen the credibility of our definitions by exploring relations to existing security notions for homomorphic schemes, namely $\ccai$, $\rcca$, $\funccpa$, $\ccva$, and $\hcca$. We prove that $\nvcca$ security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, $\nvcca$ is strictly stronger than $\ccai$. Finally, we provide a generic transformation, that takes \textit{any} $\cpa$-secure FHE scheme and makes it $\nvcca$-secure. Our transformation first turns an FHE scheme into a $\ccaii$-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge to control the evaluation algorithm. In fact we obtain \emph{four} variations for the $\nvcca$-secure FHE construction, as we give two public-key variations and two symmetric-key ones. As a direct implication, we get the \emph{first} $\ccai$-secure FHE schemes that is based on \emph{bootstrapping} techniques.