Have you ever wondered why Threshold ECDSA is painful, Threshold Schnorr is straightforward, and Threshold BLS is trivial? Here's an informal explanation:
Everything comes down to the complexity of the signing equation for each scheme.
All secrets in all schemes are typically distributed across users using Shamir's secret sharing techniques. en.wikipedia.org/wiki/Shamir%27…
Threshold ECDSA sign equation involves multiplication of two secrets (k^{-1} and x, where x is the secret).
s = k^{-1} * (Hash(v) + r * x)
This is not straightforward!
The fight with "multiplication" gates dates back to the original papers on MPC from '87-88 [see Completeness Theorems for Non-Cryptographic Fault-Tolerant Distributed Computation by Ben-Or, Goldwasser, and Wigderson' 88; "The multiplication step is only a bit harder." :).]
If you have two shares distributed following Shamir's secret sharing protocol, then multiplying them results in a polynomial of a larger degree. So if you want to preserve your threshold/participants parameters, you need to do a "degree reduction" one way or another.
Hence, you must fall back to some good old MPC techniques for this.
On the other hand, the Schnorr signatures are simpler:
s = k - x * Hash(v).
Note that you only need to multiply a distributed secret (x) by a !public value, Hash(v), which is significantly easier. [Additions usually come "for free" in all settings]
Finally, the BLS signature equation is trivial: H(m)^x.
The complexity and the security of the scheme are reduced to pairings. Aggregating distributed shares then follows the basic linearity over the group.
That's it! If everyone supported BLS signatures, our lives would be so much simpler today! 🚀😀
• • •
Missing some Tweet in this thread? You can try to
force a refresh
On a high level, an encryption scheme is homomorphic if one can perform field operations over the encrypted messages, E(a) and E(b), that result in simple base operations over the underlying encrypted values.