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
They're both additively homomorphic, but over different groups.
With Goldwasser-Micali, you can, given $E(x)$ and $E(y)$, compute $E(x \oplus y)$ (where $\oplus$ is exclusive or)
With Pallier, you can, given $E(x)$ and $E(y)$, compute $E(x + y \bmod n)$, where $n$ is a large integer; this implies that, given $E(x)$ and $k$, you can compute $E(kx \bmod n)$
...
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 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
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\...
7
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$.
...
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 ...
7
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 $[\!...
7
Yes, Paillier encryption is secure from known plaintext attack (for single-character message, and any other supported message size). With high likelihood, three ciphertexts $c_1$, $c_2$ and $c_3$ for the same plaintext will be different.
When using public modulus $n$, each Paillier encryption draws a uniformly random number $r$ in range $[0,n)$ (some ...
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 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:
$...
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
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
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}(\...
6
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.
6
In "I take 3072 for Paillier's $n$", 3072 is surely the bit size of $n$. Thus I'll read the question as:
How wide should be OU's $n=p^2q$ to be as safe as Paillier's $n=pq$ of 3072 bits?
The best known attack against both cryptosystems is the factorization of $n$.
The best known factorization method for $n=pq$ with $p$ and $q$ random primes of ...
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
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 ...
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
Can [comparison] be done using homomorphic encryption?
Not without interaction with the person with the private key.
Suppose there was a possible way; given $E_k(a)$ and $E_k(b)$, one could determine whether $a < b$. If so, then one could use that to decrypt - given $E_k(a)$, one can encrypt various values of $b$ and then check whether $a < b$ or ...
5
TLDR: The size of the group/ring is dictated by the fastest currently-known attack (as explained in this Wikipedia article).
Details. For the case of discrete-log in $\mathbb{Z}_p^*$ and factoring $\mathbb{Z}_N^*$, the fastest currently-known algorithm is the general number field sieve (GNFS). GNFS has a run-time of (roughly) $L_n(1/3,2)$, where $$L_n(\alpha,...
Only top voted, non community-wiki answers of a minimum length are eligible