What is the difference between fully homomorphic and semi-homomorphic encryption?

  • Where, specifically, have you seen the term semi-homomorphic used? It's helpful to know what you've already learned about the topic. – apsillers Mar 30 '15 at 20:04
  • For example this article talks about semi-homomorphic: eprint.iacr.org/2010/514.pdf @apsillers – Willl Mar 30 '15 at 20:07
  • "We define the relaxed notion of a semi-homomorphic encryption scheme, where the plaintext can be recovered as long as the computed function does not increase the size of the input "too much"." Which part, specifically, of this definition gives you problems? The system has a homomorphism the allows a function over ciphertext, but the function will give faulty results if the output of the homomorphic function would be substantially greater than the input. Your question is not very specific. Is this the category of answer you are looking for, or do you need a more exact definition? – apsillers Mar 30 '15 at 20:15
  • It would also be helpful to edit your question to clarify how much you already understand about homomorphic encryption. Currently, it's not clear how much background information a good answer should give. – apsillers Mar 30 '15 at 20:16
  • I have read that explanation. I have understood homomorphic encryption too. I just asked this question in order to get a formal definition of difference between them. Nothing like "too much" sth like that. I just need a formal definition about why it is called "semi".. – Willl Mar 30 '15 at 20:18

If you're happy with a more mathematical definition:

A Fully-Homomorphic Encryption preserves a ring-structure.

This means we have a Ring (R,+,*), where R are our bits on which we operate, (R,+) is an abelian group, while (R,*) is an monoid. With addition and mupltiplication over bits it's possible to create NAND gates. If you have NAND gates, you can derive every other boolean gate and therefore are able to do every computation on the encrypted data.

Semi-Homomorphic Encryption on the other hand only supports one operation and because of that you are not able to create NAND gates, which means you can't do every computation on the encrypted data.

| improve this answer | |
  • 1
    Could you please explain how to create a binary NAND gate using addition and mulitplication? – king_julien Apr 23 '17 at 12:44

Shortly, an 'homorphic encryption scheme' means that you are able to apply operations on the ciphered message and see the result of these operations once the message is deciphered.

Usually, these operations are related to arithmetic (which is known to be Turing-complete meaning that you can encode any program in it).

As arithmetic operators are 'addition' and 'multiplication' (subtraction and division are the dual of these operators). A fully homomorphic encryption scheme is able to perform addition and multiplication on the ciphered message (modern ones can also use xor and many other operations).

A 'semi-homomorphic encryption scheme' supports only one of the two operators. For example, the RSA encryption scheme is homomorphic for the multiplication (but clearly not for the addition).

| improve this answer | |

Usually when you talk about "semi-homomorphic encryption", it can mean two things :

  • You don't support all the operations of fully homomorphic encryption (for instance addition but not multiplication) because your use-case only require a subset of them and that will lower the (tremendous) overhead of homomorphic encryption.

  • Your system has an homomorphic behavior, but because of the taint/noise added to the data, the more you manipulate some data, the less they are secure (i.e. either you have to increase cipher size to compensate, or you will just have to discard data after a given number of operations because they are not deemed 'secure' enough anymore)

Without more context, it's hard to tell which one you are asking about.

| improve this answer | |
  • Secure? I think you mean that the data might not be decryptable anymore. Meaning data loss. The security of the data must remain. Moreover, this definition isn't called semi-homomorphic. It is called "Somewhat-homomorphic". The huge breakthrough in FHE was that Gentry showed that given an Somewhat-homomorphic encryption with certain condition (mainly that the decrypion procedure and additional nand gate can be evaluated homomorphically ), one can bootstrap it to a fully homomorphic encryption. – DiGMi Oct 21 '15 at 9:57

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.