4

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


1

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


Only top voted, non community-wiki answers of a minimum length are eligible