Security and reconstruction

Why k-1 shares learn nothing

The easy part is understanding that k shares reconstruct the secret. The deep part, the one that gives the scheme its security, is understanding why k - 1 shares learn absolutely nothing.

The geometric intuition

Let's take the threshold k = 2 again, so a line. Suppose a spy captures a single share, say (1, 10). What can they deduce about the secret S = P(0)?

  y
   |          . '     <- infinitely many lines
10 |  *(1,10) . '        pass through the single point (1,10)
   | .   ' .  '
   |'  '     '
   +--------------- x
   0   1

For EACH value of S at x=0,
there is exactly one line
passing through (1,10). None is
more likely than another.

Through a single point pass infinitely many lines. For each conceivable value of the secret at x = 0, there exists exactly one line that also passes through (1, 10). All these values of S are therefore equally possible. The captured share eliminates no hypothesis.

The general case: k - 1 points

The reasoning generalizes. With k - 1 shares of a polynomial of degree k - 1:

Fix k-1 points. Test a candidate value S = v.
This adds the point (0, v): we then have k points,
which determine ONE unique polynomial of degree k-1.

  candidate S = v0  -> a consistent polynomial P0
  candidate S = v1  -> a consistent polynomial P1
  candidate S = v2  -> a consistent polynomial P2
       ...                 ...
Every possible value of the secret is compatible
with the k-1 shares. None is distinguishable.

For any candidate value v of the secret, there exists exactly one polynomial of degree k - 1 that passes through the k - 1 known shares and through (0, v). There are therefore as many consistent polynomials as possible values of the secret, and they are all equally likely.

Perfect secrecy: the one-time pad analogy

This property has a strong name: perfect secrecy (or unconditional security). It means that knowing k - 1 shares changes nothing about the probability of each secret:

P(secret = S | k-1 shares known) = P(secret = S)

This is exactly the guarantee of the one-time pad: the ciphertext learns nothing about the plaintext. Here, k - 1 shares learn nothing about S.

	One-time pad	Shamir (k-1 shares)
What is observed	the ciphertext	k - 1 shares
Information about the secret	none	none
Type of security	perfect / unconditional	perfect / unconditional
Holds against	infinite computing power	infinite computing power

This is a major difference with RSA: Shamir's security does not assume any hard problem. It is proven, and even an infinitely powerful attacker learns nothing from k - 1 shares.

A condition to respect

This perfection assumes coefficients a_1, ..., a_{k-1} drawn truly at random and arithmetic in a finite field (next lesson). A biased draw would break the guarantee.

Summary