1
$\begingroup$

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

$\endgroup$
1
  • $\begingroup$ 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. $\endgroup$
    – Thomas
    Commented Mar 5, 2013 at 6:33

1 Answer 1

1
$\begingroup$

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).

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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