Support encrypted shares (by doing a second layer of 2-of-2 SSS)

[apoelstra]

Mostly filing this as an issue so I don't forget. If we took another header character to indicate a second layer of SSS, this would enable encrypted shards. (Which are useful temporarily for transporting shares, even if you think that keeping permanently encrypted shares aronud would be too fragile).

[roconnor-blockstream]

According to https://github.com/WebOfTrustInfo/rwot8-barcelona/blob/master/topics-and-advance-readings/social-key-recovery.md (referenced from SLIP-39) people may want multi-level SSS in order to facilitate social recovery subject to various restrictions.

[roconnor-blockstream]

The current proposal has left semantics for data portions beginning with A-Z as undefined (aka invalid). So there is room to repurpose that for multi-level schemes. Multi-level schemes will likely require a significantly more detailed header which supplies the thresholds of every group.

Perhaps something like MS1ZIIII(nS)*ZnS for a 2 level scheme where n is the threshold of the i th group and S is the index of the _i_th, with as many groups as there are 'n's until you hit a Z, with the final nS being used as the group threshold and index. for the share.

Another possible scheme is MS1ZnIIIISSSS where n is the threshold for the the first S is the group index, and then if you are using a threshold of 2 or 3 or 4, you use the 2nd, 3rd or 4th 'S' for your index. The position of the non-S character indicating the threshold size. This limits the size of the thresholds of the lower level to being 4 or less.

[apoelstra]

Between the two of those I like the first one, because it's more flexible and because it doesn't waste space on levels that aren't used, if they're not used.

In the 2-level case it also lets you fit the data into a single cryptosteel side, provided you drop the MS1Z prefix ... which is very inadvisable in general but might be okay for my ephemeral-encryption usecase.

[roconnor-blockstream]

For the simple transport case, a simple one time pad with a QQQ checksum would suffice.

[apoelstra]

I agree, and may do this in practice if I'm sending shares to people who are familiar with the scheme and its algebra. But using 2-of-2 has the following advantages:

• Does not require a "new" scheme which requires extra explanation/instruction to use
• Decryption forces the recipient to use the recovery wheel etc and do a "practice run" for actual recovery, ensuring that they are willing and able to do it

[roconnor-blockstream]

Here is a crazy half-baked idea.

Currently our HRP of "ms" implies a prefix that is effectively "PRRQDN". But what if we made our prefix "PRRQDNSSSSSSSS".

This has no effect on the basic 1 level splitting scheme other than an arbitrary change to the checksum initial value.

But now suppose you have one of your level 1 shares, and, post-facto you decide you want to split it. Either for transport, or otherwise.

What we do is define a new prefix, one of "ms2g" .. "ms9g" depending on the threshold choice for our second level share. These imply a prefix that is "PRRQDNSSSSSSS" through "PRRQDN" respectively. And we take our old level 1 share and prefix it with "S" through "SSSSSSSS" respectively.

What we have done is slid some number of "S"s from the implicit prefix to an explicit prefix. This makes it so that the final checksum value remains unchanged.

Now we run secret sharing on our second level share using the first character as the sub-share index.

Maybe we can leave the string of S's coming after the first character as implicitly added by the scheme's prefix.

[apoelstra]

Hah! To fill in some details, and check my understanding...

• ms turns into PRRQDN where the P comes from the initial monomial term in the checksum algorithm and the rest are from ExpandHRP (which encodes the high 3 bits of each character, then Q, then the low 5 bits) ... and that if we were to add eight Ss to this result essentially all this would do is change the initially-filled-out characters in the worksheet.
• But if we added all these Ss implicitly then we are no longer interpreting the HRP in the way that bech32 does. I guess this is your intention, although it makes me nervous because it's an obscure detail that somebody would need in order to reproduce the scheme
• You are suggesting that we use 2 as the HRP separator rather than 1, to make this deviation from bech32 clearer.

This is very tempting because, as you say, it lets the user decide retroactively to split his share up into more pieces, without having so many explicit Ss wasting space...on the other hand, I like that right now you can basically recreate the entire scheme knowing bech32, the new generator polynomial, and a few 1-in-32 guesses..

[roconnor-blockstream]

No, my intention was to begin with "ms2g1" for a 2-of-n second level split, and "ms9g1" for a 9-of-n second level split.

That said, there are some variations that are possible. The "g" can be whatever we want, and I'm tempted to move the digit into the data portion subject to a complicated checksumming rule.

One variation is to begin with msg1<n><s>... where <n> is a digit representing the threshold of the subshare and <s> in the index of the subshare, and a checksum rule that <n><s> is replaced by a string of 8 "S"s with the (10-<n>)th S replace with <s> is. Or we cold do msg<n><s>1... and construct the same string as (the tail of) the implicit prefix.

I think overall it is worthwhile to make this change, but maybe we can think of an even better idea.

[roconnor-blockstream]

Another line of thought is that we should be able to insert a carefully crafted 13 or longer character string at the beginning without changing the checksum. Possibly somewhat fewer than 13 characters if we mung the HRP appropriately. If we inserted 14 characters we would have a degree of freedom to perhaps choose a suitable value to indicate the threshold of the subshare.

[apoelstra]

I think we can't craft such a string without knowing the exact length of the full string. (Basically, inserting this string would shift the HRP and leading 1 from being multiples of x^n (mod the generator) to being a multiple of x^{n+13}. For a fixed HRP it is easy to calculate the difference in residue, which will be independent of n ... but our inserted characters will then need to equal this difference times x^-n, which we can't compute without knowing n.)

Having said this, I like your idea to have a "compressed encoding" for the shares which is uncompressed during checksum encoding.

[apoelstra]

One variation is to begin with msg1<n><s>... where <n> is a digit representing the threshold of the subshare and <s> in the index of the subshare, and a checksum rule that <n><s> is replaced by a string of 8 "S"s with the (10-<n>)th S replace with <s> is. Or we cold do msg<n><s>1... and construct the same string as (the tail of) the implicit prefix.

Ok, I like this. (The first one, where the extra data comes before the HRP.) I think the critical properties here are:

• The user will need to "decompress" the <n><s>s into the fixed-width S-string manually when working out the checksum worksheet
• (It is tempting to try to hide this by means of modifying the prefilled data or something, but since there are exponentially many possibilities I don't think this is feasible)
• The user does not need to do this decompression during any of the SSS steps, since the <n>s are constant and the <s>s are share indices which form a line.

I like this. My proposal though would be to just write <s><s>...<s>Z where the decompression step is simply to pad out the list of <s> values by adding Ss until there are 8 symbols total, and then to drop the Z.

Edit: actually I am forgetting that we need to encode both the share index and the threshold amount, at each level

[roconnor-blockstream]

Okay I think we can move all the nastiness into a specification of the second-level sharing.

Given any first level prefix, which currently is drafted to be PRRQDN and, because it is so short, is equal to its own residue, for any sub-threshold <n> there exists some other prefix of the form ...<n>S with no more that 15 characters, whose partial residue is also equal to QQQQQQQPRRQDN. Using that prefix we can push an "S" to the front of a valid MS32 string, and keep the checksum valid. The second-level sharing specification just needs to provide a fancy mapping of ms2g ... ms9g to the suitable prefixes of the form ...2S through ...9S in one table. That way we get a checksum that, commits to the threshold, and lets us insert a 'S' into the header which we can then use as a sub-index for secret sharing.

[apoelstra]

To be clear -- to do second-level sharing in this scheme, you will need to add (at most 15 characters to the start during the checksum worksheet (which we can hide behind precomputed values in the case of S but would quickly become unweildy for the other share indices). To do third-level sharing you'd need to add 30 characters, to do fourth-level you'd need to add 45, etc etc?

[roconnor-blockstream]

For the worksheet, what I'm imagining would require adding threshold - 1 many Ss to the start and having a lookup table to tell give you a compacted start for a given threshold.

[apoelstra]

The issue I see with that is that if I've got share A of a secret, and I want to further split that, then the prefix I want is ...SSSA rather than ...SSSS.