Existing research about m-of-n paper seed phrases

Question

I'm interested in designing a protocol that stores a seed phrase for a crypto wallet across N separate pieces of paper (or metal!), where any M of the pieces of paper can reconstruct the seed phrase, but less than M cannot.

I would like the entire scheme to be something you can do by hand, as these seed phrases shouldn't touch a general-purpose computer for security reasons.

Concretely: does a scheme that splits a paper seed phrase into separate parts exist?

Ideally I am looking for a scheme that uses only hand-computation, not math that you have to do on a computer.

I am not looking for a "multisig" scheme. What I want is a scheme to store the seed for a single deterministic wallet (likely a hardware wallet such as Trezor or Ledger), but in a distributed way on paper. The goal is that a person can distribute these parts to various trusted contacts, safety deposit boxes, safes, etc and not be vulnerable to a single point of failure either by losing one of the parts or by one part being compromised.

Answer 1

So, there are two answers to this. I will list them separately.

(1) The company Trezor has implemented Shamir Backup into their new Model T hardware wallet:

https://blog.trezor.io/shamir-backup-a-new-security-standard-3aa42a6ebb5f

and

https://github.com/satoshilabs/slips/blob/master/slip-0039.md

For practical purposes if you already trust the hardware wallet to behave as intended this is probably the best thing to do.

Answer 2

Second answer: It is possible to do M-of-N secret sharing entirely by hand, perhaps with the use of an old-fashioned pocket calculator, if M and N are small.

For example, if N=3 and M=2 you will create three 2-of-2 schemes.

A single 2-of-2 scheme can easily be made using addition modulo the number of words. For the BIP-0039 words this is addition mod 2048.

To hide the word "volcano" (word number 1965 on the BIP-0039 list, when indexed from 0), you generate a random number such as 376 ("congress"), and then compute 1965-376 mod 2048 = 1589 ("shop").

Now "congress" is written on one sheet, and "shop" on the other. To get the real word - "volcano" - you need both sheets. Having just one sheet gives you exactly no information.

You create three of these schemes, for a total of six sheets. Each 2-of-2 scheme is split between two of the three parts, and so each part has two sheets, like the edges of a triangle.

For a 2-of-4 scheme you would create 6 2-of-2 schemes and so on. These "trivial" 2-of-N secret sharing schemes look like complete graphs on N vertices.

For 3-of-N trivial secret sharing works similarly, but your 2-of-2 schemes are replaced by 3-of-3 schemes by the same method (3 numbers that add up to the secret number, modulo 2048).

As M and N grow, the number of sub-schemes grows like N Choose M, and the number of sheets of paper is double that, so this is only practical for M and N small. For example, a 2 of 5 scheme would require 20 sheets of paper, with each fragment having 4 sheets. This is doable by hand, but probably represents the upper limit of what people would bother with.