1.3. Shamir's (n, t) Secret Sharing Scheme

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.

The concept of secret sharing involves distributing a secret among a group of participants (or shareholders) so that only certain combinations can reconstruct the secret. Shamir introduced this method as a solution to ensure that no single party has enough information to compromise the secret, enhancing security in scenarios like nuclear weapon launch codes or banking systems.

Think of a treasure hidden in a vault that can only be accessed with multiple keys. Each key represents a share in the secret, and the (n, t) scheme specifies how many keys are needed to open the vault. If someone only has one key, they cannot access the treasure, similar to having too few shares to reconstruct the secret.

Among these n parties, there is a designated entity or a special entity whom we call as a dealer denoted by D. And dealer has some private input some secret input, let us denote it by s which is a bit string or it could be any abstract value, but you can always assume that it is a bit string and this value s belongs to a bigger set namely this set S which I call as the secret space.

In the (n, t) scheme, a dealer is responsible for sharing the secret. The secret s must come from a predefined set of potential secrets, called the secret space S. This set is known to all participants, but the actual secret selected by the dealer remains unknown until enough shares are combined. The specific values that can be secrets are predetermined, ensuring that the sharing process is standardized.

Imagine a locked box where only specific types of keys that fit can open it. The set S represents all the types of keys (potential secrets). The dealer can choose one key (the actual secret), but everyone knows that the key has to be one from that set.

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... The second requirement is that if t + 1 or more shares are available from this vector of n shares, then it should be possible to efficiently and uniquely reconstruct back the secret s.

The (n, t) secret sharing scheme is designed to be secure under two main conditions. First, if any t or fewer shares are used, the secret cannot be reconstructed. This prevents scenarios where a small number of compromised shareholders can reveal the secret. Second, if more than t shareholders combine their shares, they should be able to reconstruct the secret unambiguously. This ensures that trust is required in a group and prevents unauthorized access.

Returning to the vault analogy, you might imagine it requires at least two of three possible keys to unlock the vault. If only one key is used, the vault remains secure. However, once two keys are combined, the vault can be opened, ensuring that too many keys do not compromise the treasure.

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. He gave a very nice and very elegant solution for solving the (n, t) secret sharing problem.

Shamir designed an elegant algorithm to implement the (n, t) sharing scheme using polynomials. The dealer selects a random polynomial of degree t, where the constant term of this polynomial represents the secret. Shares are then derived as unique points on this polynomial, calculated at different non-zero values for x. This technique ensures that only a combination of shares equal to or exceeding the threshold t can reconstruct the secret, while any smaller number of shares cannot.

If we think about a group project where a final report is represented by a polynomial equation. Each team member holds a part of the report, where the final conclusion can only be derived when enough team members come together to discuss their sections. If only a couple of members meet, they lack enough context (or shares) to finalize the entire project.

Now, the question is how exactly we can solve this? The idea behind Shamir’s secret sharing scheme is the following so, imagine dealer as this secret s...

In Shamir's method, the dealer constructs a polynomial where the constant term is the secret and evaluates this polynomial at distinct points to generate shares. The polynomial's properties ensure that a minimum number of shares allows for the reconstruction of the secret while fewer shares provide no information about the secret itself, thanks to fundamental properties of polynomials.

This can be likened to how a restaurant menu operates. Each menu item (polynomial) reveals its ingredients only if you know the right combinations (shares). If you inquire about a single ingredient (share), it does not reveal much about the dish (secret). Only when you gather enough information from multiple dishes (t+1 shares) can you fully understand how they are prepared (reconstruct the secret).

--