Lab: split a secret three ways

The previous lesson claimed that below the threshold a set of shares is consistent with every possible secret, and that this is information-theoretic rather than a matter of computational difficulty. That is a strong claim. Here it is, demonstrated.

1. 1

   Write the implementation. Splitting hides the secret as the constant term of a random polynomial; recovery is Lagrange interpolation back to x = 0.

   bash Copy

   cat > /tmp/shamir.py <<'EOF'
   import random
   P = 2**127 - 1                    # prime field larger than any secret here
   
   def split(secret, threshold, shares):
       coeffs = [secret] + [random.randrange(P) for _ in range(threshold - 1)]
       f = lambda x: sum(c * pow(x, i, P) for i, c in enumerate(coeffs)) % P
       return [(x, f(x)) for x in range(1, shares + 1)]
   
   def recover(points):
       total = 0
       for i, (xi, yi) in enumerate(points):
           num = den = 1
           for j, (xj, _) in enumerate(points):
               if i != j:
                   num = (num * -xj) % P
                   den = (den * (xi - xj)) % P
           total = (total + yi * num * pow(den, -1, P)) % P
       return total
   
   secret = int.from_bytes(b"launch-code-42", "big")
   parts = split(secret, threshold=2, shares=3)
   for x, y in parts:
       print(f"share {x}: {y}")
   
   print("\nany two of three:")
   for a, b in [(0,1), (0,2), (1,2)]:
       got = recover([parts[a], parts[b]])
       print(f"  {a+1}+{b+1} -> {got.to_bytes(14, 'big')}")
   
   print("\none share alone is consistent with every possible secret:")
   x, y = parts[0]
   for guess in (0, 12345, secret):
       slope = ((y - guess) * pow(x, -1, P)) % P
       fits = (guess + slope * x) % P == y
       print(f"  secret could be {str(guess)[:20]:<20} -> share 1 still fits: {fits}")
   EOF
   python3 /tmp/shamir.py

2. 2

   Every pair reconstructs the secret exactly.

   text Copy

   any two of three:
     1+2 -> b'launch-code-42'
     1+3 -> b'launch-code-42'
     2+3 -> b'launch-code-42'

3. 3

   And one share fits every candidate secret you try.

   text Copy

   one share alone is consistent with every possible secret:
     secret could be 0                    -> share 1 still fits: True
     secret could be 12345                -> share 1 still fits: True
     secret could be 21982217121556893152 -> share 1 still fits: True

That last block is the whole property. With threshold two, one share is a single point, and exactly one line passes through that point for every possible value of f(0). The share does not narrow the secret down; it excludes nothing. Add a second point and the line is determined, which is why two shares recover it exactly.

Now the operational half. You just held three shares in one process, which is precisely the moment threshold MPC removes: the shares came together, so the complete secret existed in one place. Everything you demonstrated about secrecy below the threshold was true and irrelevant during that instant.