# Tag Info

## Hot answers tagged paillier

5

No, it is not possible to compute $\lambda$ easily. Specifically, if you have a black box that, given a random instance $c$, $c^\lambda \bmod n^2$, was able to recover $\lambda$ with nontrivial probability, you can use that to factor $n$ with nontrivial probability. Hence, if we believe the factorization problem is hard, we must also believe that this ...

3

Yes (and always). Given $\mathsf{Enc}(a)$ and $b$, you can compute $\mathsf{Enc}(a \cdot b^{-1} \bmod{n})$ by simply computing $\hat{b}=b^{-1} \bmod{n}$ and $Enc(a)^\hat{b} \bmod{n^2}$. Paillier encryption is built on the bijeective mapping from $(x,y)\in \mathbb{Z}_n \times \mathbb{Z}_n^*$ to: $E_{g,n}(x,y)=g^x y^n \bmod{n^2}$. Generator $g$ is chosen ...

2

You probably don't need to re-encrypt using the Paillier crypto system. 1) Alice encrypts $c_1=g^{m_1} r_1^n$ und $c_2=g^{m_2} r_2^n$ and computes $r_3=r_1 \cdot r_2$ and $m_3=m_1+m_2$, then sends $c_1$, $c_2$, $m_3$ and $r_3$ to Bob 2) Bob computes $c_3=c_1 \cdot c_2=g^{m_3} r_3^n$ - If the homomorphically computed sum matches the re-encryption Bob will ...

1

Yes. This can be solved through standard methods. Alice can prove she decrypted the ciphertext correctly by revealing the decrypted message and the random coins that would be used in encryption to obtain this ciphertext from this message. Suppose we have a ciphertext $c$, and Alice decrypts it to obtain the message $m$. It follows that $c = g^m r^n \bmod ... 1 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). 1 Revealing$r$would then allow the verifier to prove to someone else (another verifier) that$c$encodes$i$. The verifier could also prove other things knowing$r$to a different verifier (any other proof using a paillier ciphertext, the corresponding plaintext, and the random value$r$). With the ZKP, the verifier cannot prove anything to anyone else ... 1 Yes.$r^n$needs to be coprime with$n^2$. The only elements which have don't an inverse modulo$p^2 q^2$are all multiples of$p$and all multiples of$q$, so we just require$\gcd{(r^n, p)} = \gcd{(r^n, q)} = 1$.$\implies \gcd{(r^n, n}) = 1$Clearly, if$r$is coprime to$n$, then$r \times r \times \cdots \times r ~ (n ~ \mathrm{times})$will also be ... 1 Let us briefly recall the Paillier encryption. Let$k_{pub} = (N = PQ, g)$be a public key, where$N$is the RSA modulus. The secret key is$\lambda = \mathrm{lcm}(P-1,Q-1)$(or$P,Q$). The encryption of$p \in \mathbb{Z}_N$with randomness$r \in \mathbb{Z}_N^*$is$C = g^p r^N \bmod{N^2}$. You can verify$\mathbb{Z}_{N^2}^* \simeq \mathbb{Z}_N \times ...

1

I'm doing this as another answer since my first answer was incorrect. Your calculation of s2 is incorrect. In python I did it as s2 = pow(m*pow(inverse(G,N),s1,N), inverse(N,Lambda), N) Mathematically it would be $((G^{-1})^{s1}\bmod{N})$ for the term $G^{-s1}$ or equivalently $(G^{s1})^{-1}\bmod{N}$. In words, the inverse of $G$ (modulo $N$) raised to ...

1

One alternative that hasn't been mentioned, which may possibly be of interest, is doing plain old integer division in Paillier. The protocol is non-trivial, but, perhaps surprisingly, can be done somewhat efficiently. There was a paper at FC12: On Secure Two-party Integer Division [PDF]

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