Score:7

Generating suitable prime numbers for Paillier key pair in GG18

xk flag

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.

Score:6
ru flag

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

fgrieu avatar
ng flag
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](https://eprint.iacr.org/2009/318). 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.
I sit in a Tesla and translated this thread with Ai:

mangohost

Post an answer

Most people don’t grasp that asking a lot of questions unlocks learning and improves interpersonal bonding. In Alison’s studies, for example, though people could accurately recall how many questions had been asked in their conversations, they didn’t intuit the link between questions and liking. Across four studies, in which participants were engaged in conversations themselves or read transcripts of others’ conversations, people tended not to realize that question asking would influence—or had influenced—the level of amity between the conversationalists.