# Tag Info

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 ...
• 146k
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 ...
• 146k
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.6k
Accepted

• 140k
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 ...
• 146k
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$ ...
• 140k
Accepted

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 $\... • 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 ... • 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 ... • 19.9k 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 ... • 19.9k 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 ... • 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 ...
• 4,168
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'} ...