Shamir's secret sharing algorithm

Published: Last Edited:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

Why Shamir's scheme is perfectly secure?

"[1]Shamir's Secret Sharing is an algorithm in cryptography. It is a form of secret sharing, where a secret is divided into parts, giving each participant its own unique part, where some of the parts or all of them are needed in order to reconstruct the secret." A simple example would be suppose two people came upon a map that would lead them to an Island where ample amount of treasure is stored which will make them rich. Now to prepare for the adventurous expedition they would like to go home. The question arises i.e. who will keep the map since they both don't trust each other? An ideal solution to this situation would be to split the map in such a way that they both can't travel to the Treasure Island without each other. This concept basically defines Shamir's sharing scheme.

In Shamir's (k,n) threshold secret sharing scheme n participants hold shares generated from the secret s where any k of the parts are sufficient to reconstruct the original secret. A (k,n) threshold scheme has to satisfy the PERFECTNESS i.e. any information about s cannot be obtained from k - 1 or less shares and s can be completely recovered from k or more shares. This threshold scheme is an IDEAL secret sharing scheme if the maximum bit-size of share always equals the bit-size of s.

Considering Shamir's scheme as an interpolating scheme based on polynomial interpolation as shown in the equation below:

F(x) = a0 + a1x + ... + ak - 1 xk-1

In the above equation coefficient a0 is set as the secret and all other coefficients are random elements in the field. In this the field is known to all participants. Each of the n shares is at point (xi, yi) on the curve defined by the polynomial, where xi is not equal to 0. Given any k shares, the polynomial is uniquely determined and hence the secret a0 can be computed. However, given k - 1 or fewer shares, the secret can be any element in the field. Therefore, Shamir's scheme is a perfect secret sharing scheme

Hence, Sn = S1 + S2 where Sn is the secret which is created by the combination of shares S1 and S2.

Similarly an interesting special case is perfect security: "an encryption algorithm is perfectly secure if a cipher text produced using it provides no information about the plaintext without knowledge of the key. If E is a perfectly secure encryption function, for any fixed message m there must exist for each cipher text c at least one key such that c = Ek (m).[2]" Therefore, it would be necessary to combine all the key's k for each cipher text in order to obtain the original text or else it would be impossible for decryption to take place hence suggesting Shamir's theory to be perfect.


[1] Wikipedia - Shamir's Secret Sharing

[2] Wikipedia - Information Theoretic Security