Shamirs Secret Sharing

This refers to splitting a key K over n entities, in such a way that you need k entities to reconstruct the secret. k-1 entities can neither reconstruct the secret or any parts of it; if that conditions does not hold, the procedure is considered to be not secure.

• split K over n entities
• k := {2,...,n-1}; at least k < n entities

Issue: One malicious actor could submit the wrong key, collect the keys of the other participants and then reconstruct the secret without sharing it with the other participants. You are required to trust all participants during the decryption process.

Reconstructing Polynomials

It is possible, given n points (x_i, y_i), to reconstruct any polynomial p with deg(p)>n using Lagranges Interpolation Theorem; furthermore there are infinitely many polynomials of deg(p) when given n-1 points.

The main idea is to generate a polynomial of degree n-1 and give m, m \geq n entities one point on the polynomial; to reconstruct the polynomial and therefore reconstruct the secret, the points of at least n entities are needed.