Partnered With:

Vishen proposes a new key sharing scheme for brain wallet and social recovery design applications

Read this article in 8 Minutes

Vishen describes a new M-of-N key sharing scheme, and puts forward two application cases of brain wallet and social recovery design.

M-of-n secret sharing with pre-known shares

Originally written by Vitalik Buterin

Last night's porridge, Babbitt

In this article, Vitalik Buterin, co-founder of Ethereum, describes a new M-of-N key sharing scheme, and presents two application cases for brain wallet and social recovery design.

Suppose you want to generate a secret S, and S can be recovered by putting together M of N key shares, all of which are known in advance. There are two use cases for this scenario:

1. A brain wallet where N key sharing is the answer to N security questions and you hope to recover funds with answers to only M security questions (security questions alone would be bad, but if you combine 20 security questions, you can get quite a bit of entropy);

2. A social recovery design where you want to use threshold decryption rather than a smart contract wallet because you are trying to recover access to private data rather than cryptocurrency, and you want your recovery partners to be able to use keys they already have (to reduce the risk of losing those keys);

The ordinary M-of-N key sharing scheme does not apply to any of these use cases, because it only allows for the pre-selection of M key shares, and the remaining (n-m) key shares must be generated from the original M using a deterministic algorithm and look like random data (in the case of the brain wallet, They are not suitable as the answer to security questions, and in the case of social recovery require users to use special software to store them, rather than deriving them from an existing HD wallet).

So this is what we want to improve. We develop a N-of-(2n-m) threshold scheme to generate (n-m) additional key shares from the original N key shares. Then we publish all n-m additional key shares on the blockchain. If needed, in the case of social recovery, one could simply give each participant a copy of all additional key shares. This causes additional key sharing to become effectively public information: the risk of their loss is negligible, but any attacker will have them. And it turns out that out of the unpublished N key shares, as long as there are M key shares combined with n-m additional key shares that reveal the data, we have an m-of-n scheme, which is exactly what we want.

July 18, 2021 Update: Alternative mechanism for the social recovery use case

In the social recovery use case, we want the setup process to be as simple as possible, because users have a lazy tendency and will inevitably choose a small, insecure set of recovery partners if setup is difficult. This means that generating the distributed key generation (DKG) required for key sharing in a decentralized manner may be a bad idea, as it requires 2 rounds of communication (which means additional blockchain transactions or everyone online at the same time and having a synchronous communication channel).

Instead, we can take advantage of the fact that account holders themselves own their private keys. They can simply ask each recovery partner for their public key (for example, through pk = G * hash(ecdsa_sign(MSK, nonce)), where MSK is the recovery partner's main key), and then publish a transaction on the chain that includes nonce, Each I is encrypted (share_i, pk_i) (Note: where share_i is the ith key share and pk_i is the public key of the ith participant).

If we avoid reusing the nonce random number and therefore do not reuse the key (e.g., setting nonce = hash(secret, maddr_1... Maddr_n), where secret is the value to put in the recovery, and maddr_i is the address of the ith recovery partner, which should be sufficient), we can encrypt it using the basic Diffie-Hellman encryption algorithm, This means that a single transaction with only 32 * (n+1) bytes of callData data is sufficient to hold recovery information.

Kelvin, a member of the Ethresear.ch forum, commented on the proposal:

"That's interesting! My guess is that in a social recovery design, N participants append some public salt to their private key (by inserting a specific string at any fixed position in the password) and then hash it to generate N pre-known key shares.

Otherwise they would not want to disclose their own key sharing in order for the n-m additional key shares to be counted, and they would have to disclose M keys to restore the secret.

Also, what types of personal data do you think people distribute in this way?"

Vitalik replied:

"In fact, they will use the hash(ecdsa_sign(key, salt)) as the hash function to generate the subkey, because the ecdsa_sign method is exposed in the Web3 API and has standardized deterministic output. But this is an implementation detail and the effect is the same.

I'm just thinking about "Ethereum Email" and the encryption keys for decentralized messaging applications like Status. Another use case, of course, is the private keys of other blockchains."