Working with Paillier and ECDSA - Order issue

sm flag

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.

kelalaka avatar
in flag
Hash before sign?
ng flag

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.


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.