# Generating suitable prime numbers for Paillier key pair in GG18

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.

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