Shamir Secret Sharing with No ID Numbers! by Jorge Arce-Garro | Devcon Bogotá

All right, good afternoon everyone. Uh so my name is Jorge Arce. I am a blockchain and cryptography researcher at Nethermind. And today I want to tell you guys about Shamir Secret Sharing with no ID numbers. But before we get into the problem we're trying to solve, we would like to have a bit of a review on what Shamir Secret Sharing is all about.

So for today, because this is a lightning talk, we're going to go with a simple example. Um so let's suppose you just got this great news. You just got the private key of a wallet that is holding a thousand ether. Here's the private key. Now don't actually input this into MetaMask or you will be very disappointed, okay?

For secure long-term storage of this uh seed phrase, you want to do the following because it's a lot of money, right? So you're going to split the key into several 12-word seed phrases such that if you have two of those seed phrases, then you have enough information for reconstruction. Furthermore, you want the secret to be accessible even if one of the pieces in which you like split the information gets lost. Um and there's a third property actually that I'm mentioning uh which is you would like it so that an attacker that has um two of the pieces, no, I'm sorry. If an attacker has one of the pieces but not two, they cannot gain any information about your secret whatsoever.

So you decide that you will create three pieces such that you need two of them to reconstruct the secret. And technically we call this a two-three threshold scheme. This is what you're after. Okay, so how does this go? Um this is an old algorithm created by Shamir in 1979.

We start with the seed phrase. And the first thing we're going to do is we're we're going to turn this into a number. Uh this is in binary. What we did is we took bit 39's 2048 word dictionary and we, depending on the position of these words in that dictionary, we assign a binary binary number to each of the words. Once you have that, you're going to take a good old XY plane and you're going to take the secret.

This is a number after all and you're going to place it on the Y axis sort of like as an intercept. So, that's stage one. After that, you're going to take a random straight line that passes through the secret. Uh why a straight line? Because this is the simplest example where you only need two pieces for reconstruction.

If you wanted something more complex, you would be using like a parabola or a higher order polynomial, but let's just stick with the straight line for now. So, you have that straight line which you chose essentially at random and you're going to pick three points on the line and those points are going to be your shares. Now, what happens is lines have this very nice geometric property that says that any two uh points on a line are enough to uniquely determine the properties of your straight line. And in this context, that translates to any two shares generate the correct secret. Um just check it out.

If I have those two points, shares one and three, let's assume that share two got lost. You generate the straight line just as before and lo and behold, the intersection with the Y axis is the secret that you were trying to conceal. And this is going to be the same regardless of which two shares you have. It's independent of that, right? You have share two and share three?

You do the exact same thing. You get the same secret every time. So, we got that nice redundancy property we're after. In this example, and this is kind of unwieldy and a little bit hard to read, uh the shares are the following. The first one, this is the binary that you get if you were to actually like get the coordinates of those points on the Y axis.

Uh here's for the second point and here's for the third point. Notice that I am also labeling each of the shares with the corresponding X values 1, 2, and 3. Those are going to be called the ID numbers. Now, we don't like this. Uh it's hard to read.

So, we're going to use the BIP39 dictionary once more to turn this into words. Like so. And now that's more familiar. All right. So, this is what Shamir's Secret Sharing is all about.

But, I want you to notice this a special detail here, which is that Sorry, my bad. I am keeping the ID numbers next to the shares. They must be labeled, and this is crucial. If I were not to do that, like what would happen if I miswrote one of the ID numbers, and I mislabeled one of the many shares that I have? So, if you come and check this example, let's say I have the second share, and I make a mistake and I label it with a one instead of a two.

Notice how the geometry of the situation is going to change. Now, this point is going to be moved slightly to the left. When you go ahead and try and do the reconstruction, whoops. You're not going to get the same straight line. You're going to get something different.

You get the wrong secret. And uh that's a problem. This may not sound like a big deal, but keep in mind that you may be dealing with many shares at a time. You may be dealing with 12 points at a time. If the labels get lost, it can be uh a bit of a nuisance like solving for all the possible permutations and trying to find which one is the correct one.

So, can we improve this? We are trying to circumvent the labeling entirely. Can we encode the ID numbers in the seed phrase itself? Without having the need to add any extra words to the seed phrase. This would be nice because then I could like just mix those uh seed phrases, and no information would be lost even if the labeling uh was incorrect.

As it turns out, there's uh a peculiarity about BIP39 seed phrase standard that we can exploit to our advantage here. It turns out that not all the bits corresponding to the seed phrase carry dependent information. There's a checksum hidden in here. In the particular case of 12 words, which is what we're dealing with, it turns out that the last four bits are not independent information. Like you took the seed phrase from the initial example, the one with 1,000 ether, you turn it into binary, and these four numbers, they do not carry independent information.

What they do carry is a checksum. Go ahead and take all of the bits except for the last four, compute SHA-256 of that in binary, and you're going to get a hash. The first four bits of that hash are what you put in here. And this is there so that if you like miswrite one of your words, then uh like a wallet software can tell you that you messed up. We can use this to our advantage here because given that that is not independent information, there is no need to include the checksum bits for share generation or reconstruction.

Let us go with this slightly different approach. Um we have the this beautiful seed phrase once again. This is the binary encoding of it. And let's just discard this. We can do that without fear because this information can be regenerated whenever we want.

Now we're going to do Shamir secret sharing the same like um straight line, put the secret on the Y axis, choose a random line passing through it. On the non-checksum bits, so that the ones that actually carry information. And this time um once you do that, let's say that we get these shares. Once again, this is hard to read. We don't like this format.

But before we can turn it into um words using the dictionary, we're going to need to fill in these gaps, right? Now here's the nice thing. These gaps are places where where we can store extra information. For example, I could take these ID numbers and encode them into binary and those will be the last four bits with ID numbers I mean those will be the last four bits of each of my shares that I can put in there. Now I turn this into a seed phrase once again.

Like all of those into seed phrases. And you would get these three shares. Notice that they do not have any labels anymore. You don't really need to because if you take the last word in each of those and you turn it into binary with the dictionary. For example, popular this one ends in 0001 meaning that this should be the first share.

This one ends in 00110 the chaos the encoding of chaos meaning that this has to be the second entry and likewise for this one. So this is a nifty little trick that you can use if you want to get rid of the labeling. There's other things you can do with that with that extra space for information. You could add a checksum to the to the shares themselves. That's something do.

But we're choosing to do this because it's it seems like a convenient extra feature that we can add to Shamir Secret Sharing. All right. So thank you very much for your attention. Right here. And here's some advertising on behalf of Nethermind.

You can enter our repo I mean our GitHub Nethermind ETH and you'll find this repo research mnemonic. So this is a tool that we built with extra love to all the Ethereum community. If you guys want to use Shamir Secret Sharing for your privacy purposes for your thousand ETH airdrops or what not. I don't know if you guys are that lucky then you can use this tool. And yeah.

So thank you so much. I am Jorge Arce blockchain and cryptography researcher at Nethermind. If you have any questions or comments I'm more than happy to take those. Thanks. Hi.

Is it possible that when converting to shares it no longer fits into 12 words and has to be like 13 words or something? That's a good question. So, what can happen is we have four bits of wiggle room, right? That means that we can label as many as 16 shares. If you wanted to go above that, we would need extra bits.

And you would need an extra word. So, we don't really like that. We that that seems not very elegant. So, what we do is we limit the functionality of this feature to if you're dealing with 12-word seed phrases to 16 shares maximum. Which in practice is a sensible restriction.

We've seen that like important multi-sigs all over the Ethereum community, they normally don't go over like 11 shares or whatnot. But, if you were to use like a 24-seed phrase, for example, then you have more bits that you can use. I think you have like seven or eight bits for the encoding. And then you have like 256 shares that you can use. But yeah, that's a good question.

And there's a there's a limit on how many of these you can label. But the limit is sensible considering like the the real-world use cases. Thank you for the question.