Fully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability

Fully Homomorphic Encryption Beyond IND-CCA1 Security: Integrity Through Verifiability

연구 분야: Cryptography

학회: Annual International Conference on the Theory and Applications of Cryptographic Techniques

We focus on the problem of constructing fully homomorphic encryption (FHE) schemes that achieve some meaningful notion of adaptive chosen-ciphertext security beyond \(\textrm{CCA1}\). Towards this, we propose a new notion, called security against verified chosen-ciphertext attack (\(\textrm{vCCA}\)). The idea behind it is to ascertain 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 formalize the \(\textrm{vCCA}\) 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 encryption schemes, namely \(\textrm{CCA1}\), \(\textrm{RCCA}\), \(\textrm{FuncCPA}\), \(\textrm{CCVA}\), and \(\textrm{HCCA}\). We prove that \(\textrm{vCCA}\) security is the strongest notion known so far, that can be achieved by an FHE scheme; in particular, \(\textrm{vCCA}\) is strictly stronger than \(\textrm{CCA1}\). Finally, we provide a general transformation, that takes any \(\textrm{CPA}\)-secure FHE scheme and makes it \(\textrm{vCCA}\)-secure. Our transformation first turns an FHE scheme into a \(\textrm{CCA2}\)-secure scheme where a part of the ciphertext retains the homomorphic properties and then extends it with a succinct non-interactive argument of knowledge (SNARK) to verifiably control the evaluation algorithm. In fact, we obtain four general variations of this transformation. We handle both the asymmetric and the symmetric key FHE schemes, and for each we give two variations differing in whether the ciphertext integrity can be verified publicly or requires the secret key. We use well-known techniques to achieve \(\textrm{CCA2}\) security in the first step of our transformation. In the asymmetric case, we use the double encryption paradigm, and in the symmetric case, we use Encrypt-then-MAC techniques. Furthermore, our transformation also gives the first \(\textrm{CCA1}\)-secure FHE scheme based on bootstrapping techniques.