How multiple parties can jointly sign messages without any single party knowing the private key — and why that's much harder than it sounds.
A digital signature scheme lets you prove authorship of a message using a mathematical key pair. ECDSA — the Elliptic Curve Digital Signature Algorithm — underpins Bitcoin, Ethereum, TLS, and most of the modern security stack.
Pick a special point g on an elliptic curve. g will be publicly known. Your private key is a random scalar x.
Your public key is computed by "adding g to itself x times":
The nonce is sacred. Using the same γ twice, or leaking it even partially, allows full recovery of the private key x.
The PlayStation 3 private key was broken exactly this way in 2010.
The bottleneck is the term γ⁻¹ · (m + r·x). It involves the product of two secret values — the nonce and the key.
Multiplying things that are secretly distributed across parties requires heavy machinery.
Compare with Schnorr signatures, where the analogous computation is just γ + c·x — linear, trivially distributable.
A threshold signature distributes the private key x across n parties so that no single party holds it.
Any attempt to sign requires all parties to cooperate — yet at the end, only a standard ECDSA signature emerges, verifiable by anyone.
To compute σ = γ⁻¹ · (m + r·x) without reconstructing either γ or x,
parties need to evaluate the product of their shares. This is an inherently nonlinear operation on secret data.
The MtA problem. Party Pᵢ holds aᵢ, party Pⱼ holds bⱼ.
They want additive shares of aᵢ · bⱼ — without either learning the other's value.
This is the "Multiplicative-to-Additive" share conversion, and it's the cryptographic heart of the protocol.
The protocol runs in three rounds of communication. Each round, parties broadcast messages to all others. Click through the steps below.
Each party independently samples two local random values and encrypts them using their own Paillier key:
The Paillier ciphertexts act as commitments — binding and hiding. Parties are committing to their nonce shares before seeing others' values, preventing cheating.
This is where the magic happens. For every pair (Pᵢ , Pⱼ), we need additive shares of the cross-products
γⱼ · kᵢ and xⱼ · kᵢ — without either party learning the other's secrets.
The same procedure runs in parallel for xⱼ · kᵢ, giving shares α̂ᵢ,ⱼ and β̂ⱼ,ᵢ. Also, each party broadcasts Γᵢ = g^γᵢ.
Key innovation of this paper. Rather than just sending Paillier ciphertexts, parties also attach zero-knowledge proofs that the values inside the ciphertexts are well-formed and in range. This prevents malicious deviations without adding extra rounds.
Each party combines all the cross-product shares they received to compute local shares of γ·k and x·k:
Once all shares are collected, any party can reconstruct the signature:
The output (r, σ) is a perfectly standard ECDSA signature. Any third party can verify it with the standard ECDSA algorithm — they don't need to know it was produced by multiple parties.
Throughout the protocol, what does each party actually see?
The key insight: information about the secret key x only enters the output in round 3,
and by that point, it's indistinguishable from the signature itself — which is already public.
The entire MtA protocol rests on one special property of Paillier encryption: you can perform arithmetic on encrypted values without decrypting them. This is called homomorphic encryption.
The scalar multiplication uses only the public key of Pᵢ — Pⱼ can compute
enc_i(γⱼ · kᵢ − βⱼ,ᵢ) without ever knowing kᵢ.
Only Pᵢ can decrypt the result.
Paillier encryption is hiding but not automatically binding to any specific range. A malicious party could encrypt a value far outside the expected range and corrupt the protocol. The paper accompanies every Paillier operation with a Non-Interactive Zero-Knowledge proof (NIZK) that:
The key insight. Previous protocols (like GG18) verified correctness after the computation, requiring 6 extra rounds. This protocol embeds ZK proofs inline — achieving the same security in zero extra rounds.
What sets this protocol apart from earlier threshold ECDSA work is the combination of properties achieved simultaneously.
Rounds 1–2 run before the message is known ("presigning"). Once the message arrives, each party computes one field element and sends it. No interaction required.
Parties periodically run a key refresh. Security holds epoch-by-epoch: even if every party is compromised at some point, signatures remain safe as long as one party is honest per epoch.
If signature generation fails — due to a malicious party — the honest parties can identify and expel the culprit. Essential for real-world deployments.
Full UC security: the protocol remains secure when deployed as a component inside a larger system, with concurrent sessions and an adaptive adversary.
Secure against n−1 corrupted parties out of n. The strongest possible threshold — only one honest party is needed.
The output is a normal ECDSA signature. Verifiers need no special software — Bitcoin nodes, TLS clients, everyone just runs standard ECDSA verification.