# Tag Info

This is obtained by raising to $\lambda=\lambda(n)$: since the order of any element in $\mathbb{Z}_{n^2}$ divides $n\cdot\lambda$, the second part cancels out: \begin{align} g^{x_1-x_2}\cdot(y_2/y_1)^n=1\bmod{n^2} &\Leftrightarrow\\ g^{(x_1-x_2)\cdot\lambda}\cdot(y_2/y_1)^{n\cdot\lambda}=1\bmod{n^2}&\Leftrightarrow\\ g^{(x_1-x_2)\cdot\... 4 Does the problem of noise growth exist in the Paillier homomorphic scheme ? No, it does not. Unlike Lattice-based schemes, you can do as many homomorphic additions as you want in Paillier (without doing anything like a "reboot"), and it's never a problem. 4 The outputs must exhibit additive homomorphism such that some operation on f(a) and f(b) will equal f(a+b). Because f is mandated to be nondeterministic, I assume that the requirement be that f(a) \odot f(b) be some possible output f(a+b) (for some computable operation \odot). If so, there must be some further requirement; here's one f ... 3 What information does \mu leak about \lambda? The safe assumption is: all. It must be assumed that knowledge of \mu, together with the public key, allows computing \lambda (which allows decryption and factorization of n). At least, that holds in Paillier's scheme as described in Jonathan Katz and Yehuda Lindell's Introduction to Modern ... 3 Promoting my comment to an answer: Encryption hides information from someone who doesn't know the decryption key. In your case, P_2 knows the decryption key, and can therefore learn x. This is really no different than sending x in the clear to P_2. Note that this is the strange example from the book that is secure in the malicious setting but not ... 3 With Paillier, it's easy; generate a random encryption of 0 (r^n \bmod n^2 for random r r.p to n), and then homomorphically add it to the encryption (that is, C2 = C1 \cdot r^n \bmod n^2), and you're done (and all you need is the public key). I don't believe RSA allows this as a possibility... 2 The Paillier cryptosystem allows to encrypt integers modulo n. Therefore, if m is bigger than n, encrypting it will lose most of the message - only m \bmod n is retrieved through decryption. To encrypt a message bigger than n, you must break it into blocks, which you encrypt separately. You can for example write m in base n, as m = \sum_i m_i ... 2 You made a mistake in decryption. You wrote: m = 1191*3 mod 35 You lost L(...) here. Instead of 1191 it should be L(1191): m = L(1191)*3 mod 35 L(1191) = 34 m = 34*3 mod 35 m = 102 mod 35 m = 32 Voilà. We got the original message. 2 It is strange that Wikipedia propose to choose r\mod N^2 while r^N\mod N^2 depends on r\mod N only:(r+tN)^N=r^N+r^{N-1}tN^2+\ldots\equiv r^N\pmod{ N^2}.$$It means that you can recover only r\mod N. In order to do it you can use the formula from the cited answer$$r\equiv (r^N)^M\pmod{ N}, $$where M = N^{-1}\bmod \phi(N). 1 What is so difficult about this if z=y^n\ mod\ n^2 We don't know of an efficient way of solving it. That's essentially what we can say about just about any hard problem in cryptography. We also don't know a reduction to a better studied problem (for example, the factorization problem); hence it gets called out as a separate hard problem. The ... 1 The difficult part about understanding the Paillier cryptosystem is to understand what the L function in the cryption actually does and why it works. The good news is: To understand the homomorphism, that detail can be put on hold. The best way to understand homomorphism is to have a close look at the encryption function. Here it is:$$ E(m) = r^n g^m \...
You can find the folowing information in the book Katz, Lindell "Introduction to modern cryptography". PROPOSITION 13.6 Let $N=p q$ , where $p, q$ are distinct odd primes of equal length. Then: $\operatorname{gcd}(N, \phi(N))=1.$ For any integer $a \geq 0,$ we have $(1+N)^{a}=(1+a N) \bmod N^{2}.$ As a consequence, the order of $(1+N)$ ...