9

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

Improve this question
6
  • Where, specifically, have you seen the term semi-homomorphic used? It's helpful to know what you've already learned about the topic.
    – apsillers
    Commented Mar 30, 2015 at 20:04
  • For example this article talks about semi-homomorphic: eprint.iacr.org/2010/514.pdf @apsillers
    – Willl
    Commented Mar 30, 2015 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
    Commented Mar 30, 2015 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
    Commented Mar 30, 2015 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
    Commented Mar 30, 2015 at 20:18

3 Answers 3

Reset to default
8

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
  • 2
    Could you please explain how to create a binary NAND gate using addition and mulitplication?
    – king_julien
    Commented Apr 23, 2017 at 12:44
4

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
0

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
1
  • 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.
    – Dig
    Commented Oct 21, 2015 at 9:57

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .