1
$\begingroup$

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.

$\endgroup$
2
  • $\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

3
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.