document need for explicit rerandomisation

[mortendahl]

addition and multiplication does not implicitly rerandomise ciphertexts for performance reasons

this behaviour should be very clear from the documentation as it's a potential security concern

[polyfractal]

Would you mind expanding on this? From my limited playing around with the library, it appears the cyphertext changes differently on each operation. I.e. if I encrypt two values from the same key, perform the same operation on each and print out the cyphertext, they appear different.

Am I misunderstanding?

[mortendahl]

Paillier is what's called a probabilistic encryption scheme, meaning every ciphertext is a mix of both the plaintext and a randomness. Hence, two encryptions of the same plaintext will most likely give two different ciphertexts as the randomness will most likely be different. This is good since it provides a stronger level of security, known as semantic security.

This GitHub issue is related to the fact that the library does not currently refresh the randomness automatically after performing homomorphic operations on ciphertexts, but requires an explicit call to rerandomise to do so -- this is for performance reasons since rerandomisation is expensive and it's enough to do so once even if several homomorphic operations are performed. The reason for doing this in the first place is to make sure that a ciphertext produced through homomorphic operations cannot be distinguished from a fresh ciphertext, e.g. Randomise(Encrypt(2) + Encrypt(2)) ~ Encrypt(4), where ~ means indistinguishable.

[polyfractal]

Thanks for the explanation! Between this and some extra reading I think I'm clearer on how it all works :)