# Tag Info

10

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

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

5

Well, the problem is with logical OR and subtraction (which Pallier can also do), you've got FHE; that is, you can compute any combinatorial function of encrypted (binary) inputs. Here's how it works, you can construct the NAND function: $NAND(x, y) = (Enc(1) - x)\ OR\ (Enc(1) - y)$ If we limit $x$ and $y$ to being either encrypted 0, or encrypted 1, ...

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, b$...

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.

4

The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$. The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$. $(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs $(a,... 4 No, exactly equal length of primes$p$and$q$is not mandatory for security (or proper functioning) in the Pailler cryptosystem. Sufficient requirements are that$p$and$q$are prime,$N=p q$is hard to factor, and$\gcd(p q,(p-1)(q-1))=1$. The requirement that$p$and$q$are of exactly equal size is usually made in the Pailler cryptosystem because this ... 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 I'm not sure if I understand what you are asking, so I'll clarify what I am about to answer. We are given two ciphertexts and we want to know if they encrypt the same plaintext or if they encrypt different plaintexts, and we want to do this without revealing anything but this fact. Then, using the additive homomorphism, it's possible to compute$c=enc(r\...

3

You have to worry not just about a pair of blinding values being equal, but more complex relationships between them. Thus, finding a proof of security for this approach looks non-trivial to me. Let me elaborate. Suppose $R_j$ is the $j$th blinding variable you use. If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely. However,...

3

The first obvious objection is that it would do a lousy job of blinding values; if you reuse the blinding factor, then it would be practical to correlate the blinded values with their original ones (and the entire point of blinding values is to prevent anyone from doing so). Suppose we had two original encrypted values $c$, $d$, and the corresponded blinded ...

3

Recall that in Paillier encryption with public key $n$ of private factorization and $g=1+n$, encryption of plaintext $m$ reduces to: choose random $r$, $0<r<n$ compute and output ciphertext $c=(1+n\cdot m)\cdot r^n\bmod n^2$. Some ideas: In some contexts, it is feasible to pre-compute $r^n\bmod n^2$ in masked time, before the encryption itself, ...

3

Yes, it is possible.

3

In Paillier, as you note, multiplication in the ciphertext domain translates to addition in the plaintext domain. Thanks to the algebraic structure behind Paillier what you can do to get subtraction is use the multiplicative. This works fine when the result is positive. When the result is negative, however, you would like to return that value, but what ...

3

I may have found an answer (welcoming any comment on whether I missed something) which works, given certain size restrictions on the input $x$ and $y$: Say, party A has Enc(x) and Enc(y): A flips a coin: b in {-1, 1} A computes: $Enc(c) = (Enc(y) Enc(-x))^{b*r} Enc(-r') = Enc(b*r*(y-x)-r')$ where (r, r') are a pair of random obfuscating values such that: ...

3

How to know how much space to reserve? There are two ways: Take an implementation of the scheme, encrypt a 32-bit plaintext, and see how long the resulting ciphertext is. This is the simplest approach. Understand the scheme at a conceptual level, and then use your understanding of the algorithm to predict how long the ciphertext will be. Since it sounds ...

3

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

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

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 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 ... 2 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 ... 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 Let$c$denote a ciphertext and let$m$denote a plaintext. To my best knowledge, researchers in cryptography employ "bandwidth" as different meanings, say, ciphertext expansion ($|c|/|m|$) or a number of bits of plaintexts contained in a ciphertext ($|m|$). @owlstead refers "overhead," which is$|c| - |m|$. For example, Joye and Libert (EUROCRYPT 2013, ... 2 In your question, you already pointed out, that the necessary condition is More generally largest prime minus one does not consists of smallest prime as a prime factor therefore, it is sufficient to just check if$p$divides$q-1$by computing division. You can just verify this condition during the key generation. I don't know of a more efficient way,... 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. 2 Paillier is not order preserving, so in your algorithm$x_1+y_1$IF and ONLY IF$x_1+y_1 <= x_2+y_2 \dots$simply does not work. You can't do the$\leq$comparison. Whether you have the same$r$or not does not really matter, if we look at the encryption:$E(m)= g^m r^n$mod$n^2$You could try to achieve that by fixing$r^n$such that the product with ... 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 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.

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