A beginner’s guide to Shamir’s Secret Sharing

An introduction to this privacy-preserving cryptographic technique and how Keyless is using it to transform the way we share and store private data across the internet.

Shamir’s Secret Sharing scheme is an important cryptographic algorithm that allows private information— “secrets” — to be distributed securely amongst an untrusted network.

It is one of the cryptographic techniques that Keyless uses to ensure that personal data is kept safe and secure — whether that’s biometric data, private keys or any other personal information that should not be made public.

To understand Shamir’s Secret Sharing, first it’s important to understand what secret sharing aims to achieve.

What is secret sharing?

In cryptography, secret sharing is a way to securely distribute fragments of important private information amongst a distributed network or group, making such schemes particularly useful for safeguarding highly sensitive information like private cryptographic keys or biometric data.

Secret sharing works by splitting private information into smaller pieces — or shares — and then distributing those shares amongst a group or network.

Each individual share is useless on its own but when all the shares are together, they reconstruct an original secret.

Imagine that you had one million dollars that you kept in a bank account, and in order to access this bank account you used to the password: secret.

You could split it up and distribute a letter each to six trusted shareholders.

s_____, _e____, __c___, ___r__, ____e_, _____t

The only information that each shareholder would have is the letter that they hold, essentially making their individual shares useless.

Secret sharing schemes can also be hierarchical depending on how the shares are distributed. This allows the secret owner to distribute shares based on how much the shareholders are trusted.

Let’s say you wanted to safely store your private key that you used to access your cryptocurrency wallet.

Private keys are used to send cryptocurrency from one address to another. They consist of a sequence of random and unique numbers and are given to users at the time they open a wallet.

Firstly, you wouldn’t want to give anyone the entire sequence, so say you split the key into eight shares. Then you distribute copies of those shares between your closest friends and trusted family members.

You may give eight shares to each of your parents, who you trust without a doubt, four each to your brother your sister, who you trust for the most part, and one each to eight of your friends, who you somewhat trust.

This hierarchical distribution scheme allows for secret owners to distribute shares based on how much they trust their shareholders.

But what about when there is no trust between the secret owner and the shareholders?

In most schemes an added encryption layer is implemented to ensure additional privacy and security, allowing the shares to be distributed amongst a network or group that are unknown to the secret owner.

Let’s say that each shareholder only holds what seems to be random numbers:

19_____, _5____, __3___, ___18__, ____5_,_____20

With encryption, when all the separate shares (numbers) are together, they still require a decrypting key to reveal the secret (letters) that they represent in the alphabet.

This important step protects private information from organized attacks; even if each shareholder were to collude to recreate the original secret, they wouldn’t be able to learn anything about that secret, as the original secret is encrypted.

Understanding Shamir’s Secret Sharing Scheme

One of the challenges of distributing shares is that they can often be lost or compromised. Shareholders can die, lose their shares or have them stolen. At other times, shareholders themselves turn rogue. When many different shares are distributed, it’s also impractical and inefficient to require all shares to reconstruct the secret.

Shamir’s Secret Sharing scheme is an algorithm that was first proposed in 1979 by the renowned Israeli cryptographer Adi Shamir. It allows for information to be broken into many shares, while only requiring a fraction of those shares to reconstruct the original secret.

This means that, instead of requiring all shares to reconstruct the original secret, Shamir’s scheme requires a minimum number of shares — this minimum is referred to as the threshold.

One of the benefits of Shamir’s algorithm is that it is flexible and extensible — meaning that the secret owner could add, amend or remove shares at anytime if they wanted to, without modifying the original secret.

The threshold needs to be met in order to reconstruct the secret. If there is anything less than the threshold, the secret cannot be reconstructed, thus making Shamir’s Secret Sharing secure against an adversary — a malicious attacker — that has unlimited computational power; in cryptography this is what we call information theoretically secure.

Information theoretically secure simply means that not even an adversary with unlimited computational power would be able to break the encrypted secret.

For example:

Using the same example from earlier, say that the threshold to reveal the password is 3:

When three shares are presented:

19_____, _5____, __3___ = 19,5,3,18,5,20 = secret

When two shares are presented:

19_____, _5____ = 19_____, _5____

It’s important to note that with Shamir’s algorithm, shareholders never find out what the other encrypted shares are in a secret. Only the secret owner has access to the entire set of decrypted shares once the secret is reconstructed.

How Shamir’s Secret Sharing actually works

Shamir’s method for secret sharing relies on polynomial interpolation, which is an algebraic method of estimating unknown values in a gap between two known data points — without needing to know anything about what is on either side of those points.

We will go into further detail on polynomial interpolation in another blog piece, but for the purpose of explaining how SSS works, you can think of it like this:

SSS encodes a “secret” into a polynomial, then splits it into pieces and distributes it It’s possible to use polynomial interpolation to efficiently reconstruct that secret without requiring every single share. Instead only the threshold is needed, which provides enough points of data to correctly estimate the values between gaps in the encrypted shares.

Why Shamir’s Secret Sharing is essential to maintaining data privacy

Shamir’s Secret Sharing makes it possible for multiple parties who do not know each other to store private information. In Keyless’s case, this would be for securely storing user secrets — whether that’s personal information or private cryptographic keys — across our distributed network.

Because Shamir’s Secret Sharing scheme is information theoretically secure, even an attacker with unlimited computational power cannot break the decrypted share to access the data without having enough shares to meet the threshold — or minimum number of shares.

When combined with other cryptographic techniques, like secure multiparty computation and zero-knowledge cryptography, SSS offers an extra layer of security, making data sharing and storage secure, private, and resilient to accidental data loss and external attacks.

How Keyless uses Shamir’s scheme to keep your biometric data private

Thanks to this algorithm, we can safely distribute secret data in a way that is efficient, secure and private. Instead of storing sensitive data on centralized servers, Keyless is able to split encrypted secrets into pieces, distributing those randomly to nodes across a zero-trust network.

Imagine that you write down a secret message on a piece of paper. The message that you wrote uses whole words to substitute letters, but only you know that. For example, PIG stands for P. You place the piece of paper into an envelope, and then seal it and cut it into twenty different pieces, and give those pieces out to random strangers at Shibuya crossing in Tokyo — the busiest pedestrian crossing in the world.

Since the encrypted data is split into ‘shares’ and randomly assigned to Keyless nodes, there is no longer a centralized storage system that adversaries — also known as hackers or bad players — can target.

Someone who wanted to find those pieces of the envelope and use them illegally, wouldn’t know where to start looking.

To reconstruct the message, a minimum number of shares need to be collected from nodes in our network. So in order to compromise the user’s “secrets”, someone would need to take over enough nodes in the network to acquire the minimum number of shares to meet the threshold.

Despite the odds, that person would need to find at least half of people carrying different pieces of the envelope. They would then need to try to steal the pieces from these five strangers — who may have their own weapons to fight off the attacker.

The last line of defense is that the shares are encrypted, so even if an attacker compromises all the nodes of the network, it can’t decrypt the shares because they are encrypted with a key that is only stored within the user’s device.

Imagine, the attacker finally managed to steal five of those pieces of the envelope you wrote your message in. Now, he can finally learn what the message is. However, when he goes to open the pieces, he finds a bunch of random words, and he in unable to make sense of it. The only person that knows how to decrypt the message is the person who created it — you.

The potential of secret sharing

As our physical and digital worlds continue to converge and blend together, SSS, combined with zero-knowledge encryption and secure multiparty computation, will most likely be used to decentralize risk across all industries, while enabling users to confidently share private data in a way that is secure and empowering.

Thinking beyond biometric authentication, Keyless is using SSS to build platforms that allow us to securely manage our private cryptographic keys online, as well as our entire digital identities. These technologies will help transform the way we interact with the internet and the world around us, giving unmatched power and control back to the user.