tldr Shamir secret sharing seems to beat XOR secret sharing when there’s more than 10 participants but practical use cases are usually less than 10 participants. Also XOR secret sharing is easier to understand and use. Should I use Shamir or XOR in practice today? And which software in particular?
The paper introducing Shamir's Secret Sharing Scheme starts as follows:
In 2, Liu considers the following problem:
Eleven scientists are working on a secret project. They wish to lock up the documents in a cabinet so that the cabinet can be opened if and only if six or more of the scientists are present. What is the smallest number of locks needed? What is the smallest number of keys to the locks each scientist must carry?
It is not hard to show that the minimal solution uses 462 locks and 252 keys per scientist. These numbers are clearly impractical, and they become exponentially worse when the number of scientists increases.
Shamir secret sharing requires smaller key sizes than trivial secret sharing. Wikipedia lists how this trivial secret sharing scheme can achieved using simple XOR operations:
There are several (t, n) secret-sharing schemes for t = n, when all shares are necessary to recover the secret: Encode the secret as a binary number s of any length. Give to each player i aside from the last a random binary number pi of the same length as s. Give to the last player the share calculated as pn = s ⊕ p1 ⊕ p2 ⊕ ... ⊕ pn−1, where ⊕ denotes bitwise exclusive or. The secret is the bitwise exclusive-or of all the players' numbers (pi, for 1 ≤ i ≤ n).
When space efficiency is not a concern, trivial t = n schemes can be used to reveal a secret to any desired subsets of the players simply by applying the scheme for each subset. For example, to reveal a secret s to any two of the three players Alice, Bob and Carol, create three (3C2) different t = n = 2 secret shares for s, giving the three sets of two shares to Alice and Bob, Alice and Carol, and Bob and Carol.
In theory, I understand why this makes Shamir superior to just doing XOR.
In practice however, here are my observations.
- Use case: The main practical use case of secret sharing is backups rather than any day-to-day usage. Unlike say, blockchain multisigs, where the shares don't always need to be assembled at one location and hence day-to-day usage is also feasible. Backups can be made of other cryptographic keys, files, addresses, and generally any sort of important information you can imagine storing on a computer.
- Long-lasting: Backups are expected to last with limited to no maintenance for many years. However hard drives fail every few years and software, operating systems, and internet protocols get updated every few years as well.
- XOR secret shares can be backed up on paper or DVD and are easy to perform by hand. The scheme can be explained to someone with limited mathematical knowledge, and can be written down in plain English on a piece of paper. Shamir secret sharing can be performed by hand too, but this is not standardised as of 2024, is more complicated to explain to other participants and has more chances of someone making an error.
- SSSS requires storing a copy of the software and a copy of the compiler (and the OS?), and risks mistakes if you lack technical skills or understanding of the software you are running. Journalists have previously messed up using PGP in high stakes situations, if I understand correctly.
- If you are sufficiently paranoid, you could use secret sharing to encrypt information that points to a one-time pad stored somewhere else. This lets you encrypt and decrypt information without access to electricity, a computer, or any other tool or information from modern society.
- Mature software: Cryptographic software in particular takes a long time to mature. Asymmetric encryption software has taken over 20 years to mature.
- As of 2024, there is no battle-tested implementation of Shamir secret sharing that can be entrusted with people's lives or millions of dollars. Most implementations around seem suitable for hobbyist and low stakes usage. PayPal famously messed up their implementation of SSSS and risked losing their entire business over it.
- This could change in another decade if enough people cared to battle-test it, but is not guaranteed to happen. ssss on linux was non-standardised a decade ago, and still seems non-standardised today.
As Matthew Green has noted, “poking through an OpenPGP implementation is like visiting a museum of 1990s crypto.” The protocol reflects layers of cruft built up over the 20 years that it took for cryptography (and software engineering) to really come of age,
Number of participants: I'm yet to see a practical use case for secret sharing among >20 different trusted participants. Typically shares are split among family and friends or among trusted members at the top-level of a startup or corporation or board. Dunbar's number of 150 upper bounds how many people you want on your secret sharing scheme, and in practice you want key decision makers not people who would invite you for drinks.
- Hence the almost exponential blowup of key size just doing XOR seems less important? This is the hypothesis I'm least confident about. I tried reading theoretical use cases of secret sharing for multiparty computation and some require many participants. I'm not sure if any are usable in the real world.
Execution time: Encryption and decryption times for big files don't really matter since in practice most schemes be it secret shares or asymmetric keys are ultimately used to encrypt a symmetric key which encrypts the files. As long as the secret sharing part runs in a practical amount of time like 5 seconds, this is fast enough to encrypt or decrypt a backup.
Are any of my observations incorrect? Given actual stakes not hobbyist usage, which scheme would you recommend people use in 2024 and why?
