I recentely asked "IND-CCA1 RSA padding?" about whether there is a IND-CCA1 secure variant of RSA. The original version of the question also allowed usage of ECC which would allow usage of ElGamal, providing IND-CPA and somewhat IND-CCA1.

Now I have the same setting as in the above question, meaning I need a cryptosystem with some homomorphic property and maximal security notion (IND-CCA1 would be optimal, but IND-CPA would also be OK). But this time I'm asking for a post-quantum scheme having a homomorphic property and being IND-CCA1 secure.

So finally the question:
Is there any post-quantum public key encryption algorithm providing IND-CCA1/CPA security and a partial homomorphic property?

Please exclude fully homomorphic encryption schemes from the answers. I know most of them are PQ safe, but they're too slow. And of course please also exclude schemes being even slower than FHE schemes.


Essentially any IND-CPA-secure lattice-based cryptosystem offers additive homomorphism, up to a predetermined number of operations.

I don't know of any IND-CCA1-secure post-quantum candidate that offers any homomorphic property, except Loftus-May-Smart-Vercauteren SAC'11, which is based on a nonstandard "knowledge of error" lattice assumption.

  • $\begingroup$ At first I thought that your CCA1-secure scheme from EUROCRYPT 2012 may be additively homomorphic, but then I realized that the tag matrices $\mathbf H$ are random for each ciphertext, so it doens't work straightaway. Is it possible to fix these matrices without impacting security? Also, I don't know if the encoding of the messages is homomorphic too. $\endgroup$ – cygnusv Aug 24 '15 at 8:50
  • $\begingroup$ Now that I see it, you mention in your paper the possibility of setting $\mathbf H = \mathbf I$. In that case, and given that it seems that the encoding is additively homomorphic too, then this scheme could be an example of CCA1-secure lattice-based PKE that is additively homomorphic. $\endgroup$ – cygnusv Aug 24 '15 at 9:22
  • $\begingroup$ Unfortunately no, the CCA1 proof breaks down entirely if you fix the tag matrices to be the same for all ciphertexts. The simulator needs to produce a challenge ciphertext at the tag on which the public key is "punctured," and needs decryption queries need to have different tags so the simulator can decrypt them. Also, I suspect that the scheme is actually insecure under CCA1 for the usual reasons, but haven't verified carefully. $\endgroup$ – Chris Peikert Aug 24 '15 at 12:54

There should be plenty of them. Off the top of my head, I'm thinking of the provable secure version of NTRU by Stehlé and Steinfeld [1], which is IND-CPA secure. In this scheme, ciphertexts are of the form:

\begin{equation} c = pk \cdot s + p\cdot e + \operatorname{encode}(m) \end{equation}

where $s$ and $e$ are random polynomials, $p$ is a small prime, and $pk$ is the public key. It can be shown that this scheme is additively homomorphic: \begin{equation} c + c' = pk \cdot (s+s') + p\cdot (e+e') + \operatorname{encode}(m + m') \end{equation}

In fact, this cryptosystem has been used as the basis of some fully homomorphic encryption schemes, such as [2].

In the response to this question I precisely tackle with the correctness condition for the addition of ciphertexts in this cryptosystem.


[1] Stehlé, D., & Steinfeld, R. (2011). Making NTRU as secure as worst-case problems over ideal lattices. In Advances in Cryptology–EUROCRYPT 2011 (pp. 27-47). Springer Berlin Heidelberg.

[2] López-Alt, A., Tromer, E., & Vaikuntanathan, V. (2012, May). On-the-fly multiparty computation on the cloud via multikey fully homomorphic encryption. In Proceedings of the forty-fourth annual ACM symposium on Theory of computing (pp. 1219-1234). ACM.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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