Working with Paillier and ECDSA - Order issue

Question

I'm trying to implement two party computation for ECDSA signing using Paillier cryptosystem.

But my problem is that the order of Paillier is different from the order of the curve (secp256k1 in my case) so when I multiply two scalars in Paillier and then I decrypt them they are in a different order than the rest of the parameters.

Concrete example:

Paillier order - N
ECDSA order - Q

Alice got her secretKey - aliceSK
Bob got his SecretKey - bobSK

Alice generate Paillier key pair - (paAliceSK, paAlicePK)

expectedRes = (aliceSK X bobSK) mod Q

encAliceSK = Paillier.Encrypt(paAlicePK, aliceSK)
encBobSK = Paillier.Encrypt(paAlicePK, bobSK)

encRes = Paillier.Mul(paAlicePK, encAliceSK, encBobSK)

res = Paillier.Decrypt(paAlicePK, encRes)
res = res mod Q

I get at the end that res != expectedRes.

But when I calcluate the expectedRes with mod N I'll get res == expectedRes.

So my question is how should I use Paillier and return the decrypted Paillier result back to the curve order.

Answer 1

One possibility is we choose¹ a small public integer $r>1$ with $r^{(q-1)/2}\equiv-1\pmod q$, and ensure² the $n$ in Pailler is at least $2q-1$. Now $x\mapsto r^x\bmod q$ is a bijection on $[1,q)$.

Alice chooses $\widetilde{\mathsf{aliceSK}}$ uniformly at random in $[1,q)$ and derives $\mathsf{aliceSK}=r^{\widetilde{\mathsf{aliceSK}}}\bmod q$. She Pailler-encrypts $\widetilde{\mathsf{aliceSK}}$.

Same for Bob.

Somewhat the Pailler ciphertexts get Pailler-combined (that is multiplied modulo $n^2$ where $n$ is the public Pailler modulus) and Pailler-deciphered to $d=\widetilde{\mathsf{aliceSK}}+\widetilde{\mathsf{bobSK}}$

And from this it's possible to get

$$\mathsf{aliceSK}\times\mathsf{bobSK}\bmod q=r^d\bmod q$$

---

With 256-bit and even 384-bit $q$, it's reasonably easy to find $\widetilde{\mathsf{aliceSK}}$ from $\mathsf{aliceSK}$. Thus that technique can also be used after $\mathsf{aliceSK}$ was drawn the standard way.

I have never seen this proposed, but it's so simple that I doubt it's new.

---

¹ Trial and error with $r$ the first primes will find one quickly in an average of two attempts.

² That will hold for common $q$ in ECDSA, which usually is some hundreds bits, and common $n$ for secure Paillier, which usually is in the thousands bits.