Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|improve this question
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).

share|improve this answer

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.