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 ...
9
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 ...
9
The multiplicatively homomorphic variant of RSA is not semantically secure. This is a major disadvantage. ElGamal is a semantically secure, multiplicativey homomorphic cipher. Paillier is a semantically secure, additively homomorphic cipher.
As described by tylo, all homomorphic ciphers are malleable by definition. Chances are, however, if you are ...
8
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
The homomorphic property also implies malleability. This means, if you have some ciphertext, then you can create a different ciphertext with a related plaintext, and this property can be unwanted in this scheme (e.g. in an auction where you just encrypt your actual bid; then the attacker could just use your bid $+1$ or exchange your name with his, etc.) ...
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
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
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
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 ...
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 ...
6
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}(\...
5
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 ...
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
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
You should be using a 2048-bit modulus, as with RSA. Personally I feel comfortable with 1536, but 2048 is considered the minimum standard.
5
This can be done by using a zero-knowledge proof to prove that a Paillier ciphertext is an encryption of zero. Specifically, let $c$ be the original ciphertext, and let $m$ be the decryption that Alice sends back to Bob. Then, both Alice and Bob can each locally use the homomorphic property to compute a ciphertext $c'$ that is an encryption of the value ...
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
Does the problem of noise growth exist in the Paillier homomorphic scheme ?
No, it does not. Unlike Lattice-based schemes, you can do as many homomorphic additions as you want in Paillier (without doing anything like a "reboot"), and it's never a problem.
4
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 ...
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
Being malleable they are prone to alteration of data in case your trusted party doing the computation is malicious. For example in Paillier Cryptosystem, you use the encryption scheme so that the other party should not know the actual value which you passed to do the computation. But in case the second party doing computations is corrupt or even if not ...
Only top voted, non community-wiki answers of a minimum length are eligible
