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

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 ...


2

No, there are no security compromises; the Pallier system remains secure. Both messages are in the supported message space and as Paillier encryption provides IND-CPA security you are safe when doing this.


2

Paillier is not order preserving, so in your algorithm $x_1+y_1$ IF and ONLY IF $x_1+y_1 <= x_2+y_2 \dots$ simply does not work. You can't do the $\leq$ comparison. Whether you have the same $r$ or not does not really matter, if we look at the encryption: $E(m)= g^m r^n$ mod $n^2$ You could try to achieve that by fixing $r^n$ such that the product with ...


1

Let's review the encryption process for Paillier: Let $m$ be a message to be encrypted where $m\in\mathbb{Z}_n$ (in your case $m\in\{0,1\}$) Select random $r$ where $r\in\mathbb{Z}_n^*$ Compute ciphertext as: $c=g^m\cdot r^n\bmod{n^2}$ It is that random value $r$ that makes it so that encrypting values drawn from a small plaintext space does not have ...


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