# Security relevance of random factor in Paillier

In the Paillier cryptosystem [1] the encryption of $m \in \mathbb{Z}_N$ with randomness $r \in \mathbb{Z}_n^*$ is $c = g^m r^n \bmod{n^2}$.

The additive-homomorphic property of the system shows that $g^{m_1} r_1^n \cdot g^{m_2} r_2^n = g^{m_1+m_2} (r_1r_2)^n = g^{m_1+m_2} r'^n\mod n^2 = m_1 + m_2 \mod n$

so the resulting $r'$, that would be needed to encrypt $m_1 + m_2$ to the identical result of the homomorphic addition, would be: $r_1 \cdot r_2 \mod n^2$

Supposed now one were to homomorphically sum up the encryptions of a couple of messages from a limited publicly known set of plaintexts $S=\{0, 1\}$. If one then were to proof the correct encryption of the sum by disclosing the encrypted sum, the plaintext sum and the resulting random factor $r'$ for the encrypted sum - would this provide any useful information about which summand encrypts which plaintext message?

Assuming "revealing r" would provide any information about the summands of a homomorphically added sum. Would it help to use primes as random factors for the encryption of the summands? I mean an attacker then would have to find an efficient way to factorize the resulting $r'$.

Is there a way to turn "revealing r" into an interactive version involving a challenge? Would this solve the problem that by passing on $r'$ the proof becomes transferable which may be an undesired property?

[1] Pascal Paillier - Public-Key Cryptosystems Based on Composite Degree Residuosity Classes Link

• Revealing $r_1 \cdot r_2 ~ \text{mod} ~ n^2$ will not reveal $r_1$ and $r_2$, since there are exponentially many pairs of solutions, and only one will allow the recovery of $m_1$ and $m_2$ given the two ciphertexts. – Thomas Mar 5 '13 at 6:33

Easy solution is to use a large $r$. You are correct that if the $r$'s were small primes we would have a problem, ergo randomness is essential. However, if the $r$'s are generated randomly then their product doesn't help in guessing one. (Think about guessing $x,y$ random given $x+y$ in an abelian group).