For example say we have two numbers a and b. Now is there any partial homomorphic encryption scheme that allows to compute (a-b)^2 over the ciphertexts of a and b without round trips.

  • $\begingroup$ Possible duplicate of Homomorphic Encryption with Addition and Exponentiation. $\endgroup$ – mikeazo Feb 17 '16 at 13:00
  • $\begingroup$ Your question's title talks about additive homomorphic encryption while the question's body talks about partial homomorphic encryption. Could you please define better that? $\endgroup$ – Hilder Vítor Lima Pereira Feb 17 '16 at 16:51
  • $\begingroup$ I'm agreeing with mikeazo on this one. If you could compute $(a-b)^2$, you could also compute $ab=-(a-0)^2-(b-0)^2-(a-b)^2$ which would allow fully homomorphic encryption (assuming exponentiating with $1$ is allowed). The answer to the referenced question is lacking though, therefore I do not vote for closing as dupe. $\endgroup$ – SEJPM Feb 17 '16 at 20:55

What you want is a cryptosystem that supports linear operations, and some bounded number of multiplications (supporting exponentiations by bounded values is equivalent to supporting multiplication, as to compute a*b homomorphically, you can always compute (a-b)²-a²-b² homomorphically and divide this by two). Without requiring a bound on the number of multiplications, this is just fully homomorphic encryption.

With a bound, it is known as somewhat hommorphic encryption (SHE). Most constructions for SHE are based on lattice assumptions (such as LWE). A noticeable exception is the Boneh-Goh-Nissim (BGN) cryptosystem which uses pairing based cryptography; the scheme is homomorphic for linear operations and one multiplication (e.g. one squaring as in your example), in any order (e.g. the function f:(a,b) -> a² + b² can be computed homomorphically with the BGN scheme). However, as decryption requires a discrete logarithm, the plaintexts must be small for the decryption algorithm to be efficient.

However, for your particular example, there is even a simpler way: there is a generic conversion from any linearly homomorphic encryption scheme (with some reasonable properties) to an homomorphic scheme that supports linear operations, then one multiplication, then a bounded number of linear operations (once the multiplication was performed, the ciphertext grows linearly with the number of additional linear operations you perform). The article is "Boosting Linearly-Homomorphic Encryption to Evaluate Degree-2 Functions on Encrypted Data". f:(a,b) -> (a-b)² is typically the kind of operations supported by this conversion. Such a cryptosystem can be constructed from the (additive variant of the) ElGamal cryptosystem, or the Paillier cryptosystem, for example. From the Paillier cryptosystem, you get such a degree-two homomorphic cryptosystem, with no restriction on the plaintext size as in ElGamal or BGN.


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.