Threshold Cryptography V: Auxiliary Zero-knowledge Proofs

Zero-knowledge proofs (ZKPs) are foundational to the security of the threshold ECDSA in GG18 [3]. They allow each participant to demonstrate knowledge of secret values, such as private key shares or random factors with range, without disclosing them to other parties.

In this post, we analyze the specific ZKP constructions implemented in Binance’s tss-lib [1]. These proofs address previously identified weaknesses in the Multiplicative-to-Additive (MtA) protocol, Paillier encryption parameters, and auxiliary RSA modulus generation. Our discussion is grounded in the improvements formalized by the specifications in CGGMP21 [4], which strengthen the robustness of threshold ECDSA against known attacks.

Sigma Protocol

The auxiliary zero-knowledge proofs in threshold ECDSA are based on a standard sigma protocol (aka, $\Sigma$-protocol), a three-round interactive proof system for proving the knowledge of a secret without revealing it. It involves the following three steps:

Commitment: The prover sends a commitment computed using randomness and public input.
Challenge: The verifier issues a random challenge $c$ , typically derived via the Fiat–Shamir transformation using prior messages and public inputs to convert the interactive system into a non-interactive one.
Response: The prover replies with a value $z$ that encodes the secret and the challenge.

The verifier then checks a predefined relation over the commitment, challenge, and response to verify knowledge of the secret.

Range Proofs in MtA Protocol

In our recent post, Threshold Cryptography IV, we discussed how the Multiplicative-to-Additive (MtA) protocol incorporates range proofs constructed using the sigma protocol. These range proofs are critical to ensuring that encrypted secret shares are well-formed and lie within the expected domain. Without them, an adversary could craft malformed ciphertexts that subvert the security assumptions of the protocol. In fact, the absence of range proofs has been directly linked to real-world vulnerabilities, as demonstrated in Attacking Threshold Wallets, A Note on the Security of GG18, and further explored in Alpha-Rays: Key Extraction Attacks on Threshold ECDSA Implementations.

Schnorr Proof

Schnorr proof is a special case of the sigma protocol that is intended to prove knowledge of the discrete logarithm, for example, on elliptic curves.

Public: A generator $g \in G$ of large prime order $q$ , and a point $h \in G$ .
Secret: The prover knows a secret $x$ with $h=x \bullet g$ , that is, knows the discrete log with respect to the point $h$ .

The protocol operates in three rounds, as illustrated in the sigma protocol:

Commitment: The prover samples random $r \in \mathbb{Z}_q^*$ , computes the commitment $\alpha = r \bullet g$ and sends it to the verifier.
Challenge: The verifier validates $h$ and $\alpha$ , then sends random $c = H(q, g, \alpha , h) \in \mathbb{Z}_q$ , where $H$ is a cryptographic hash function that serves as Fiat-Shamir transformation.
Response: The prover computes $z = r + c \cdot x$ mod $q$ .

Verifier checks that $z \bullet g = \alpha + c \bullet h$ . If the equation holds, the verifier is convinced the prover knows the secret $x$ without learning it. Schnorr proofs are widely used in the threshold ECDSA to prove one party knows a secret without revealing it to others.

Paillier Proof

As part of the distributed key generation in GG18 [3], each party must generate a Paillier public key $N$ that is square-free, that is, there is no prime number $p$ such that $p^2$ divides $N$ . Ensuring this property is critical, since a non-square-free modulus could undermine the semantic security guarantees of the encryption scheme. To enforce correctness, each party produces a Paillier proof that certifies the validity of its modulus to all other participants. The tss-lib [1] implementation adopts the construction from GRSB19 [5], which refines earlier techniques introduced in GMR98 [6].

Refer to GG18 [3], Page 10:

Proof 1

Refer to GRSB19 [5], Page 6, 7:

Proof 2

Mod Proof

In later refinements of threshold ECDSA, the Paillier modulus $N$ is required not only to be square-free but to satisfy the stronger condition of being a Paillier–Blum modulus. This property is enforced via the mod proof, a zero-knowledge proof that certifies correct parameter generation. Specifically, the proof demonstrates that the prover knows a factorization $N = p \cdot q$ such that $p=3$ mod 4, $q=3$ mod 4. At the same time, the construction guarantees that $N$ is coprime with its Euler totient $\phi(N)$ , which implies that $N$ is square-free. By requiring this structure, the Mod proof strengthens the hardness assumptions underlying Paillier encryption and mitigates attacks stemming from weak or malformed moduli.

Refer to CGGMP21 [4], Page 31:

Proof 3

Factor Proof

In response to the vulnerabilities highlighted in Practical Key-Extraction Attacks in Leading MPC Wallets, tss-lib [1] adopts the small-factor proof to harden the security of the Paillier modulus. The proof ensures that the prover’s secret prime factors $p,q$ of the RSA modulus are not only unknown to other parties but also bounded within a range relative to $\sqrt{N}$. By leveraging sigma protocol techniques with commitment parameters, the proof convinces verifiers that $p$ and $q$ are well-formed without disclosing them, thereby eliminating attack vectors that exploit improperly generated or undersized/oversized factors.

Refer to CGGMP21 [4], Page 60:

Proof 4

DLN Proof

DLN proof is a zero-knowledge proof that ensures the correct generation of Pedersen parameters $(N, s, t)$ such that $s, t \in N^*$ by requiring the prover to demonstrate knowledge of an exponent $\lambda$ such that $s = t^\lambda$ mod $N$ . This guarantees that the parameters are properly linked and prevents adversaries from injecting malformed or trapdoored values, which could otherwise lead to key extraction attacks. Missing or incorrectly implemented DLN proofs, as highlighted in New Key Extraction Attacks on Threshold ECDSA Implementations, have been shown to open the door to practical exploits. By enforcing well-formed Pedersen commitments, the DLN proof enhances the trustworthiness of the auxiliary setup in threshold ECDSA and reduces the attack surface, resulting from improperly generated public parameters.

Refer to CGGMP21 [4], Page 32:

Proof 5

Conclusion

This post wraps up our series on threshold cryptography, where we explored the auxiliary zero-knowledge proofs in GG18 [3] and their implementation in Binance’s tss-lib [1]. These proofs are essential for realizing the MtA protocol and Paillier encryption scheme, providing assurance in parameter correctness and secure message authentication in threshold ECDSA.

At CertiK, our cryptography team is actively engaged in research and development across applied cryptography, including threshold cryptography, zero-knowledge proofs, and post-quantum cryptography schemes. If your project requires a security review in any of these areas, we’d be glad to connect. From threshold cryptography to post-quantum security, CertiK helps you Elevate Your Web3 Journey.