Tag Info

Hot answers tagged

4

No, exactly equal length of primes $p$ and $q$ is not mandatory for security (or proper functioning) in the Pailler cryptosystem. Sufficient requirements are that $p$ and $q$ are prime, $N=p q$ is hard to factor, and $\gcd(p q,(p-1)(q-1))=1$. The requirement that $p$ and $q$ are of exactly equal size is usually made in the Pailler cryptosystem because this ...


3

The requirement is that your element $g$ is in $\mathbb{Z}_{n^2}^*$ and not in $(\mathbb{Z}_{n}^*)^2$. The set $\mathbb{Z}_{n^2}^*$ is the set of integers smaller than $n^2$ that are relatively prime to $n^2$, i.e., you require an element $g$ from $\mathbb{Z}_{n^2}$ such that $\gcd(g,n^2)=1$. $(\mathbb{Z}_{n}^*)^2$ on the other hand is the set of pairs ...


3

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=(1+n\cdot m)\cdot r^n\bmod n^2$. Some ideas: In some contexts, it is feasible to pre-compute $r^n\bmod n^2$ in masked time, before the encryption itself, ...


3

You have to worry not just about a pair of blinding values being equal, but more complex relationships between them. Thus, finding a proof of security for this approach looks non-trivial to me. Let me elaborate. Suppose $R_j$ is the $j$th blinding variable you use. If $R_i = R_j$, that's a problem, but as you say, that can be made very unlikely. ...


2

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 (and the entire point of blinding values is to prevent anyone from doing so). Suppose we had two original encrypted values $c$, $d$, and the corresponded blinded ...


1

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 is use the multiplicative. This works fine when the result is positive. When the result is negative, however, you would like to return that value, but what ...


1

In your question, you already pointed out, that the necessary condition is More generally largest prime minus one does not consists of smallest prime as a prime factor therefore, it is sufficient to just check if $p$ divides $q-1$ by computing division. You can just verify this condition during the key generation. I don't know of a more efficient ...


1

Since $p$ and $q$ are primes, the only factors you needs to rule out are those two numbers. Suppose $p$ divides $(p-1)(q-1)$. Then it divides either $p-1$ (clearly not true) or $q-1$. The latter means $q-1 = p \cdot x$, for some $x \ge 2$ (if $x = 1$ either $p$ or $q$ is even, which is only possible if the numbers are 2 and 3). However, then $q \ge 2p+1$, ...



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