2 ms·
Do you have M friends, of which you're certain at most N-1 would collaborate to steal from you and/or get hacked? In that case, you can do secure password reco
by KMag 9y ago
Do you have M friends, of which you're certain at most N-1 would collaborate to steal from you and/or get hacked? In that case, you can do secure password recovery.
Shamir's secret sharing algorithm can be applied over many groups other than GF(2^N). In particular, you can generate a polynomial of degree N where F(0) is your ECDSA private key, and for 1 < x < M, tell trusted party number x that they're party x and F(x) = y. Cooperation/collusion among any N of the M parties is sufficient to reconstruct the polynomial and calculate F(0). However, N-1 collaborators learn nothing about F(0), as long as you've generated all of your coefficients randomly and uniformly over the size of the subgroup generated by your elliptic curve's generator.
You can even have N parties each generate their own secret random polynomial f of degree N, and publicly share f(0)*G and privately share f(x) with party x. You add up all of the publicly shared elliptic curve points to get a public key for which no one party knows the secret key. Each party remembers the sum of the f(x) secrets they've been told. For polynomials, f(x) + g(x) + h(x) = (g+g+h)(x), so any N of the participants can collaborate to calculate the previously unknown polynomial for which f(0) is the private key. You need to first share Pedersen commitments of the public f(0)G values, perform a sanity check on those, and then reveal the f(0)G values and perform some more sanity checks in order to rule out cheating. See https://duckduckgo.com/?q=gennaro+distributed+key+generation https://duckduckgo.com/?q=gennaro+distributed+key+generation
Once you have your public key for which nobody knows the private key, you can perform the same procedure to generate the random R value of the (R,S) pair of a Schnorr signature. Each party can then perform a Schnorr signature on H using their secret share of R and their secret share of the public key. They each reveal their signatures, and any N of those signatures can be used to reconstruct a polynomial where F(0) is the S value in the (R,S) signature on H. At the end, all of the sub-signatures and the final signature can be made public without anyone learning anything about the secret values. This is called a threshold signature scheme. (There are other threshold signature schemes. I had to implement threshold RSA in Rivest's 6.857 class.)
Unfortunately, ECDSA isn't a Schnorr signature scheme, but Ed25519 is. Any coin built using Schnorr signatures for wallets would allow you to construct threshold wallets where any N of M parties can collaborate to spend from the wallet, but generating transactions doesn't leak information to anyone about how to generate transactions alone.
- KMag 9y agoI should add that with Schnorr signatures, if you have a bunch of signatures on the same H, you can add up all of the (R,S) pairs of signatures, and the result is a single signature where the public key is the sum of all of the public keys of the N signers. This allows very compact storage and verification of multi-party signatures. All of these nice properties are just consequences of the linear composability of Schnorr signatures. BitCoin, at present, only supports ECDSA signatures, which aren't linearly composable.