7
$\begingroup$

I am trying to better understand homomorphic encryption, but I feel like I keep getting inconsistent information in the papers that I am reading.

One of the papers I am reading says the following:

Earlier, homomoprhic encryption was defined as a form of encryption where a specific algebraic operation performed on plaintext is equivalent to another algebraic operation performed on its ciphertext

Meanwhile, another paper says the following:

For now, a homomorphic cryptosystem can be thought of as an oracle, or black box, that, when given two ciphertexts and an operation, returns an encryption of the result of that operation on the two corresponding plaintexts.

The wording of the first one makes it seem as though the operation does not have to be the same (it says "another"), but the wording of the second one makes it seem as though the operation IS the same.

Can somebody clear up which one is correct?

$\endgroup$
  • 1
    $\begingroup$ You surely know that $e^{x+y} = e^x\cdot e^y$. If you take $x\mapsto e^x$ as "encryption", then the first citation says that addition on the "plaintexts" $x$ and $y$ corresponds to the multiplication of the "ciphertexts" $e^x$ and $e^y$. The second citation says that multiplication is an oracle that returns given $e^x$ and $e^y$ the encryption of the result of the operation addition applied to the two plain texts, which is just the equation you hopefully know. $\endgroup$ – j.p. Apr 14 '16 at 19:14
6
$\begingroup$

The operation does not have to be the same. For example, with Paillier, we multiply ciphertexts to get the addition of the plaintexts.

That said, I think what the 2nd quotation is saying is that the operation that is passed to the oracle is the desired operation in the plaintext domain. The oracle knows how to translate that operation into something that, when performed on the ciphertexts, results in the desired operation in the plaintext domain.

$\endgroup$
6
$\begingroup$

In short, the operations may be different, but they do not must be.

For instance, in the scheme presented on the pages 6 and 7 of this paper the homomorphic addition is simply a addition, but the homomorphic multiplication is a complex operation involving auxiliary functions and operations...

About your question:

Can somebody clear up which one is correct?

I think neither the first nor the second quote is really OK...

In the first, it seems that the operation has to be different and in the second, the issue about the operations was ignored.

Moreover, you should know that those quotes are very informal and high level. For example, the second one says that "given two ciphertexts and an operation" it is possible operate homomorphically, but the scheme in the paper I have linked uses an evaluation key (denoted by evk) to do some operations, then, just the ciphertexts and the definition of the operation are not enough to use such a black-box...

$\endgroup$

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.