2
$\begingroup$

In homomorphic encryption scheme FV, I can multiply an encrypted polynomial for any integer scalar, obtaining the same effect on the plain polynomial. For example, given the plain polynomial $\sum_ia_ix^i$, and its encrypted version $\sum_ib_ix^i$, I could multiply the latter by $c$ and decipher it, to obtain $\sum_i(ca_i)x^i$. Is there a way to do the same with squaring? Can I perform some operation on $\sum_ib_ix^i$ and then decipher it, to get $\sum_ia_i^2x^i$? I already tried with $\sum_ib_i^2x^i$, but it just dosen't work.

About the reasons I'm doing this, it's because I have to use a polynomial activation function in a neural network that uses homomorphic encryption, as explained in this paper

$\endgroup$
  • $\begingroup$ could you please put a link to some description of the homomorphic encryption scheme you're using? there are many of them, and depending on the one you're using, the multiplication operation might be different. $\endgroup$ – Florian Bourse Mar 19 '18 at 14:49
  • $\begingroup$ Ehy, thanks for the reply! The software library I am using is SEAL from Microsoft, and as far as I know it is an implementation of the Fan-Vercauteren (FV) scheme. $\endgroup$ – Armando Mar 19 '18 at 16:21
  • $\begingroup$ So, you have $c$ which encrypts a polynomial $f(x) = a_0 + a_1x + ... + a_nx^n$ and you want to operate homomorphically to generate some ciphertext that encrypt $a_0^2 + a_1^2x + ... + a_n^2x^n$, right? $\endgroup$ – Hilder Vitor Lima Pereira Mar 20 '18 at 9:35
  • $\begingroup$ Exactly!! I would like to understand if this is possible! If not, it means that I misinterpreted the data encoding. Unfortunately there are not many details about the relationship between the square activation layer and the management of polynomials in the paper. $\endgroup$ – Armando Mar 20 '18 at 12:04
1
$\begingroup$

In the Fan-Vercauteren scheme, ciphertexts are composed of 2 polynomials, call them $ct_0$ and $ct_1$.
Although homomorphic addition is really simple (add the two parts independently), the same cannot be said for multiplication. As you noticed, simply multiplying the polynomials won't give you the desired result.
The homomorphic multiplication is composed of 2 steps. First, you compute an intermediary ciphertext (it is not a real ciphertext because it's composed of 3 elements and not 2): $$\frac{t}{q}ct_0ct'_0, \;\; \frac{t}{q}(ct_0ct'_1+ct_1ct'_0), \;\; \frac{t}{q}ct_1ct'_1$$ all of them rounded and taken modulo q. This intermediate can be obtained with the SEAL library using Evaluator::multiply.
You can use only this operation and keep your ciphertext size growing, but at some point, it would be more efficient to relinearize.
This operation is used to go back to a ciphertext containing only 2 elements, and can be obtained with the SEAL library using Evaluator::relinearize (it needs a key as a second argument that can be generated using KeyGenerator::generate_evaluation_keys.

Now in order to square an element, you just have to multiply it by itself, but using the correct multiplication operation instead of the naive one.

For more details, you can have a look at this documentation.

| improve this answer | |
$\endgroup$
  • $\begingroup$ But if $c$ encrypts a polynomial $f(x) = a_0 + a_1x + ... + a_nx^n$, then $c^2$ doesn't decrypt to $a_0^2 + a_1^2x + ... + a_n^2x^n$. $\endgroup$ – Hilder Vitor Lima Pereira Mar 20 '18 at 9:33
  • $\begingroup$ I have already tried this way, but as Hilder also states, this does not elevate the polynomial coefficients squarely, but the polynomial itself. As an example, if we take $2x+3$, we encrypt it, multiply it by itself and decode it, the result is not $4x+9$, but instead $4x^2+6x+9$. $\endgroup$ – Armando Mar 20 '18 at 12:32

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.