Shamir's Secret Sharing

File: shamir-1..png (76KB, 1600x1200px) Image search: [Google]

76KB, 1600x1200px

Hi everyone, it's interactive proof (>>8388303) guy here. I'll put "Kesari" in the name field in these threads for convenience.

Today I'll be talking about a (hopefully more accessible) topic called secret sharing. I will assume very basic knowledge of polynomials and algebra.

The idea is this. You are the president of your country, and you have the launch code for the nuclear missiles. But it's possible you might some day get assassinated, and no one else will know the codes.

You have a group of 20 advisors, and you want to give each advisor some information such that if any 15 of them agree that we should launch a missile, then they can obtain the launch code (15 in case a few go rogue). But if only 14 of them agree, then there should be no way for them to obtain the launch code, even by brute force (it should be as hard as if only 1 of them was trying to find the launch code). Thus the launch code is a shared secret.

Computers can be hacked so you want a mathematical way to do this.

Preliminaries. Attached is a picture of a line. I'd like to write down many lines, but drawing graphs for each one will take forever. Specifically, I want to represent each line by a few points that lie on that line.

If I give you one point, say (0, -1) that lies on the line, this doesn't help you know which line I'm talking about, because there are many lines that could pass through the point. But if I give you two points on the line, then you know exactly which line I'm talking about.

That's because you can just draw a straight line with a ruler between those two points and then extend it from there.

Refresher challenge: I'm thinking of a line that passes through (0, 1) and (2, 0). What is the line? You can either give it in slope-intercept form, 2-point form, or a graph.

Next up: polynomials.