15
votes
Accepted
In which public key encryption algorithms are the private and public key not reversible?
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 ...
- 134k
10
votes
Paillier can add and multiply, why is it only partially homomorphic?
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)...
- 37.8k
9
votes
Accepted
Advantages of Paillier vs Goldwasser-Micali
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 ...
- 134k
8
votes
Accepted
Paillier encryption: Many private keys for a public key
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 ...
- 12.3k
7
votes
Accepted
Equality checking using additive homomorphic encryption
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 ...
- 27k
7
votes
Are Paillier and El Gamal encryption schemes secure against quantum attacks?
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 ...
- 44.7k
7
votes
Accepted
SPDZ for the 2-party case
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 ...
- 2,857
7
votes
Accepted
Paillier paper: Number Theoretic Lemma doesn't seem to work
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 ...
- 11.2k
7
votes
Accepted
Paillier Homomorphic encryption to calculate the means
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 $$[...
- 1,699
7
votes
Accepted
Is Paillier secure from known plaintext attack for single character message?
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 ...
- 125k
6
votes
Accepted
Making Pascal Paillier' output absolute
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 ...
- 134k
6
votes
Accepted
Why is Paillier Cryptosystem called probabilistic?
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 ...
- 3,225
6
votes
What if the p and q used in keys generation of Pailler cryptosystem are composite?
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 $\...
- 12.3k
6
votes
Accepted
Homomorphic $\bmod p$ operation
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 ...
- 134k
6
votes
How to prove correct decryption in Paillier cryptosystem
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 ...
- 27k
6
votes
Paillier's scheme generalisation
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 ...
- 125k
6
votes
Accepted
Homomorphic properties of Paillier
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$ ...
- 125k
6
votes
Accepted
Paillier scheme and noise growth
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 ...
- 134k
6
votes
$n=pq$ and $n=p^2q$. How to take the value of two $n$ is the same in security
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?
...
- 125k
5
votes
Accepted
How can I do minus on plaintexts in the Paillier cryptosystem?
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 ...
- 37.8k
5
votes
Accepted
How bad would it be to reuse the random blinding factor in a scheme like Paillier?
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 (...
- 134k
5
votes
Why is Paillier Cryptosystem called probabilistic?
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 ...
- 5,932
5
votes
SPDZ for the 2-party case
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.
...
- 10.8k
5
votes
Accepted
Paillier's Cryptosystem - Secure Key Size
You should be using a 2048-bit modulus, as with RSA. Personally I feel comfortable with 1536, but 2048 is considered the minimum standard.
- 27k
5
votes
Accepted
Prove that some Cyphertext C encrypts some plaintext D
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 ...
- 134k
5
votes
Comparison of values in Paillier homomorphic encryption
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 ...
- 134k
5
votes
Accepted
How to calculate the n in n-bit security of a crypto algorithm?
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 $\...
- 4,503
4
votes
How to calculate Enc(-m) from Enc(m) in Paillier cryptosystem?
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} ...
- 134k
4
votes
Accepted
Why multiple homomorphic operations on a ciphertext leaks no information about the plaintext?
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 ...
- 37.8k
4
votes
Performance bottlenecks in Paillier encryption
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=(...
- 125k
Only top scored, non community-wiki answers of a minimum length are eligible