3
$\begingroup$

I found some questions and answers about the performance of Fully and Partially homomorphic encryption. I am interested in a comparison in terms of security guarantees (of any kind, formal or informal). I understand that there are various schemes for both and so a comparison between specific schemes is equally useful to me.

Is, for instance, Paillier/Elgamal more/less secure than FHE (both allow additions and multiplications)?

Is DET/OPE/ORE more/less(probably) secure than FHE (both allow equality and order comparisons)?

Improve this question
$\endgroup$
6
  • $\begingroup$ Can you precisely define "security"? Otherwise, how are we to answer? $\endgroup$
    – mikeazo
    Commented Oct 23, 2017 at 12:38
  • 1
    $\begingroup$ Unfortunately, you're trying to compare apples and oranges here. Security is always defined with a security parameter, which means ElGamal with $\lambda = 12$ is more secure than ElGamal with $\lambda = 10$. To which do you want to compare the FHE construction by Gentry with a securtiy parameter of $\lambda = 15$ now? The values just examples, but they should show the problem. $\endgroup$
    – tylo
    Commented Oct 23, 2017 at 12:43
  • 1
    $\begingroup$ If you consider something like "with equal runtime", then almost surely FHE is going to be less secure - usually it's stated the other way around: FHE is really slow compared to semi-homomorphic schemes with similar security parameter. But still, a comparison for that can only benchmark some implementation of the scheme, not the scheme itself. $\endgroup$
    – tylo
    Commented Oct 23, 2017 at 12:50
  • $\begingroup$ I see thanks, I am not very familiar with FHE. Still, for PHE you could say, informally, that Paillier is more secure than DET (security parameters aside) since the latter reveals equality of values or OPE that reveals order. Perhaps amongst probabilistic schemes, such comparison is not meaningful? $\endgroup$
    – savx2
    Commented Oct 23, 2017 at 12:51
  • 1
    $\begingroup$ Apples and oranges. They are different kind of schemes, different security definitions, they achieve different goals. Considerng such a comparison as "not meaningful" is only partially right - it makes no sense, honestly. $\endgroup$
    – tylo
    Commented Oct 23, 2017 at 12:52

1 Answer 1

Reset to default
3
$\begingroup$

In short: They can not be compared, because those cryptosystems are vastly different constructions for different goals.

Taking a step back, usually the security of a cryptosystem is defined with a security parameter $\lambda$, and the security then is described as "... is less than a negligible function $f(\lambda)$ ...", so we can say that e.g. ElGamal with $\lambda = 10$ is less secure than ElGamal with $\lambda = 12$.

But as soon as looking at different constructions, this gets tricky, because they don't compare to the same negligible function any more. Also, they are just upper bounds and there is no statement possible like "it has exactly security $23$".

If you want to combine security with other aspects like runtime, then you run into other issues. Some cryptosystems have fast key generation, others have fast encryption or decryption, etc. There's just one rule of thumb: Quite surely any FHE construction is much, much slower than traditional PKE systems when aiming at similar levels of security. Also, if you consider runtime of a system and include this in your comparison, then you have to keep in mind you are comparing implementations and not the scheme itself.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thank you for your answer. In what basis is then one crypto scheme preferred over another? ECB vs CBC, ElGamal vs (default) RSA? Is it based on known attacks? Also if I was to categorize scheme A as CPA and B as not CPA, could I not say A is strictly better in terms of confidentiality? Isn't that a form of comparison even if the schemes can be vastly different? $\endgroup$
    – savx2
    Commented Oct 27, 2017 at 14:17
  • 1
    $\begingroup$ @SavvasSavvides It depends. Of course, it's better if a scheme is IND-CPA (or even IND-CCA) than if it isn't IND-CPA secure. However, anything below IND-CPA is considered insecure anyway (including textbook-RSA). The main basis for the decision for one scheme over another should be: What is your goal? What can the adversary do? How do you define security? Just like a hammer and pliers are used for different things, the same way you need to choose the appropriate cryptosystem. $\endgroup$
    – tylo
    Commented Oct 30, 2017 at 13:11

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.