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 '15 at 19:27
  • $\begingroup$ @SEJPM Thank you. Is there any short justification for that? $\endgroup$ – Ay. Oct 5 '15 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$ – Yehuda Lindell Oct 5 '15 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$ – Ay. Oct 5 '15 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$ – Yehuda Lindell Oct 5 '15 at 19:47

Your Answer

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

Browse other questions tagged or ask your own question.