time-delayed social recovery scheme

[conduition]

Carrying this out of the email thread:

we could allow a group of recoverers to cooperate remotely and sign a challenge (not necessarily with threshold signatures, but that is an option). Once enough members of the group have signed this challenge, assuming the group is large enough, then a time-delay can start on the SOS backend. This would give recoverers time to book flights and schedule a meeting where they can physically gather their shares and finish recovering the SOS vault(s).

Requirements:

• Recoverers can start the time delay remotely, if the threshold is met
• Recovery package is distributed (method TBD) once the time delay is met
• Account owner can abort the recovery and issue new shares if an illegitimate recovery is attempted

[conduition]

@tmpfs You mentioned this:

However, when I think of schemes not using threshold signatures then the backend SOS server would need to know the threshold required to start the recovery process which we should avoid for obvious reasons!

Could you elaborate? It sounds like you're implying that the secret sharing threshold should be considered private enough that the backend server isn't allowed to store it?

[tmpfs]

@tmpfs You mentioned this:

However, when I think of schemes not using threshold signatures then the backend SOS server would need to know the threshold required to start the recovery process which we should avoid for obvious reasons!

Could you elaborate? It sounds like you're implying that the secret sharing threshold should be considered private enough that the backend server isn't allowed to store it?

I would prefer it if the server has no knowledge of the threshold as otherwise we would have the ability to adjust it, whilst it's not a severe problem I think it's worth avoiding if possible.

As a general design principle I am trying to give the server the least amount of authority and knowledge of accounts as possible.

Tangential, I had in mind that in order to create a social recovery group all the other participants would need to have installed SOS, this was because I envisaged us using threshold signatures which would require all participants to have p2p connections. I wonder what you think about this requirement?

[tmpfs]

When I weigh up the pros and cons of threshold signatures I think we should avoid them for this use case. Storing the threshold on the server is not really an issue as the server is responsible for triggering the release process anyhow.

Pros

• Cryptographically secure threshold consensus

Cons

• DKG can be slow for some protocols (will affect recovery group UX)
• Requires all participants to be online at the same time for DKG and signing
• Complex networking requirements
• Increases data that needs to be stored for a recovery share (two key shares)

I wonder whether a simple solution which just uses the account identity signing key to identify recovery group participants is enough. The server then just needs to know the addresses of the recovery group participants and the threshold required to start the recovery process.

In particular, I like that this would not require all the recovery group participants to be online at the same time during recovery group creation and triggering recovery.

[conduition]

When I weigh up the pros and cons of threshold signatures I think we should avoid them for this use case. Storing the threshold on the server is not really an issue as the server is responsible for triggering the release process anyhow.

i'm in the same boat there. Compared to simply storing the recovery threshold on the server, the costs of implementing a threshold signature scheme just aren't worth it. Besides, the real security of the vault is derived from the end-to-end-encryption of the recovery package. Even in the most extreme scenario where the SoS server is ransacked, with all the encrypted vaults exposed lastpass-style, attackers would also need to phish or steal secret recovery shares from customers in order to decrypt those vaults.

Tangential, I had in mind that in order to create a social recovery group all the other participants would need to have installed SOS, this was because I envisaged us using threshold signatures which would require all participants to have p2p connections. I wonder what you think about this requirement?

I think creating the recovery group should be possible without the shareholders needing to installing any software. Shares can just be SLIP-39-style mnemonics written on paper, or digital files on USB drives. The SoS server doesn't need to know how many shares were issued - only the threshold, and how to verify each share. Here's how I'd do it:

Share Distribution

1. The customer (the person paying for SoS and setting this all up) asks SoS to create a recovery group for their vault. They input two parameters, $t$ and $n$. $t$ is the threshold of shares needed to recover the vault, and $n$ is the number of shares initially issued to the group.
2. The SoS app generates a random encryption key $k$. This key will be shared among the social recovery group.
   • Let $m$ be the master key which decrypts the customer's vault.
   • The SoS app encrypts $m$ as a message, under encryption key $k$, to produce an encrypted master key $\hat{m}_k$. ¹ You could do this by simply XORing $m$ and $k$.
3. SoS app executes Feldman's Verifiable Secret Sharing (VSS) protocol to share the group key $k$ (which can decrypt $\hat{m}_k$).
   • This outputs $n$ shares $\{s_1, s_2, ... s_n\}$, as well as the public polynomial commitment which I'll call $P(x)$, which can be used to compute $P(i) = s_i G$ (i.e. the public key for any secret share $i$).
4. The SoS app uploads the polynomial $P(x)$², and the encrypted master key $\hat{m}_k$ to the SoS backend server.
   • The SoS backend server can infer the threshold $t$ by counting the number of coefficients in $P(x)$.
5. The customer prints/writes/copies the $n$ shares and distributes them by paper/email/USB/etc to their trusted recovery aides.
   • Each share should embed its index $i$, and an identifier to quickly identify shares belonging to different groups. Possibly other data could be embedded, TBD.

Recovery

At the recovery stage, then absolutely the shareholders will need to install or run specialized software to trigger the recovery countdown, and eventually decrypt and access the recovered vault.

1. A shareholder installs SoS. They click a button such as "Start social recovery".
2. The shareholder inputs their share $s_i$ into the SoS app, along with:
   • A vault identifier $v$ (possibly embedded in the share) telling the server which vault they are trying to recover, and which recovery group they are part of.
   • A destination $d$ for the encrypted recovery package, e.g. an email address, or an SoS account username.
3. The SoS app talks to the SoS backend and says "I'd like to recover vault $v$ please. I am shareholder $i$. Please send the recovery package to destination $d$."
   • The client attaches a signature on $d$ and the current time, using the share $s_i$ as a signing key.
4. The SoS backend server verifies the signature against the public key $P(i) = s_i G$ for that recovery group. If the signature is valid, then the backend knows the client holds share $s_i$ and is trying to trigger recovery to destination $d$.
   • At this point, the SoS backend should send notifications to the customer who owns the vault, offering them an emergency abort button in case the recovery is malicious.
5. If at least $t$ shareholders in the group provide valid signatures on the same destination $d$ within some fixed time period, e.g. 24 hours, then the backend starts the countdown. At the end of the countdown, the recovery package, which includes the encrypted vault, and encrypted master key $\hat{m}_k$, is dispatched to destination $d$.
6. A client receives the recovery package (either by email or some other push mechanism).
7. Some set of shares $\{s_1, s_2, ... s_t\}$ ³ are brought together to an SoS client on the trusted recovery machine.
8. The client uses the shares to recover $k$, and then uses $k$ to decrypt $\hat{m}_k \rightarrow m$, and then uses $m$ to decrypt the vault.

Advantages

• The backend server never learns how many shares were issued or to whom. It only learns the threshold $t$, and how to identify valid shares with $P(x)$.
• Vaults can have multiple recovery groups with different $(t, n)$ setups, different timeouts, etc.
• The customer's SoS app could store the SSS secret coefficients in the vault itself, allowing them to recover or issue shares for any recovery group.
• Whole recovery groups can be instantly revoked by the vault owner at any time by simply deleting $P(x)$ from the server.
• Individual shares within a recovery group can be cryptographically revoked such that they can't be used for recovery or decryption, by using the SSS secret coefficients to carefully tweak $\hat{m}_k$, (cool math down this road). Actually, i think this might only be possible with an $n$-of-$n$ threshold.

Limitations

• Distribution of the vault recovery package is trustful. I'm assuming that there is some trusted executor who is responsible for receiving and decrypting the vault without running off into the sunset.
• We'll probably have to embed a lot of data into the shares, so they may become rather long if we encode them as mnemonic phrases a la SLIP39.

Footnotes

1. Why not simply use VSS to share the vault master key m itself? Because the customer might want to revoke the recovery group later, which is easier and safer if the vault's master key doesn't need to be changed as a result. This configuration allows multiple independent recovery groups to coexist for the same vault, too. ↩

2. Why upload the public polynomial to the backend, instead of its evaluations? Because this way the server only learns the threshold, and not the number of shares issued. Since the threshold is always smaller, it means the server needs to store less data. It also means the client can issue new shares without talking to the server at all. ↩

3. The shares used to decrypt the recovery package do not necessarily need to be the same shares used to initiate the recovery countdown, because any valid set of t or more shares are functionally equivalent to one-another. ↩

[conduition]

I wonder whether a simple solution which just uses the account identity signing key to identify recovery group participants is enough. The server then just needs to know the addresses of the recovery group participants and the threshold required to start the recovery process.

If we wanted we could extend the recovery process to integrate more tightly with SoS itself. Instead of shares saved on paper, the share could be saved automatically in encrypted form on the server, such that only the correct shareholders can access and decrypt them. But for the sake of accessibility we definitely need to support fully offline shares.

[tmpfs]

@conduition , this is great, thank you.

Some minor nitpicks and a few higher level comments afterwards.

In Share Distribution (2):

Let m be the master key which decrypts the customer's vault.

I think this should read let m be the master key which decrypts the customer's recovery pack.

A recovery pack is just a mapping of vault identifiers to (automatically generated) diceware passphrases (see DelgatedPassphrase) and this is the final artifact that will be decrypted during recovery. Combining the decrypted recovery pack with the data of the respective vaults is the end game of recovery.

In Recovery (2) I think the identifier sent will be the account identifier (just an Ethereum style address) as they are recovering an account but restricted only to the folders that the account owner chose when they created the recovery pack/group.

Note that here I think the server will need to know the vault identifiers that exist in the recovery pack before encryption to release only the vaults that the account owner has explicitly granted recovery rights to.

I should really write an overview of the architecture and terminology so that the language is clear for the terms I have used. Will get to that soon!

Distribution of the vault recovery package is trustful. I'm assuming that there is some trusted executor who is responsible for receiving and decrypting the vault without running off into the sunset.

That is right, I always imagined that a single trusted person is the executor, so we would need to store that information too I think and either a) only allow the executor to start/complete the recovery process or if possible b) let anyone start the recovery process but only allow the executor to complete recovery.

We might also want to allow multiple executors with a priority weighting in case an executor is dead or otherwise unavailable.

---

I really like your direction of allowing recovery group/pack creation without the app installed by the other parties.

But I do wonder if it will affect the UX of the recovery group creation flow, for example, if everyone had the app installed we could make recovery share distribution seamless (E2EE encrypted delivery of the key shares).

I am torn on this one, need to consider it some more and maybe see what the the UX is like with the flow you describe, for example, participants are going to need to know who the other participants are (including contact details) in order for them to sign to trigger recovery. I assume this is fine but it's quite a lot of effort on the part of the person creating the recovery pack to get this right and I really want this to be very, very easy to use so it appeals to everybody.

I thought by having everyone use the app a lot of the legwork of these notifications/participant co-ordination could be handled in-app.

If we wanted we could extend the recovery process to integrate more tightly with SoS itself. Instead of shares saved on paper, the share could be saved automatically in encrypted form on the server, such that only the correct shareholders can access and decrypt them. But for the sake of accessibility we definitely need to support fully offline shares.

Yes, now I re-read this I think we need to support both flows. Let's start with the fully offline use case you describe and then later enhance with an improved UX where possible.

On your footnotes, I think we have 1) already covered due to using a recovery pack which is independent of the account master password and 2) is very cool - so if a recovery participant dies the owner could just issue a new share to somebody else - is that right?

And footnote 3) is interesting, are there any benefits from separating the share encryption and signing keys?

Really very excited to have you working on this, what's the next step, should we write a specification or would you prefer to get stuck in to a draft PR?

[conduition]

I should really write an overview of the architecture and terminology so that the language is clear for the terms I have used. Will get to that soon!

I agree, I think I need to know the difference between "Folders", "Accounts", and "Vaults" before I get too carried away here.

but restricted only to the folders that the account owner chose when they created the recovery pack/group.

Ah, so the account owner can dictate which parts of their Account are recoverable through the social recovery process? That might merit some more careful consideration. These "folders" will need to be encrypted separately from one-another, so that an account owner can change each folder's encryption key independently, to scope the access of the recoverers as they prefer.

participants are going to need to know who the other participants are (including contact details) in order for them to sign to trigger recovery.

Idea for this:

• The account owner can upload contact details for all their shareholders, encrypted under a key with a 1-of-$n$ access structure.
• The shareholder contact details can be an encrypted blob with a padded length, so that the actual count of shareholders is kept secret until recovery time.
• When any one of the recovery shareholders submits a recovery request and signature, they can supply a special public share derived from their secret share which lets the SoS server decrypt the contact info for all shareholders.
• The SoS server can then send notifications to shareholders via email/SMS or whatever, informing them that somebody in their recovery group initiated the recovery process for the account owned by such-and-such.

i made a simple protocol which enables this access structure without adding any extra data to the recovery shares. Happy to share if you're interested.

That is right, I always imagined that a single trusted person is the executor, so we would need to store that information too I think and either a) only allow the executor to start/complete the recovery process or if possible b) let anyone start the recovery process but only allow the executor to complete recovery.

All sounds good to me. This can also be enforced cryptographically using sharded secret sharing groups, so that one specific share (the executor's share) is mandatory to recovery the vault, plus some threshold of less-trusted shares. You could allow more than one "executor share" as well, although there is no concept of 'fallback', so that part would need to be enforced server-side.

if a recovery participant dies the owner could just issue a new share to somebody else - is that right?

Exactly correct.

are there any benefits from separating the share encryption and signing keys?

Sorry, I think was vague in that footnote. let me clarify with an example.

Picture a 2-of-3 recovery group, Alice, Bob, & Carol. Alice and Bob cooperate to initiate the recovery countdown, but then Alice disappears. At the end of the recovery countdown when Bob receives the encrypted vault, he and Carol can decrypt it together. Alice was the shareholder who originally helped start the countdown, not Carol, but Alice and Carol's shares are functionally equivalent when it comes time to decrypt the recovered vault.

Really very excited to have you working on this, what's the next step, should we write a specification or would you prefer to get stuck in to a draft PR?

Same here! I think a high-level design document would be the next concrete step, listing requirements and describing the architecture. But before I get into that, i'd like to take some time to get my build environment set up and explore the frontend/backend source code repos for a while.

[tmpfs]

@conduition, I have had a go at this in the overview. Please let me know if the language can be improved or anything is not clear.

Later I intend to document the binary file formats in great detail but for now want to keep focused on the sync logic.

Ah, so the account owner can dictate which parts of their Account are recoverable through the social recovery process? That might merit some more careful consideration. These "folders" will need to be encrypted separately from one-another, so that an account owner can change each folder's encryption key independently, to scope the access of the recoverers as they prefer.

Let's say for now the executor can recover all the folders that the owner has granted the recovery group access to? Which means that we can encrypt the recovery pack (as opposed to a single password) and your protocol continues to work as intended. I think the scope is implicit as the owner chooses which folders are included in the recovery pack during recovery group/pack creation.

Idea for this:

This is brilliant! I love it :)

i made a simple protocol which enables this access structure without adding any extra data to the recovery shares. Happy to share if you're interested.

Please do 🙏

This can also be enforced cryptographically using sharded secret sharing groups, so that one specific share (the executor's share) is mandatory to recovery the vault, plus some threshold of less-trusted shares.

I like the idea of enforcing the use of the executor's share, however I don't know if it would be possible to change the executor? Without that I think the death of an executor would invalidate the entire recovery (which we should avoid IMO) - is that correct?

Exactly correct.

This is a very important property for the protocol to have, great design 👍

Picture a 2-of-3 recovery group, Alice, Bob, & Carol. Alice and Bob cooperate to initiate the recovery countdown, but then Alice disappears. At the end of the recovery countdown when Bob receives the encrypted vault, he and Carol can decrypt it together. Alice was the shareholder who originally helped start the countdown, not Carol, but Alice and Carol's shares are functionally equivalent when it comes time to decrypt the recovered vault.

I think this is another important property for the protocol to have, we need to ensure that as much as possible (except in very extraordinary circumstances) it is possible to complete the recovery process.

I wonder if once we have a specification we should draw a graph, I think a visualization would really help with my mental model.

[conduition]

I have had a go at this in the overview.

Thanks, that's very helpful. I'm not sure why you're using diceware passwords for decrypting each Vault, instead of just using raw encryption keys, but that's probably out of scope for this issue. let's chat about that on slack.

I think the scope is implicit as the owner chooses which folders are included in the recovery pack during recovery group/pack creation.

All sounds good to me. As long as we allow the owner to update the recovery pack on-demand, they can change the set of recoverable folders however they want.

I like the idea of enforcing the use of the executor's share, however I don't know if it would be possible to change the executor? Without that I think the death of an executor would invalidate the entire recovery (which we should avoid IMO) - is that correct?

If there's only one "executor-share", and the executor disappears at the same time as the owner, then yes, everyone else is hooped unless they can find his share. I think sharding would still be a cool feature regardless as it would allow people to give higher privileges to more trusted friends/family. Maybe not something we need for our PoC but something we can plan for in the future.

[tmpfs]

All sounds good to me. As long as we allow the owner to update the recovery pack on-demand, they can change the set of recoverable folders however they want.

Yep, the owner can store the full recovery key in their identity vault and be able to adjust the folders in the recovery pack, whenever they want, that's a nice touch.

If there's only one "executor-share", and the executor disappears at the same time as the owner, then yes, everyone else is hooped unless they can find his share. I think sharding would still be a cool feature regardless as it would allow people to give higher privileges to more trusted friends/family. Maybe not something we need for our PoC but something we can plan for in the future.

I would like to understand more about sharding, can you point me to a resource to learn more about it please?

[conduition]

i made a simple protocol which enables this access structure without adding any extra data to the recovery shares. Happy to share if you're interested.

I have two options for you.

Simple XOR

First the simple approach.

Contact Sharing

1. Let $\{s_1, s_2, ... s_n\}$ denote the secret shares, which here i'll interpret as fixed-length byte arrays.
2. The account owner computes a random contact-sharing encryption key $k$. They use $k$ to encrypt the contact details of their recovery group.
3. For each share index $1 \le i \le n$, the account owner computes the XOR key $c_i = H(i, s_i) \oplus k$, where $\oplus$ denotes byte-wise XOR.
4. (optional) to obfuscate the true number of shareholders, the account owner pads the set $\{c_1, c_2, ... c_n\}$ with extra XOR keys to some length $m > n$.
5. The account owner uploads the set of XOR keys $\{c_1, c_2, ... c_m\}$ and the encrypted contact info to the SoS backend server.

Contact Recovery

6. A shareholder at index $i$ initiates recovery. She sends $(i, H(i, s_i))$ to the SoS backend server along with a signature to authenticate herself.
7. The server looks up $c_i$, and can now compute the contact encryption key $k = c_i \oplus H(i, s_i)$.
8. The server uses $k$ to decrypt the recovery group contact details.

Explanation

Each shareholder can derive a key $H(i, s_i)$ which only she and the account owner can compute. By XORing $H(i, s_i)$ with the contact encryption key $k$, we can produce individual XOR keys $\{c_1, c_2, ... c_n\}$ which are useless to the server until provided with $H(i, s_i)$. Assuming $H$ is preimage resistant, the server cannot compute $s_i$.

Benefits

Very easy to implement. Very easy to describe in documentation. Secure as long as the hash function $H$ is preimage resistant.

Drawbacks

We have to pad the number of XOR keyswhich the account owner uploads, wasting storage space on the server-side, and revealing an upper-limit on how many shareholders could be in the recovery group.

If we do not pad the XOR key set, then we have to be OK with the server knowing how many shareholders are in the recovery group, even before anyone initiates recovery.

If the account owner issues a new share for which the server doesn't know $c_i$, then the account owner must push $c_i$ to the backend server.

ECC approach

And now, a much more convoluted but slightly more efficient and private approach.

Let's review some shamir-secret-sharing notation first.

Review of SSS

• We define $s_0$ as the encryption key used to decrypt the recovery pack. This is what we're sharing to the recovery group.
• Let $f(x)$ be the secret sharing polynomial of degree $t-1$ with constant term $s_0$, and $t-1$ random scalar coefficients $\{a_1, a_2, ... a_{t-1}\}$.
  • More precisely, $f(x) = s_0 + a_1 x + a_2 x^2 + ... + a_{t-1} x^{t-1}$
  • The constant term of $f(x)$ is $s_0$, which implies $f(0) = s_0$.
• Let $\{s_1, s_2, ... s_n\}$ be the secret recovery shares of $s_0$. These shares are the evaluations of $f(x)$, so that for any share index $i$ we have $f(i) = s_i$.
• $f(x)$ has degree $t - 1$, so a recovery group knowing any $t$ or more shares can interpolate any $f(x)$ evaluation, including the recovery pack encryption key $s_0$.
• The share verification polynomial is computed as $F(x) = f(x) \cdot G$, where $G$ is the elliptic curve base point. $F(x)$ is what the client uploads to the SoS Backend server to let it correctly identify shares.

All the above is just good ol' fashioned Shamir's Secret Sharing, plus Feldman's verifiable secret sharing.

OK strap in, let's start with the new stuff.

Contact Sharing

1. Fix some elliptic curve point $Q$ which has a provably unknown discrete log (secret key) relative to the curve base point $G$. We could get one of these by, for example, hashing some fixed public message with SHA256, and using the hash as an X-coordinate. This point $Q$ does have a discrete log (secret key) relative to $G$, but neither you, me nor anyone else can compute what it is (without a quantum computer).
2. The SoS client of the account owner knows the original secret sharing polynomial $f(x)$. From $f(x)$, the SoS client derives what i'm going to call the "contact sharing polynomial":
   • $Z(x) = f(x) \cdot Q = s_0 Q + a_1 x Q + a_2 x^2 Q + ... + a_{t-1} x^{t-1} Q$.
   • This is just $f(x)$ but "scaled" by the constant point $Q$, so the degree of $Z(x)$ and the degree of $f(x)$ are the same.
   • The major difference is that $Z(x)$ outputs elliptic curve points, instead of scalars like $f(x)$.

Important facts to keep in mind here:

• Knowing the output of $Z(x)$ does not give you any information about $f(x)$ or $F(X)$ other than polynomial degree. Thanks ECDLP.
• Knowing the output of $F(x)$ similarly reveals nothing about $Z(x)$.
• This is all because the discrete log of $Q$ relative to $G$ is unknown.

Let's continue.

11. The client picks $t-1$ indexes which are reserved and guaranteed not to be used by real shares. For example, we'll probably only use share indexes 0 through 255, so that we only need one byte in the recovery share to store the share index. To be super safe, we can use indexes counting down from the secp256k1 curve order $n$ (kind of like using negative numbers) which are all but certain never to be issued for actual recovery shareholders.
12. For each of these $t-1$ reserved share indexes $n - t \lt j \lt n$, the client computes the curve point $S_j' = Z(j)$.
13. The client computes the hash $k = H(Z(0))$, and uses $k$ as the key to encrypt the shareholder contact details, which is uploaded to the SoS Backend server.

Contact Recovery

14. A shareholder at index $i$ decides to initiate recovery. Alongside the other things we've discussed like the challenge signature, they also upload the point $S_i' = s_i Q$.
15. The server now knows $t$ evaluations of $Z(x)$, and can thus interpolate any $Z(x)$.
16. The server can compute $k = H(Z(0))$ and use $k$ to decrypt the recovery group contact details.

Explanation

The contact sharing polynomial $Z(x)$ which is arithmetically related to $f(x)$ but not to $F(x)$. A shareholder who knows their share $s_i$ can compute $Z(i) = S_i' = s_i Q$, assuming they know the static fixed point $Q$. This point can be a hardcoded constant in the SoS frontend app.

The owner of the account gives the Sos Backend server $t-1$ shares of $Z(x) = f(x) \cdot Q$ ahead of time, at indexes which are guaranteed not to collide with actual shares issued to the recovery group. By giving the server any other share of $Z(x)$, a shareholder will enable the server to recover the full polynomial $Z(x)$ and compute the contact sharing key $k = H(Z(0))$.

The server already has the full polynomial $F(x)$ (which is used to verify shares for the time delay), but because $Q$ has an unknown discrete log relative to $G$, knowing $F(x)$ gives no information about the contact sharing polynomial $Z(x)$ to the server. Equally, because the ECDLP problem is probably hard, the server learns nothing about $f(x)$ by learning the evaluations of $Z(x)$. These properties are important because we don't want the server to be able to decrypt the contact sharing details until at least one shareholder tries to initiate recovery. Shareholders and the server also cannot use $Z(x)$ in an attempt to break the secret sharing threshold through collusion.

Benefits

Unlike simple XOR keys, the main benefit of using ECC is that the server now only needs to store $t-1$ curve points alongside the encrypted contact info. The backend learns nothing new about the secret sharing group, until someone gives it a share of the contact sharing polynomial $Z(x)$. Unless the account owner changes the secret sharing polynomial $f(x)$, there is no need for them to upload new data to the server when issuing new shares.

Drawbacks

Obviously this approach takes more effort to implement correctly than using simple XOR and SHA256, but it's not as hard as you probably expect from the length of this description.

Unlike XOR, this approach is not 'unconditionally secure', but that doesn't really matter because we're already going to be depending on the elliptic curve discrete log problem (ECDLP) hardness assumption by using Feldman's verifiable secret sharing.

Sorry for the two-towers of technical text in there. I wanted to be thorough enough that I could just copy/paste either of these approaches later when we start writing the high level design document for social recovery.

EDIT: just realized i'm a dummy and shouldn't be reusing the key $k$ in the XOR operations, as that is effectively a one-time pad reuse situation. Instead of XOR just use some cipher that maintains security if you encrypt the same message under multiple keys, like AES.

[conduition]

I would like to understand more about sharding, can you point me to a resource to learn more about it please?

Probably the best in-the-wild implementation of SSS is Trezor's SLIP39 spec. Specifically, this section talks about sharding, although the more common terminology is 'groups'. They reference this document for justification.

Sharding works by breaking shares up into smaller shares. For example, you can shard your secret into three groups of shares: family, friends, and colleagues. You might set the groups up such that if any two groups out of the three are in agreement, then they can cooperate to recover the secret. However, you might not trust each of your colleagues as much as your family. Your family group might be a 2-of-4, while your colleagues' shares are a 10-of-12.

There's no theoretical limit on how deep you can go. Shards can be broken into shards which can be broken into more shards. They can be customized to oblivion and back. But to reduce cognitive overhead and complexity it's probably best to limit it to at most two levels of sharding depth, which is what Trezor has done.

[conduition]

I added a draft of the aforementioned social recovery design document: #234

It lists basic requirements and details the setup stage, but not the recovery stages yet.