Consider two schemes both have computation complexity linear to the input size (i.e. number of inputs). One scheme is based on Paillier encryption and the other one is based on fully homomorphic encryption.

Question 1: In general, can we compare their performance (i.e. which one is faster)?

Question 2: In general, can we compare their ciphertext size( i.e. which one has smaller sized ciphertex)?

  • $\begingroup$ quick (and likely) guess: FHE is slower and gives larger ciphertexts. $\endgroup$
    – SEJPM
    Oct 5, 2015 at 19:27
  • $\begingroup$ @SEJPM Thank you. Is there any short justification for that? $\endgroup$
    – Aydin
    Oct 5, 2015 at 19:28
  • 1
    $\begingroup$ This is the wrong comparison. You should compare Paillier to standard lattice-based encryption which is already additively homomorphic. My guess is that the lattice based encryption will win (and I know that this is Shai Halevi's claim as well). $\endgroup$ Oct 5, 2015 at 19:32
  • $\begingroup$ @YehudaLindell Well, I am considering the scheme that is based on (multi-key) fully homomorphic encryption: dl.acm.org/citation.cfm?id=2214086 $\endgroup$
    – Aydin
    Oct 5, 2015 at 19:36
  • 1
    $\begingroup$ My guess is then like @SEJPM. I suggest that you look on ePrint for the most recent implementations of fully homomorphic encryption, and then you can compare. $\endgroup$ Oct 5, 2015 at 19:47


Your Answer

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