I am working on MPCs (multi party computation) in crypto, and now I am developing a implementation of GG 18.

In sign phase, algorithm needs MtA (Multiplicative to Additive) and uses a Paillier key pair for this.

Paillier uses modulus $N$ ($N=p_1 * p_2$†, prime numbers drawn at key generation). But we need to consider the order $q$ of the elliptic curve. spec256k1 for example, so the algorithm has some considerations.

Consider that Alice and Bob have $a$ and $b$ as their secrets. and they want to get $\alpha$ and $\beta$ so that $a*b = \alpha + \beta$, without revealing their secrets.

GG18 says that for modulus problem there are some considerations:

  • $a$ must be less than $q^3$.
  • $b$ must be less than $q^3$.
  • $\beta$ must be less than $q^5$.
  • $N$ must be greater than $q^8$.

In spec256k1, $q$ (115792089237316195423570985008687907852837564279074904382605163141518161494337) is very close to $2^{256}$. So $q^8$ is very close to $2 ^{2048}$.

If I generate random 1024-bit prime numbers $p_1$ and $p_2$ for Paillier key generation, I almost never can not satisfy this condition :

$N = p_1 * p_2 > q^8$

What can I do? I can use greater numbers for $p_1$ and $p_2$ (1025 bit for example. It gives me a 2050-bit $N$ that most of the time is greater than $q^ 8$)

Is there any other solution? I prefer use 1024 bit numbers for $p_1$ and $p_2$.

I use "$p_1$" and "$p_2$" instead of "$p$" and "$q$" for Paillier key generation to prevent confusion with "$q$" as order of elliptic curve.


1 Answer 1


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 number $r$, add it to $q^4$ and use this as a starting point for your prime search. Once you have found a prime number, pick another random 898-bit number and search again. Both primes that you find will be greater than $q^4$ and so their product will be greater than $q^8$.

  • 1
    $\begingroup$ Yes. This is safe against basic Fermat factoring, which cost is $(p_1-p_2)^2/(p_1+p_2)/k$ operations for some moderate $k$ (in the thousands, subject to a time/memory tradeoff). And also against known improvements e.g. this paper. We can't meet the FIPS 186-5 requirement that $|p_1-p_2|>2^{924}$, but I rescind my earlier comment that something based on Coppersmith's theorem might endanger what's proposed. SNFS won't be an issue either. $\endgroup$
    – fgrieu
    May 8, 2023 at 14:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.