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, 2016 at 13:00
  • $\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, 2016 at 20:55

1 Answer 1


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 homomorphic 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 and acknowledge you have read our privacy policy.