The words Secret and Sharing when used together produce a kind of ambiguity.!¬†Traditionally! a secret is something which is not to be shared.!. Well to clarify,in this scenario it is about dividing a secret into many different secrets. This was surely a breakthrough in Cryptography when Adi Shamir and George Blakley independently invented it in 1979. Blakley’s scheme was something related to hyperplanes. I will brief about Shamir’s scheme.

Shamir’s paper on secret sharing titled “How to share a secret?” was a kind of revolution. Shamir proposed a scheme in which a secret can be divided into many secrets where each secret independently would not reveal any information about the original or the parent secret for reasons that are obvious. It is a mere two page paper which holds a lot information. In brief the scheme is something as follows: A secret, is divided into ‘n’ different parts. Let this secret be ‘scrt’. If any ‘k’ of the ‘n'(1 < k <= n) parts come together( come together here refers to some mathematics), then the secret ‘scrt’ is revealed. Beauty of the scheme is that if any of the ‘k-1′ or less shares come together then even with theoretically infinite computing power, the original secret,’scrt’ cannot be recovered.

The scheme is based on the mathematical concept of interpolation. The secret ‘scrt'(assumed to be a number) is divided into ‘n’ parts. This is done by randomly picking a polynomial of degree ‘k-1’. Let this polynomial be called q(x).

q(x) = a0 + a1x + a2x^2+…..+a’k-1’x^k-1.

Now the original secret, scrt = q(0) = a0. scrt1 = q(1),scrt2 = q(2)…scrtn = q(n).

Now consider any subset of this ‘n’ broken secrets (scrt’i’), With these a ‘k’ values a polynomial can be formed by interpolation whose constant term ‘a0’ will give the value of the original secret. scrt = q(0). On the other hand, any k-1 or less number of broken secrets can form polynomials of degree strictly less than k-1 and hence value of scrt can never be recovered. Advantages of the scheme and a better explanation! can be found in the original paper.

Advertisements