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.