# Shamir secret sharing beats XOR in theory or in practice too?

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?

• I think your initial assumption that "the main practical use case of secret sharing is backups" is incorrect: At least a very common and important application of secret sharing is multiparty computation (here you find a really nice book on (pragmatic) MPC by Evans, Kolesnikov, and Rosulek). Also, often you want to tackle settings where a certain threshold (like half) of all shares is required. Even for backups think of the case when one of your devices/prints is destroyed => You want to add redundancy. That's where the trivial approach is bad in practice. Commented May 16 at 11:27
• @ellipsoid Thanks for replying! I will go through the book. You are right I didn't pay enough attention to MPC because I was more focussed on backups. I didn't understand why having a threshold of half matters, if you need any 4 out of 7 signatures on your company board for example, this can be done with XOR approach in wikipedia article. Being able to add/delete members without having to again securely communicate with existing members seems super important, you are right I will think about this more. Commented May 16 at 12:21
• For "MPC + secret sharing" too I am curious if any of the practical applications required a large number of participants (like >10 or >20). I will read more on this. Commented May 16 at 12:22
• Thanks for sharing that anecdote about PayPal and their secret sharing disaster. I hadn't heard it before. I don't think the story has any bearing on Shamir sharing vs XOR sharing, though. The story would have played out exactly the same if they had used XOR sharing. Still, I enjoyed hearing the anecdote. Commented May 17 at 2:53
• PayPal's problem is not about missing a standard solution this is about not knowing what you dealt with. SSS is already can be deal t shares out of n, long time ago. Commented May 17 at 9:28

If it's important in your application that secret recovery can be accomplished by xoring shares, you can use a transposed/bit-parallel version of Shamir's scheme, where instead of dividing the secret into $$q$$-bit pieces each representing an element of $$GF(2^q)$$, you divide it into $$q$$ pieces, the first containing only the lowest bit of each field element, etc. The $$n$$ shares are then just concatenated xors of those subblocks and $$(k-1)q$$ subblocks of random bits, and the secret is concatenated xors of the $$kq$$ subblocks of any $$k$$ of the shares. Calculating the correct combinations of subblocks is nontrivial, but since they only depend on the public parameters, you can precalculate them and publish them all. This requires $$n$$ secret shares and $$\binom n k$$ public decoding tables (or an untrusted computer to generate them on the fly), which seems preferable to $$k\binom{n}{k} = n\binom{n-1}{k-1}$$ secret shares.