• Is there a way of maintaining malleability in a homomorphic encryption system while making it infeasible to perform chosen ciphertext attacks?

I have been reading about homomorphic encryption and malleable cryptosystems lately and have found it fascinating. I still have a lot of reading to do, however, I came across a statement in my reading that suggested malleability is inherently counter to security against chosen ciphertext attacks.

While I read up more about this relationship, I am curious to learn if there a way to maintain malleability while making a chosen ciphertext attack computationally infeasible? Why or why not?


1 Answer 1


I know of two lines of work on this question. It is indeed possible to allow malleability but still make some guarantees in the presence of a chosen-ciphertext attack:

Both papers present encryption schemes (and security definitions) that allow malleability $\textsf{Enc}(m) \leadsto \textsf{Enc}(T(m))$ for some set of allowed transformations $T$ (as a feature), but where any other kind of malleability is infeasible.

As a concrete example, suppose the only allowable transformation is the identity transformation. Then it is possible to transform $\textsf{Enc}(m)$ into another "fresh" encryption of the same (unknown) $m$. But it is infeasible to transform $\textsf{Enc}(m)$ into any $m' \ne m$ that is related to $m$. This special case is called "rerandomizable RCCA" encryption.

The first paper is my work, a combination of 3 of our conference papers; the one most relevant to your question is this one. Our construction has additional security requirement: a "transformed" ciphertext obtained via $\textsf{Enc}(m) \leadsto \textsf{Enc}(T(m))$ should be indistinguishable from a "fresh" ciphertext (even to the private-key holder). We only consider the case of unary transformations, since n-ary transformations (i.e., combining several ciphertexts in a transformation) are impossible under these definitions.

The second paper does not have this extra requirement --- so "transformed" ciphertexts look different than "fresh" ciphertexts. They use an approach of appending a ZK proof that an allowable transformation was used on some original ciphertext.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.