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 ...
user avatar
  • 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)...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $$[...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 $\...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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$ ...
user avatar
  • 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 ...
user avatar
  • 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? ...
user avatar
  • 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 ...
user avatar
  • 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 (...
user avatar
  • 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 ...
user avatar
  • 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. ...
user avatar
  • 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.
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 $\...
user avatar
  • 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} ...
user avatar
  • 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 ...
user avatar
  • 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=(...
user avatar
  • 125k

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