15
Are there other public key systems that do not have this property?
A more cogent question might be "are there any public key systems other than RSA that does have this property?"
In particular, I'm calling "this property" the idea that you can swap the public and private keys and remain secure (which you can do with RSA, as long as you select large public ...
13
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 ...
7
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,...
7
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, ...
7
No, that doesn't work.
If one party chooses primes $p,q$ and sets $n = pq$, then other parties would also have to know $p$ and $q$, because it is the only way to get the same $n$.
But you just left out a part of the public key, which is $g$. This results in a different question:
If you have a trusted party set up $n$ and assign different $g$ values to each ...
7
Your understanding is correct. The SPDZ protocol can be used for any number of two or more parties. In fact, this is one of the strengths of the SPDZ protocol. Namely, many recent secure computation protocols such as the various versions of the Yao protocol or the TinyOT protocol are limited to two parties. So it may sometimes be overemphasized that SPDZ ...
7
Short answer: This appears to be an error in the paper, but it's not a problem in practice.
The proof of Lemma 3 uses the following implication:
Since $\gcd(\lambda,n)=1$, $x_2-x_1$ is necessarily a multiple of $n$. Consequently, $x_2-x_1=0\bmod n$ and $(y_2/y_1)^n=1\bmod n^2$, which leads to the unique solution $y_2/y_1=1$ over $\mathbb Z_n^\ast$.
As ...
6
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 ...
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 ...
6
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$...
6
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\...
6
Sure there's a difference between Paillier and ElGamal as opposed to lattice-based cryptography regarding quantum attackers.
Paillier's security is broken as soon as you can efficiently factor large integers which is "easy" using Shor's algorithm. This is caused by the fact that you can easily recover the private from the public key by factoring $n$.
...
6
Is there any protocol, that given $E(m)$ can compute homomorphic $E(m \bmod p)?$
If there were a way to perform that operation (for any $p>1$ relatively prime to $N$) without the Pallier private key being involved, then you have just shown that Pallier is Fully Homomorphic; that is, you can homomorphicly implement any computation; at the very least, by ...
6
The Paillier encryption of an integer $x_i$ is given by $c_i = (1+x_iN)r_i^N \bmod N^2$ for some random $0<r_i<N$. Given the encryption of $x_1, \dots, x_k$, the encrypted mean is defined as $$[\![\mu]\!] = \left(\prod_{i=1}^k c_i\right)^{k^{-1}\bmod N} r^N\bmod N^2$$
for some random $0<r<N$.
If we now apply Paillier decryption procedure to $[\!...
6
Yes, Pailler encryption can be generalized to the product of more than two (distinct) primes, much like in multi-prime-rsa. We just have $N=\prod p_i$ with $i\ne j\implies p_i\ne p_j$. Each $p_i$ must be secret and uniformly random in some large interval. It we want to use $g=N+1$ as the generator (which is common) without an explicit check of its order, it ...
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
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:
$...
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
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 ...
5
my understanding I could use it to do 2-party computation
You are correct, SPDZ can give secure MPC for any number of parties. It is just a matter of generating enough multiplication triples.
Should I favor a 3 party setting instead of a 2 party one when using SPDZ?
Whichever makes sense in your application is fine.
why is not widely use for the 2-...
5
Assuming that $D$ is the correct decryption, we have
$$C = g^D r^n \pmod{n^2}$$
for some value $r$.
Someone with the private key can easily recover $r$; hence they can just display it (and you can easily verify the above equation).
Learning the value $r$ does not allow you to derive the private key (if it did, you could encrypt values yourself using a ...
5
No, there is no reason that $\textsf{Dec}(\textsf{sk}, \textsf{Enc}(\textsf{pk},\alpha)^{\textsf{Enc}(\textsf{pk}, \alpha^{-1})})$ would be $\alpha\cdot\alpha^{-1}$, including when we spread $\bmod N$ or $\bmod N^2$ here and there.
What does apply is: for overwhelmingly most $\alpha$ and $k$ in $\Bbb Z$, it holds that $\textsf{Dec}(\textsf{sk},\textsf{Enc}(\...
4
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 ...
4
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 ...
4
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 ...
4
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, ...
4
Yes, it is possible.
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
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 $...
Only top voted, non community-wiki answers of a minimum length are eligible
