Threshold Cryptography IV: Multiplicative-to-Additive (MtA) Protocol and Paillier Encryption Scheme

In our recent post, Threshold Cryptography III, we discussed how the challenge of constructing a threshold variant of ECDSA was addressed in the GG18 [3] through the use of the Multiplicative-to-Additive (MtA) protocol. This MtA protocol is employed in the initial 3 rounds of the 9-round threshold ECDSA protocol implemented in Binance tss-lib [1].

In this post, we provide a detailed examination of the MtA protocol, which utilizes the additively homomorphic properties of the Paillier encryption scheme to facilitate the exchange of encrypted secret shares among the participating parties.

Paillier Encryption Scheme

The Paillier additive homomorphic encryption scheme is employed in the MtA protocol to encrypt and decrypt exchanged secret shares. It supports additive homomorphism over a large modulus (typically of 2048 bits in size), which is substantially larger than the scalar field of the Secp256k1 elliptic curve. Homomorphic encryption is a term that simply means we are able to perform the operations on the encrypted message without requiring decryption, thereby preserving the confidentiality of the original message during computation.

Paillier Key Generation

Generate two large primes $P$ , $Q$ (called safe primes, for example, of 1024 bits), where $P=2p+1$ , $Q=2q+1$ and both $p$ , $q$ are primes. The Paillier public key is $N=P \cdot Q$ (i.e., an RSA modulus) and an additional public value $\Gamma = N+1$ , the private key is the Carmichael function of $N$ , $\lambda(N)=lcm(P-1,Q-1)=2pq$ , where $lcm()$ is the function to compute the least common multiple of two integers.

Encryption

Given a message (plaintext) $m \in \mathbb{Z}_N$ , the encryption $E_N(m)$ of the message $m$ is called a ciphertext $c=\Gamma^m x^N$ $\in \mathbb{Z}_{N^2}$ , where $x$ is a randomly generated integer that is coprime with $N$ .

Decryption

Given a ciphertext $c$ in the multiplicative group $\mathbb{Z}_{N^2}^*$ (elements in $\mathbb{Z}_{N^2}$ that has inverse), the decryption $D_{N^2}(c)$ of $c$ is $\frac{L(c^{\lambda(N)})}{L(\Gamma^{\lambda(N)})}$ mod $N$ , where $L$ is a function defined as $L(u) = \frac{u-1}{N}$ over $u \in \mathbb{Z}_{N^2}$ such that $u=1$ mod $N$ .

Correctness of Encryption and Decryption

Decryption in the Paillier encryption scheme is the inverse of encryption, which means that applying the decryption function $D_{N^2}$ to a ciphertext $c = E_N(m)$ yields the original message: $D_{N^2}(E_N(m))=m.$ Given the Paillier encryption function:

$E_N(m) = \Gamma^m x^N \ \text{mod} \ N^2 = (1+N)^m x^N \ \text{mod} \ N^2.$

, using the binomial expansion of $(1+N)^m$ mod $N^2$ , and eliminating the terms divisible by $N^2$ gives us $(1+N)^m$ mod $N^2$ $=(1+mN+\cdots)$ mod $N^2$ $=1+mN$ , the ciphertext becomes $c =E_N(m) = \Gamma^m x^N$ mod $N^2$ $=(1+mN)x^N$ mod $N^2$ .

For decryption,

$\frac{L(c^{\lambda(N)})}{L(\Gamma^{\lambda(N)})}=\frac{(((1+mN)x^N)^{\lambda(N)}-1)/N}{((1+N)^{\lambda(N)}-1)/N},$

applying the binomial expansion on the numerator and the denominator with modulus $N^2$ , then the numerator is

$\frac{((1+mN)x^N)^{\lambda(N)} \ \text{mod} \ N^2 -1}{N} = \frac{(1+m\lambda(N)N)x^{\lambda(N)N} \ \text{mod} \ N^2-1}{N},$

and the denominator is

$\frac{(1+N)^{\lambda(N)} \ \text{mod} \ N^2-1}{N} = \frac{(1+\lambda(N)N)-1}{N} = \lambda(N).$

By Carmichael's theorems, for any $x \in \mathbb{Z}_N^*$ , it holds that $x^{\lambda(N)}=1$ mod $N$ . Applying this result within the numerator and leveraging the binomial expansion, we obtain $x^{\lambda(N)N}=1$ mod $N^2$ .

As a result, the exponentiated ciphertext $c^{\lambda(N)}$ simplifies such that the numerator in the decryption function becomes $m \lambda(N)$ .

Therefore, the decryption function evaluates as: $\frac{L(c^{\lambda(N)})}{L(\Gamma^{\lambda(N)})} = \frac{m\lambda(N)}{\lambda(N)}=m \ \text{mod} \ N,$ which correctly recovers the original message $m$ .

Additive Homomorphism

The Paillier encryption scheme supports additive homomorphism over the message space $\mathbb{Z}_N$ . Specifically, given any two messages $m_1, m_2 \in \mathbb{Z}_N$ , and two ciphertexts $c_1, c_2 \in \mathbb{Z}_{N^2}^*$ such that $c_1=E_N(m_1)$ , $c_2=E_N(m_2)$ , the Paillier encryption satisfies:

$E_N(m_1+m_2 \ \text{mod} \ N) = E_N(m_1) \cdot E_N(m_2) \ \text{mod} \ N^2$

where the multiplication $\cdot$ is performed in the multiplicative group $\mathbb{Z}_{N^2}^*$ . For two messages $m_1$ and $m_2$ , the ciphertexts are $c_1=E_N(m_1)=\Gamma^{m_1}x_1^N$ mod $N^2$ , $c_2=E_N(m_2)=\Gamma^{m_2}x_2^N$ mod $N^2$ . Then $$E_N(m_1) \cdot E_N(m_2) \ \text{mod} \ N^2=\Gamma^{m_1}x_1^N \Gamma^{m_2}x_2^N \ \text{mod} \ N^2=\Gamma^{m_1+m_2}(x_1x_2)^N \ \text{mod} \ N^2,$$ which is $E_N(m_1+m_2 \ \text{mod} \ N)$ .

MtA Protocol

While the 3-round MtA protocol was briefly introduced in the previous post, we now provide a more detailed description in the context of the Paillier cryptosystem, including the associated range proofs over encrypted secret shares. In addition to the previously defined RSA modulus used in the Paillier encryption scheme, each party $P_i$ is also instantiated with an auxiliary RSA module $\hat{N}_i$ along with two values $h_{1i}$ , $h_{2i}$ in $\mathbb{Z}_{\hat{N}_i}^*$ , which are required for creating range proofs based on commitment schemes.

Assume that each party possesses the Paillier public key and corresponding RSA modulus, with all public parameters securely generated, publicly disclosed, and verified by other parties. The MtA protocol executes between any two parties, typically denoted Alice and Bob. Recall that the goal of MtA protocol is to redistribute the multiplicative shares $a, b$ into additive shares $\alpha, \beta$ such that $a \cdot b = \alpha + \beta \ \text{mod} \ q$ , where $q$ is the scalar field of the Secp256k1 curve.

The following steps are based on the interactive algorithms defined in GG18 [3], where the sender (Prover) and receiver (Verifier) engage in a sequence of message exchanges. In practical implementations, these interactive protocols are typically converted into non-interactive counterparts using the Fiat–Shamir transformation, thereby removing the need for back-and-forth communication while preserving soundness in the random oracle model.

Round 1

The initiator (i.e., Alice) of MtA(MtAwc) protocol performs the following operations.

Encrypts the secret share $a$ with its Paillier public key $A$ using the Paillier encryption scheme.
Creates a range proof of $a$ to prove she knows $a < q^3$ .
Sends the encrypted share $c_A=E_A(a)$ and the range proof of $a$ to Bob via p2p.

Refer to GG18 [3], Page 9:

Code 1

The range proof proceeds as follows on Page 28 of GG18 [3]:

Code 2

Round 2

Upon receiving the encrypted share $c_A$ and the range proof,

Bob verifies the range proof as in the above algorithm.
If the verification succeeds, Bob then randomly generates $\beta' \in \mathbb{Z}_{q^5}$ .
Computes $c_B = (c_A)^b \cdot E_A(\beta') = E_A(ab+\beta')$ (in a different notation) and sets its secret share as $\beta = -\beta'$ mod $q$ .
Creates a Bob proof for MtA to prove $b < q^3$ , $\beta' < q^7$ , or a Bob proof for MtAwc (MtA with check) to prove $b < q^3$ , $\beta' < q^7$ and he also knows $b$ , as shown in the following algorithm.
Sends encrypted share $c_B$ and the Bob proof to Alice via p2p.

Refer to GG18 [3], Page 9:

Code 3

Refer to GG18 [3], Page 31 for range proof in MtA:

Code 4

Refer to GG18 [3], Page 30 for range proof in MtAwc:

Code 5

Round 3

Upon receiving the encrypted share $c_B$ and the Bob proof,

Alice verifies the Bob proof as in the above algorithms.
If the verification succeeds, Alice decrypts $c_B$ to obtain $\alpha'$ with its Paillier private key and sets $\alpha=\alpha'$ mod $q$ as its additive share.

Refer to GG18 [3], Page 9:

Code 6

At the conclusion of the MtA(MtAwc) protocols, Alice and Bob collaboratively converts the multiplicative share $a \cdot b$ into additive shares $\alpha$ and $\beta$ such that:

$a \cdot b = \alpha + \beta \ \text{mod} \ q$ where:

$\alpha \in \mathbb{Z}_q$ is known only to Alice;
$\beta \in \mathbb{Z}_q$ is known only to Bob;
and $q$ is the scalar field of the Secp256k1 curve.

The resulting additive sharing ensures that neither party learns the value of $a \cdot b$ directly, preserving the secrecy of their respective inputs.

Conclusion

This post reviewed the MtA(MtAwc) protocols instantiated using the Paillier additively homomorphic encryption scheme, under the assumption that all participants possess securely generated, publicly known, and mutually verified Paillier public keys and RSA modulus. The verification of these parameters is a non-trivial task, requiring a series of zero-knowledge proofs to ensure their correctness and compliance with cryptographic security requirements. The details of these verification procedures will be discussed in the next post.