Take the 2-minute tour ×
Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

I'm doing some self-teaching / research for my own benefit in homomorphic cryptography.

I've studied both additive and multiplicative schemes (Pallier and RSA respectively), but all I can seem to find are benefits for the schemes.

Are there any disadvantages to these schemes being used for homomorphic operations (minus their obvious limitations in not being fully homomorphic)? If so, where should I be looking, and which key-words have I not been searching for?

share|improve this question
1  
Do you want general disadvantages of homomorphic schemes (i.e. which are induced by the homomorphic properties), compared to something else (what?), or disadvantages of these schemes compared to an "ideal homomorphic encryption primitive"? –  Paŭlo Ebermann Jun 24 '13 at 11:28
add comment

3 Answers 3

The multiplicatively homomorphic variant of RSA is not semantically secure. This is a major disadvantage. ElGamal is a semantically secure, multiplicativey homomorphic cipher. Paillier is a semantically secure, additively homomorphic cipher.

As described by tylo, all homomorphic ciphers are malleable by definition. Chances are, however, if you are interested in homomorphic ciphers, however, malleability is probably not a concern.

Homomorphic ciphers typically do not, in and of themselves, do not provide verifiable computing. In words, you encrypt your data, send it to the cloud and let the cloud compute on it for you. How do you know the cloud performed the correct computation? To get this sort of guarantee, other machinery is needed.

Performance is often a disadvantage. Ciphertexts in the ciphers you mention are much larger than the plaintexts, so communication requirements typically go up. The computations on these large ciphertexts are typically slower than if you just performed the computation on the plaintext itself. Because of this, in the outsourcing computation model, we typically see a requirement that encrypting inputs and decrypting outputs should be faster than performing the computation itself. In the case of multiple parties with individual inputs this seems to be less of a concern as privacy, not efficiency is the concern.

In the case of multiple, participating parties, guaranteeing fairness (which means everyone who is suppose to get an output, gets it) is often difficult and requires extra machinery (e.g., threshold decryption) and more assumptions (threshold of honest parties, etc). Another concern in the multiple, participating parties model is how the parties privately input their values for the computation. If one party knows the private key, they can decrypt the inputs and violate another party's privacy. So in this case, threshold decryption is often used. This in itself is a disadvantage as generating threshold keys is a non-trivial task.

share|improve this answer
add comment

The homomorphic property also implies malleability. This means, if you have some ciphertext, then you can create a different ciphertext with a related plaintext, and this property can be unwanted in this scheme (e.g. in an auction where you just encrypt your actual bid; then the attacker could just use your bid $+1$ or exchange your name with his, etc.) Malleability doesn't specify what kind of relation is implied by changing the ciphertext, while the homomorphic property usually refers to an algebraic operation.

One of the negative effects is that it is a contradiction of the CCA2 security definition.

Additionally, homomorphic properties are unwanted in signature schemes, where you want to provide provable unforgeability (if possible with the security definition of EUF-CMA).

share|improve this answer
    
I would prefer different wording in the first sentance. Being homomorphic isn't something I've heard as being called malleable, rather if something is homomorphic then it's malleable. The general point is a good one, and would get my upvote if clarified. Possible wording to illustrate what I mean: "If a scheme has the homomorphic property, then by definition it must also have the [malleability](blah) property. Unlike being homomorphic, which may be desirable, being malleable is generally a weakness" –  figlesquidge Apr 9 at 16:29
    
Well, the definition of the properties are (almost) equivalent. Just one term is used when you actually want this property and the other when you don't. The actual difference is, that malleability only requires some sort of relation, while leaving the actual relation unspecified –  tylo Apr 10 at 12:04
add comment

Being malleable they are prone to alteration of data in case your trusted party doing the computation is malicious. For example in Paillier Cryptosystem, you use the encryption scheme so that the other party should not know the actual value which you passed to do the computation. But in case the second party doing computations is corrupt or even if not corrupt but doing computations in a wrong way, there is no way you will come to know of this thing and you will get some value after decrypting the final ciphertext. And this will not let you know if it has been derived in the way you wanted it to be.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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