Hot answers tagged

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

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


4

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.


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

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


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


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

Regardless whether input is small, $n$ must be large enough to avoid factorization. Next, $r$ must be sampled from a large space to avoid decryption by trial-and-error. Some crypto and big-numbers library (bouncycastle, openssl, crypto..) might be handy to implement such an algorithm. It would be safe to choose an implementation rather than write it from ...


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


2

No, there are no security compromises; the Pallier system remains secure. Both messages are in the supported message space and as Paillier encryption provides IND-CPA security you are safe when doing this.


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

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


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

Let's review the encryption process for Paillier: Let $m$ be a message to be encrypted where $m\in\mathbb{Z}_n$ (in your case $m\in\{0,1\}$) Select random $r$ where $r\in\mathbb{Z}_n^*$ Compute ciphertext as: $c=g^m\cdot r^n\bmod{n^2}$ It is that random value $r$ that makes it so that encrypting values drawn from a small plaintext space does not have ...


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



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