# Tag Info

6

For starters: Paillier and RSA are based on very similar assumptions, and both systems would be broken immediately by an algorithm to factor large composites. Additionally, knowing $\phi(n)$ or $\lambda(n)$ is quite essential to both systems, because the trapdoor for decryption is based on that. As you can see, the relation to RSA is quite close, and thus ...

5

Because each time you encrypt a message $m$, its ciphertext changes and is not the same (each time you encrypt you pickup a random element $z \leftarrow \mathbb{Z}_n^*$). If for each message there was the same ciphertext then the encryption scheme would be deterministic and would not be semantically secure or would not provide indistinguishability.

5

No, or at least, if you can, you have an Extremely Significant result; you've just shown that Paillier is a Fully Homomorphic system, and so it could perform any operation on encrypted data (and in a way that's significantly more efficient than any other known FHE system). Here's why: The $|a - b|$ operation is effectively an $XOR$; if the ciphertexts $a, ... 4 Yes, for example CryptDB uses the Paillier cryptosystem to implement homomorphic encryption for columns that require it. See CryptDB: Protecting Confidentiality with Encrypted Query Processing (pdf) for a description. Whether you consider that use "effective" is another matter. Earlier this month there was a back and forth between the CryptDB developers and ... 3 As user curious said in a other answer probabilistic means that the encryption of the same plaintext under the same key gives as output a different ciphertext. This is a more general property and it is known as a basic security property: it is usually refered to as semantically secure or indistinguishability (roughly: an attacker cannot guess which one of ... 3 If the parties do exactly what you have described, then yes, the malicious server can learn some information. In particular, if$h_1 == h_2$, then$c_D == c_E$. So, given the$c$values, the malicious server can learn whether or not$h_1 == h_2$. Furthermore, the malicious server can learn if either$h$value is$1$, as$c$would not change. Finally, if the ... 3 Actually, computing the inverse modulo$n^2$using (say) the Extended Euclidean method is exactly what you do. If$c = g^m r^n \bmod n^2$is an encrypted version of$m$, then$c^{-1} = (g^m r^n)^{-1} = g^{-m} (r^{-1})^n$is a representation of$-m$(because if$r \in \mathbb{Z}^*_n$, so is$r^{-1}$) That$enc(m) * enc(-m)$isn't precisely 1 isn't relevant; ... 3 With version 1, you are essentially using an additively homomorphic substitution cipher. I understand that the database is quite large, but the number of different values small. This (typically) means that statistical analysis can be used to derive a lot of information, especially if the attacker has some auxiliary information which is often the case. This ... 2 No. There are$2^{32}$ciphertexts that fit into 32 bits. They will decrypt to$2^{32}$random plaintexts uniformly distributed in the range$\{0, 1, \ldots, 2^{|n|}\}$. Since$|n| \gg 32$for practical Paillier moduli, the probability of any 32-bit ciphertext encoding a plaintext in$\{0, \ldots, 44\}$is negligibly small. 2 It can not do multiplication in the plaintext domain using two ciphertexts. In other words, given$E(m_1)$and$E(m_2)$, you can not get$E(m_1\cdot m_2)$. You can only get$E(m_1+m_2)$. Given$E(m_1)$and$m_2$, you can get$E(m_1\cdot m_2)$however. But notice that$m_2$in this case was not encrypted. On the site you reference,$C$is not encrypted. It ... 1 With Damgard-Jurik, not only expansion factor is decreased: this scheme improves state of the art. Reducing size of prime factors makes better chance of factoriation or maybe solving particular decision problem that Paillier scheme depends on. 1 Does the limited range of the values, makes cracking the Paillier cryptosystem easier? That depends. I'm assuming that you are generating good, large random$r$values, just reusing them for the same plaintexts. The main problem with this is that you loose semantic security. It however does not lead to a key leakage attack (AFAIK). So, your question is ... 1 You should not use keys smaller than 1024, and even 1024 is considered too small today. However, if you want additive homomorphism, then you can you encrypt with "ElGamal in the exponent" over Elliptic curves. To explain what I mean by this, let$G$be the base point (generator) for the Elliptic curve group, let$x$be the ElGamal private key, and let ... 1 No, this is not possible. The homomorphism only works at one layer. A ciphertext in Paillier is$g^m\cdot r^n\bmod{n^2}$. The plaintext space is the multiplicative group of integers modulo$n$. So, for it to even have a chance to work, first of all, the modulus of the outer encryption would have to be greater than$n^2$, where$n\$ is the modulus of the ...

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