2. Shamir’s Secret Sharing Protocol

So, now, let us abstract both the examples that we had seen by this general problem of what we call as (n, t) secret sharing and this problem or this primitive was independently introduced by Turing award winner, Adi Shamir in 1979 and by Blakley in the same year.

In this section, we introduce the concept of (n, t) secret sharing, a method for securely sharing a secret among a group of shareholders. This primitive was developed by Adi Shamir and others in 1979. The essence of this method is to ensure that a secret can only be reconstructed when a specified number of shareholders (at least t) come together. This is crucial in scenarios where you want to protect sensitive information from being accessible by a single entity or an insufficient number of entities.

Think of a team of security guards at a vault where they need a correct combination of keys to access the vault. Each guard has a key, but any single guard alone cannot open the vault. The vault can only be accessed if at least two guards come together and use their keys. This mirrors the (n, t) secret sharing model.

The knowledge of the secret space is publicly known, namely, it denotes the set of all possible secrets which dealer can have. What exactly is the value of the secret from the secret space which dealer has no one will be knowing...

In this part, we outline the primary components of the (n, t) secret sharing model. The dealer, who possesses a secret 's', distributes this secret among intended shareholders. The secret comes from a known set called the 'secret space.' Although everyone understands the range of possible secrets, they do not know the exact secret held by the dealer. This ensures that the security of the secret is maintained, even if the method of sharing it is known.

Imagine a treasure map that indicates possible treasure locations. While everyone knows where the treasure could be found, only one person has the exact location marked. Even if someone knows all the treasure spots, they won't find anything without the precise map with the actual location.

we require that it should be impossible for any set of t or less number of shareholders to pool their shares and reconstruct back the secret s. So again, like n, t is also some given parameter...

The sharing mechanism must satisfy two critical requirements. First, if t or fewer shareholders come together, they shouldn’t be able to reconstruct the secret. This ensures that as long as less than t parties attempt to access the secret, it remains secure. Second, if t + 1 or more shareholders unite, they should be able to reconstruct the secret unambiguously. This threshold system protects the secret from being compromised too easily while still permitting those who have the requisite number of shares to retrieve the secret.

Returning to the vault analogy: if only one guard tries to open the vault, they cannot do so. However, if two guards are present, they can successfully input their keys and access the vault without any issues. This dual requirement strengthens the security of the system.

So, let me discuss this (n, t) secret sharing scheme due to Shamir. So, this is also called as Shamir’s (n, t) secret sharing scheme...

Shamir's secret sharing scheme is described next, highlighting its elegant solution to the (n, t) problem through the use of polynomials. The dealer selects a random polynomial of degree t, with the constant term being the secret. The shares are calculated as points on this polynomial. Only t + 1 or more points yield enough information to reconstruct the polynomial, thereby revealing the secret. This technique ensures that while knowledge of the polynomial's structure is public, the specific polynomial chosen (and hence the secret) remains unknown to those with fewer shares.

Imagine a huge piece of artwork that is divided into segments. Each segment corresponds to a polynomial evaluation and together they form the whole artwork (the secret). Only when several segments are combined can the entire artwork be reconstructed. However, having only one or two pieces won't reveal anything meaningful about the entire image; hence the secret is safeguarded.

And now, the share for the ith party is the evaluation of this polynomial at x = x, of course, all operations done over a finite field...

In this chunk, the method of constructing shares is made clear: each share corresponds to the evaluation of the polynomial at distinct x-values. These x-values are public knowledge while the polynomial and its related random coefficients remain private to the dealer. This setup means that each shareholder receives a unique share of the secret that can’t reveal any information about the secret on its own.

Consider a digital puzzle where each piece (share) has a unique shape. Even if one person has a piece, it won’t make sense until they fit it with other pieces (shares). Each piece is designed in a way that, alone, it doesn’t disclose the entire image of the puzzle (the secret).

The reason it constitutes (n, t) secret sharing is because of the following 2 facts...

The properties that allow reconstruction of the secret center around polynomial functions. If you have more share evaluations than the degree of the polynomial, you can reconstruct the polynomial and thus the secret. Conversely, with fewer points than the degree of the polynomial, the exact polynomial cannot be determined, thus leaving the secret undisclosed. This dual property is what makes Shamir's method secure and functionally sound for secret sharing.

If you’re given a jigsaw puzzle with too few pieces, you can’t accurately guess the picture. However, if you have just the right amount of pieces to create a recognizable image, you can easily reconstruct it. This logic behind reconstructing secrets in Shamir’s scheme plays out similarly.

--