search

snipsco / rust-paillier

A pure-Rust implementation of the Paillier encryption scheme
Other
80 stars 12 forks source link

document need for explicit rerandomisation #22

Open mortendahl opened 7 years ago

mortendahl commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

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 commented 7 years ago

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