Overflow when iterate and divide Encrypted number

[agrojas]

Hi, I try to run this example using phe and numpy, but have Overflow when iterate some loops Can you help me? Thanks!

import phe as paillier
import numpy as np

init_values = [['7.44012909e-02', '-4.46416365e-02', '1.14508998e-01', '2.87580964e-02',
                '2.45741445e-02', '2.49905934e-02', '1.91869970e-02', '-2.59226200e-03',
                '-6.09254186e-04', '-5.21980442e-03', '1.00000000e+00'],
               ['1.62806757e-02', '5.06801187e-02', '-4.60850009e-02', '1.15437429e-02',
                '-3.32158756e-02', '-1.60318551e-02', '-1.02661054e-02', '-2.59226200e-03',
                '-4.39854026e-02', '-4.24987666e-02', '1.00000000e+00'],
               ['1.62806757e-02', '-4.46416365e-02', '2.07393477e-02', '2.18723550e-02',
                '-1.39525355e-02', '-1.32135190e-02', '-6.58446761e-03', '-2.59226200e-03',
                '1.33159679e-02', '4.03433716e-02', '1.00000000e+00'],
               ['5.98711371e-02', '5.06801187e-02', '1.64280994e-02', '2.87580964e-02',
                '-4.14715927e-02', '-2.91840905e-02', '-2.86742944e-02', '-2.59226200e-03',
                '-2.39668149e-03', '-2.17882321e-02', '1.00000000e+00'],
               ['4.53409833e-02', '5.06801187e-02', '6.06183944e-02', '3.10533436e-02',
                '2.87020031e-02', '-4.73467013e-02', '-5.44457591e-02', '7.12099798e-02',
                '1.33598980e-01', '1.35611831e-01', '1.00000000e+00']]


def divide_values_by_scalar(values, scalar):
    return np.array(values) / scalar


def encrypt_vector(public_key, x):
    return [public_key.encrypt(i) for i in x]


def decrypt_vector(private_key, x):
    return [private_key.decrypt(i) for i in x]


if __name__ == "__main__":
    float_values = [float(v) for v_array in init_values for v in v_array]
    pubkey, privkey = paillier.generate_paillier_keypair()
    to_np_values = np.array(float_values)
    encrypted_values = encrypt_vector(pubkey, to_np_values)
    divided_values = encrypted_values
    for i in range(1, 100):
        divided_values = divide_values_by_scalar(divided_values, 1)
    print(decrypt_vector(privkey, divided_values))

Traceback (most recent call last):
  File "/home/agustinrojas/Repositories/agrojas/fiuba/federated-learning-poc/commons/test.py", line 41, in <module>
    print(decrypt_vector(privkey, divided_values))
  File "/home/agustinrojas/Repositories/agrojas/fiuba/federated-learning-poc/commons/test.py", line 30, in decrypt_vector
    return [private_key.decrypt(i) for i in x]
  File "/home/agustinrojas/Repositories/agrojas/fiuba/federated-learning-poc/commons/test.py", line 30, in <listcomp>
    return [private_key.decrypt(i) for i in x]
  File "/home/agustinrojas/Repositories/agrojas/fiuba/federated-learning-poc/server/venv/lib/python3.6/site-packages/phe/paillier.py", line 287, in decrypt
    return encoded.decode()
  File "/home/agustinrojas/Repositories/agrojas/fiuba/federated-learning-poc/server/venv/lib/python3.6/site-packages/phe/encoding.py", line 221, in decode
    raise OverflowError('Overflow detected in decrypted number')
OverflowError: Overflow detected in decrypted number

[wilko77]

Overflows are a consequence of the encoding scheme.

The Paillier cryptosystem allows arithmetic over the integers modulo n. That is the numbers {0, 1, ..., n-1}. And thus, n-1 + 2 = 1 mod n or, the numbers "wrap around".

Our encoding scheme maps floating point numbers onto the integers in such a way that it preserves arithmetic. We do this by encrypting the mantissa as an integer and keeping the exponent in the clear.

However, there is a big difference to conventional floating point arithmetic. Whereas your computer will round to the nearest floating point number in arithmetic operations, making sure that the number is always representable with the available bits, our system is different. It will always compute the exact result. For example, if you multiply two doubles with a 53 bit mantissa each, then in our scheme the result will have a mantissa of 106 bits.

The important observation here is that with every arithmetic operation, the mantissa will only grow. And as the mantissa is mapped onto an integer in the Paillier scheme, it will eventually be too big to be represented (a wrap around will occur). That's what we call an overflow.

In your example, you repeatedly multiply, and after 55 iterations the mantissa grew so much that it could not be represented anymore within a Paillier ciphertext.

[agrojas]

Thanks @wilko77! I try using other simple example and have other Overflow error. Using

import phe as paillier
if __name__ == "__main__":
    public_key, private_key = paillier.generate_paillier_keypair()
    encryp_number = public_key.encrypt(1.0)
    for i in range(1, 100):
        print(encryp_number.exponent)
        encryp_number = encryp_number * 1.0
    print(private_key.decrypt(encryp_number))

The exponent increase until raise Overflow error.

-13
-26
-39
-52
-65
-78
-91
-104
-117
-130
-143
-156
...
-1196
-1209
-1222
-1235
-1248
-1261
-1274
-1287
Traceback (most recent call last):
  File "test.py", line 57, in <module>
    print(private_key.decrypt(encryp_number))
  File "/home/agu/Repositorios/fiuba/federated-learning-poc/client/venv/lib/python3.5/site-packages/phe/paillier.py", line 287, in decrypt
    return encoded.decode()
  File "/home/agu/Repositorios/fiuba/federated-learning-poc/client/venv/lib/python3.5/site-packages/phe/encoding.py", line 220, in decode
    return mantissa * pow(self.BASE, self.exponent)
OverflowError: int too large to convert to float

It's a expected behavoir? (iterating 100 times and only multiplying 1*1 each time)

[XieFuran]

I have the same problem, so how can we solve it?

[marcoCalipari]

Hello everyone.

I am running in the same issue. I was trying to use the phe module in one of my project but apparently while looping for 3 times I receive the same overflow error.

I did the calculations manually, and it should not overflow the system.

I can very well encrypt and work with ciphertexts, but when it comes to the decryption I either get an error, or some completely random values.

I tried to play with the precision parameter of the encrypt function, but yet no fortune. In some rare occasions the decryption was fine, but tremendously rare. Any solution or suggestions?

Thanks in advance