Can pailler cryptosystem encrypt and decrypt negative big integers?

Question

I use paillier cryptosystem to encrypt and decrypt random data which at first are in the form of byte arrays and then i transform them to big integers and if the byte array become a negative big integer the decrypted number and the input number are different (basically it doesn't work with negative big integers). Is there a way to make this work without checking the input if it will become positive or negative ?

Answer 1

No, you cannot use negative numbers as everything is computed modulo n.

Yes, you can use any array, as long as the value, when converted to a number, is a number smaller than n.

For this you can use new BigInteger(1, plaintext) which will always result in a positive number. The first parameter is the sign.

You may need an encoding for specific structures, e.g. with zero bit values for the most significant bits (message-> encode-> convert to number -> Paillier encryption -> encode ciphertext and decode ciphertext -> Paillier decryption -> decode -> message).

See I2OSP and OS2IP for an example on how to encode / decode data to numbers.

Answer 2

Paillier cryptosystem is defined over modulo n for plaintexts and n^2 for ciphertexts. So, if you even encrypt a negative number, it is going to have a positive equivalent for modulo n. This can be proven in python as:

# pip install lightphe
from lightphe import LightPHE
 
# build a cryptosystem
cs = LightPHE(algorithm_name = 'Paillier')
modulo = cs.cs.plaintext_modulo
 
# define plaintexts
m1 = -10
 
# calculate ciphertexts
c1 = cs.encrypt(m1)
 
# performing homomorphic addition on ciphertexts
assert cs.decrypt(c1) == m1 % modulo