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 ...
poncho's user avatar
  • 146k
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 ...
poncho's user avatar
  • 146k
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 ...
tylo's user avatar
  • 12.6k
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 $$[...
user94293's user avatar
  • 1,779
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 ...
yyyyyyy's user avatar
  • 12.1k
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 ...
Guut Boy's user avatar
  • 2,867
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 ...
Yehuda Lindell's 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 ...
SEJPM's user avatar
  • 45.9k
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 ...
fgrieu's user avatar
  • 140k
7 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 ...
fgrieu's user avatar
  • 140k
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 ...
ddddavidee's user avatar
  • 3,324
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 ...
poncho's user avatar
  • 146k
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 ...
Yehuda Lindell's user avatar
6 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 ...
poncho's user avatar
  • 146k
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 ...
poncho's user avatar
  • 146k
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? ...
fgrieu's user avatar
  • 140k
6 votes
Accepted

Generating suitable prime numbers for Paillier key pair in GG18

The difference between $2^{1024}$ and $q^4$ is over 898-bits, which leaves more than enough diversity for choosing prime numbers and protection from Fermat factoring. Simply choose a random $898$-bit ...
Daniel S's user avatar
  • 23k
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.
Yehuda Lindell's user avatar
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. ...
Mikero's user avatar
  • 13.1k
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 ...
curious's user avatar
  • 6,150
5 votes
Accepted

Paillier subtraction for negative result

In Pailler encryption, it holds for all messages $m_1$ and $m_2$, and whatever randoms[*] are used by encryption, that: $$\begin{align} (m_1+m_2\bmod n)&=D(E(m_1)\cdot E(m_2)\bmod n^2)&&\...
fgrieu's user avatar
  • 140k
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 ...
poncho's user avatar
  • 146k
5 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$ ...
fgrieu's user avatar
  • 140k
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 $\...
ckamath's user avatar
  • 5,188
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 ...
mikeazo's user avatar
  • 38.5k
4 votes
Accepted

Showing the decrypted sum of encrypted values

There is a recent line of work that does exactly this; it is called functional encryption for inner-product. It allows to encrypt a vector of integers (from some exponent space $\mathbb{Z}_p$) so that ...
Geoffroy Couteau's user avatar
4 votes
Accepted

In Paillier homomorphic encryption, do we need to take modulo after multiplication of 2 ciphertexts?

Yes, both will give the same result. However, taking mod after each multiplication is far more efficient: if you do not take modulos during intermediate multiplications, the size of the strings you ...
Geoffroy Couteau's user avatar
4 votes
Accepted

Paillier Homomoprhic addition overflows after a certain value

The plaintext space for Paillier is integers modulo $n$. You are seeing "overflow" at the modulus, which makes sense. You should choose larger primes for both security reasons and to make it so that ...
mikeazo's user avatar
  • 38.5k
4 votes
Accepted

Paillier: guessing the message when knowing the cipher and the random number

You don't need to guess, you can find $m$ for sure. If you know $c,r,n,g$, then you can eliminate $r^n$ from the ciphertext and get $c'=g^m \bmod n^2$. In $Z_{n^2}^*$, we have $(n+1)^x = 1+nx \bmod ...
Changyu Dong's user avatar
  • 4,168
4 votes
Accepted

In a specific Paillier implementation, why is r prime?

Is there any risk in changing the implementation to make $r$ random but not necessarily prime? None [1]. Consider the case where you encrypt two values, forming the ciphertexts $g^m r^n$ and $g^{m'} ...
poncho's user avatar
  • 146k

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