4
$\begingroup$

I am trying to use division in PySyft or tenSeal or anything but the devs still haven't learned how to support division?!?!

$\endgroup$

2 Answers 2

4
$\begingroup$

Fully homomorphic encryption is (mostly) able to perform operations that may be encoded as polynomials. One can attempt to encode (integer) division in this form by exploiting the identity

$$ \frac{1}{x} = \frac{1}{1-(1-x)} = 1 - (1-x) - (1-x)^2-\dots, $$ truncated at an appropriate degree to achieve (some) desired level of precision, at least when $|x| < 1$ is known to be bounded. This can be done (for example) using the CKKS scheme. But, it is a not great solution --- it requires

  • being able to bound $|x| < B$ at some point in the computation (one can then multply by an approximation to the scalar $\lfloor 1/B\rfloor$ to shift $|x|\lfloor 1/B\rfloor < |x/B| < 1$), and
  • being able to tolerate the approximation error, which is rather high, even for moderate degrees $k$ of truncation. In particular, it should be on the order of $(1-x)^{k+1}$, e.g. for $x\approx 1$ the approximation will be quite bad. For $|x| < 1/2$, things may be fine though.

Note that there are other tricks of this type. They (vaguely) involve homomorphically computing various division algorithms. I don't know of any trick that is that much better than the others, but you could try the various options listed.

As mentioned in the other answer, you can get much better performance if you can use various "tricks". One that was already mentioned is encrypting some approximation to $1/x$, and then multiplying by this approximation. The following has not been mentioned yet, but may still be useful.

If you can rewrite your homomorphic computation as

  1. computing one polynomial $p(x)$ homomorphically, then
  2. computing another (separate) polynomial $q(x)$ homomorphically, then
  3. computing the quotient $p(x) / q(x)$ at the end.

Then one can simply homomorphically compute $p(x), q(x)$ (separately), return encryptions of these to the client, who decrypts and takes the quotient themself. If you cannot defer the quotient to the end, the above can still be used to give an interactive protocol to compute division, e.g. you can do

  1. standard FHE stuff, then
  2. send the client ciphertexts, that they must decrypt, take the quotient of, then reencrypt and send back to the server, then
  3. do more standard FHE stuff.

This is of course not great, but none of the options are great honestly, so it is useful to know the various choices.

$\endgroup$
1
  • $\begingroup$ To be honest, instead of dealing with the noise, sending the partial result to client, much better choice, however, in some protocols where the client doesn't own the data, but is allowed to extract information like average, max, min, etc, will increase the protocol complexity. $\endgroup$
    – kelalaka
    Commented May 17 at 9:13
3
$\begingroup$

It is not really about the devs, but more about the complexity of division for known fully homomorphic encryption schemes.

Without going into much details, while addition and multiplication are pretty straight forward (without accounting for noise growth), the underlying structure of FHE ciphertext does not offer a simple way to divide. There are several attempts to implement homomorphic division (see this article for example), but it is still not that developed to my knowledge.

Also for basic things like calculating means/standard deviation, (plaintext) multiplication often suffices by encoding and encrypting the inverse.

So to sum it up, it is normal that PySyft or tenSeal do not support homomorphic division, because multiplication should be enough for most applications. If division is absolutely required in your case you should look at the cited paper and the implementation they have done in HElib.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.