search

ibarrond / Pyfhel

PYthon For Homomorphic Encryption Libraries, perform encrypted computations such as sum, mult, scalar product or matrix multiplication in Python, with NumPy compatibility. Uses SEAL/PALISADE as backends, implemented using Cython.
https://pyfhel.readthedocs.io/
Apache License 2.0
487 stars 78 forks source link

Multiplication in encrypted domain fails after ~20-25 operations #88

Closed vurdeljica closed 3 years ago

vurdeljica commented 3 years ago

Description I am trying to do multiple multiplications on encrypted numbers. I have managed to perform 20-25 operations and than multiplication starts to output invalid results. I am not sure whether I have configured context parameters in the wrong way or it is the bug in the Pyfhel. It really looks like some overflow is going on in Pyfhel. Please see the code below which you could use to reproduce the issue.

Code To Reproduce Error

from Pyfhel import Pyfhel
import random

HE = Pyfhel()
HE.contextGen(p=65537, m=32768, base=2)
HE.keyGen()

add_total = 0
mul_total = 1
add_total_encrypted = HE.encryptInt(add_total)
mul_total_encrypted = HE.encryptInt(mul_total)

for i in range(30):
    num = random.randint(1, 2)
    num_encrypted = HE.encryptInt(num)

    add_total += num
    mul_total *= num

    add_total_encrypted += num_encrypted
    mul_total_encrypted *= num_encrypted

    isSumGood = True
    isProductGood = True

    if HE.decryptInt(add_total_encrypted) != add_total:
        print("Adding is wrong on", i, "step. add_total_decrypted", HE.decryptInt(add_total_encrypted), ", add_total",
              add_total)
        isSumGood = False

    if HE.decryptInt(mul_total_encrypted) != mul_total:
        print("Mul is wrong on", i, "step. mul_total_decrypted", HE.decryptInt(mul_total_encrypted), ", mul_total",
              mul_total)
        isProductGood = False

    if isSumGood and isProductGood:
        print("Everything is ok in step:", i)

And output is:

Everything is ok in step: 0
Everything is ok in step: 1
Everything is ok in step: 2
Everything is ok in step: 3
Everything is ok in step: 4
Everything is ok in step: 5
Everything is ok in step: 6
Everything is ok in step: 7
Everything is ok in step: 8
Everything is ok in step: 9
Everything is ok in step: 10
Everything is ok in step: 11
Everything is ok in step: 12
Everything is ok in step: 13
Everything is ok in step: 14
Everything is ok in step: 15
Everything is ok in step: 16
Everything is ok in step: 17
Everything is ok in step: 18
Everything is ok in step: 19
Everything is ok in step: 20
Everything is ok in step: 21
Everything is ok in step: 22
Mul is wrong on 23 step. mul_total_decrypted -8570050456246514752 , mul_total 4096
Mul is wrong on 24 step. mul_total_decrypted -6361059045031529825 , mul_total 4096
Mul is wrong on 25 step. mul_total_decrypted 1787448009269290778 , mul_total 4096
Mul is wrong on 26 step. mul_total_decrypted 8207440967009556728 , mul_total 8192
Mul is wrong on 27 step. mul_total_decrypted 2076747607347692154 , mul_total 8192
Mul is wrong on 28 step. mul_total_decrypted 5863639603841695066 , mul_total 8192
Mul is wrong on 29 step. mul_total_decrypted 1005574422191187536 , mul_total 8192

Expected behavior Expected behavior is to perform all multiplications correctly or to have some warning/error that operation can't be executed correctly in the encrypted domain due to limitations in homomorphic encryption.

Setup:

ibarrond commented 3 years ago

Hi @vurdeljica , I'm afraid you might be trying to perform too many multiplications without decrypting. Unfortunately, other than playing with the context parameters, your best chance is to send some intermediate results back to the owner, decrypt them, encrypt them again, and continue the computation. Note that this limitation is inherent to Homomorphic Encryption schemes like the ones implemented in SEAL (our preferred backend).

Additionally, if you want to know the multiplication depth of a given Pyfhel instance, you can use the following function (introduced in 3ce85c1):

https://github.com/ibarrond/Pyfhel/blob/3ce85c14f3644a8eac961092335befad3a8169a4/Pyfhel/Pyfhel.pyx#L1344

You can see an example of its usage in the Demo_MultDepth_n_relin.py example. Try running it!:

https://github.com/ibarrond/Pyfhel/blob/3ce85c14f3644a8eac961092335befad3a8169a4/examples/Demo_MultDepth_n_relin.py#L76-L77

ibarrond commented 3 years ago

Unfortunately, you can only do so many multiplications before the noise inside grows too much for the ciphertext to be decipherable at all. There is no "safe" way to detect if an operation can be executed or not without the decryption key (otherwise this information could be use to attack the entire protocol). If you have the decryption key, it suffices to check the noiseLevel of the PyCtxt: if it reached 0, then it cannot be decrypted correctly anymore.

vurdeljica commented 3 years ago

I confirm that noise impacts the result. I have also tried to use lattigo library for go. I have used BFV scheme and I managed to multiply 10000 (I stopped here, maybe more multiplications can be done) encrypted numbers without the issue. Also the computation was super fast. Do you have any idea why is lattigo heavily outperforming SEAL? Does Pyfhel have the option to choose which scheme (BFV or CKKS) we want to use? I see that SEAL supports both schemes.

ibarrond commented 3 years ago

We never got enough time to implement the latest version of SEAL (the one implementing CKKS). If you're truly interested, you could tackle this implementation with guidance.