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 ...
- 151k
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 ...
- 151k
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 ...
- 145k
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,779
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 ...
- 145k
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,907
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 ...
- 12.2k
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 ...
- 28.2k
6
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.
- 28.2k
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 ...
- 151k
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 ...
- 151k
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?
...
- 145k
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 ...
- 26.4k
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)&&\...
- 145k
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.
...
- 14.5k
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 ...
- 151k
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$ ...
- 145k
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 $\...
- 5,488
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 ...
- 21.3k
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 ...
- 21.3k
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.9k
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,198
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'} ...
- 151k
4
votes
Accepted
Paillier encryption problem when q or p divides r
In Paillier encryption, the ciphertext is $c=g^n \cdot r^n \bmod n^2$, and to decrypt, you compute $m=L(c^\lambda \bmod n^2)\cdot \mu \bmod n$.
For decryption to be correct, $r$ must be a member of ...
- 4,198
4
votes
Accepted
Can the CRT speed-up Paillier decryption by more than a factor of two?
Yes, there's nothing complicated here. Let's write $\mathcal L_p(x)$ for the Fermat quotient for a prime $p$
$$\mathcal L_p(x)=\frac{(x^{p-1}-1)\mod p^2}p.$$
Then if we have $N=pq$ and a generator $g$,...
- 26.4k
4
votes
Do any probabilistic hashing algorithms have additive homomorphism?
The outputs must exhibit additive homomorphism such that some operation on $f(a)$ and $f(b)$ will equal $f(a+b)$.
Because $f$ is mandated to be nondeterministic, I assume that the requirement be that ...
- 151k
4
votes
Accepted
Proof of lemma 1 Paillier encryption
This is obtained by raising to $\lambda=\lambda(n)$: since the order of any element in $\mathbb{Z}_{n^2}$ divides $n\cdot\lambda$, the second part cancels out:
$$\begin{align}
g^{x_1-x_2}\cdot(...
- 5,488
4
votes
What is the difference between Paillier additive homomorphic property and addition of two paillier ciphers
In standard Paillier encryption
Property 1 really is:
$m_1=D(c_1)\text{ and }m_2=D(c_2)\implies D(c_1\cdot c_2\bmod n^2) = m_1+m_2\bmod n$.
Property 2 does not hold (but see final off-topic note).
...
- 145k
4
votes
Accepted
Generation of the order $\lambda$ (which is lcm((p-1),(q-1))) element g in modified paillier, why $-a^{2n}$?
If we choose $n$ to be the product of two strong primes $p=2r+1$ and $q=2s+1$ with $r$ and $s$ prime, note that $p$ and $q$ are 3 mod 4 and that $\mathrm{LCM}(p-1,q-1)=2rs$. Choosing a random $a$ and ...
- 26.4k
4
votes
Efficient multiplication modulo a square
Contrary to what fgrieu said, I believe we can do a bit better for the case of multiplication modulo $n^2$.
If we represent our values in the form $an+b$, $cn+d$ (where $0 \le a, b, c, d < n$), ...
- 151k
Only top scored, non community-wiki answers of a minimum length are eligible