Someone calls you at work and says, “Don’t tell anyone, but…” If you are like most people, there are one or two people you will pass it along to with the same admonishment. In fact, they are probably repeating it from someone else, and you are on their list of two people. So for really big secrets, you need a way to spread the secret out so that no one has any real information about the secret, but a certain number of people together can decode it. As [neeaj] explains in a recent post about Shamir’s Secret Sharing, [Adi Shamir] (the S in RSA encryption) devised a way to do this very well in 1979, and the core concept is very easy to understand.
The explanation works with geometry. The equation for a line is y=mx+b, where m is the slope and b is the y-intercept (that is, where the line touches the y-axis when X is 0. An infinite number of lines cross the Y axis at, for example, 10. The line y=3x+10 does, and so does the line y=-1.41x+10. You can’t guess the b value from just the slope, because any slope will satisfy the equation.
So suppose the secret number is 10. I can pick a random slope and generate points on it. Like the y-intercept, any number of equations might satisfy that point. Let’s pick a random slope of 2 just to make the math easy. Our real equation is y=2x+10. Let’s pick a random X of 100 and tell one person their part of the secret is (100,210). That matches our equation, of course, but it also matches y=4x-190 and y=x+110, along with an infinite number of other lines.
To know the actual equation, you need at least two points. So let’s pick x=25 and tell another person that their part of the secret is (25,60). Now, if those two people compare notes, you can find the secret number by solving the two equations:
210=100m+b and 60=25m+b
The second equation is the same as 240=100m+4b, and you can subtract the first one from that:
30=3b
10=b
You can hand out any number of points to any number of people. Any two of them can recover the secret number. If you need to require more people to unlock the secret, you just go up in order. A parabola equation, for example, requires three points. A cubic takes four, and so on.
In reality, practical implementations take a polynomial, not a graph. But the elegant idea is the same. Not the first time we’ve heard of this algorithm. Reminds us of how a nuclear launch requires multiple keys.
Sort of like passkeys and oldschool college dorm room keys.
Collect a few impressions, get blank and files…
Do dorms have hotel style electronic keys (and electronic mamas) by now.
We’d have hated it.
Can they even pull off dorm room keggers anymore?
Cameras and all?
Will just encourage kids to move off campus quicker.
A few things in the design documents for that (follow the breadcrumbs) project look interesting. Glad I can read the Go written server parts, even if the Android/iOS apps… provide an growing security hole to my paranoid mind now.
(At least at first glance, ultimately, access to the museum is simple password protection – I admit I could be wrong)
Bookmarks the GitHub, and considers the ratio of stars vs watches.
Either way, I might spin it up on my staging/test machine and look deeper.
Look at the “value of zero days exploit by os”. Mobile exploits are the most expensive, due to the difficulty of finding one. That’s also the reason they make the news.
Project Zero guys focus there because it’s hard. Also, I suspect most Googlers use iPhones themselves (there are two types of people in this world, those with FaceTime….) and have MacBooks at work.
I’d have thought that like me, most people secrets are qualitative.
But if your secret is “42”, then good for you, you can use that to figure who you can’t trust. Although this method also assumes that those people know that they only know half of the secret and work together, so since communication is required, it isn’t really a secret.
A series of these could encode ASCII or ebcdic or whatever. This isn’t meant to show a practical implementation, just the concept which I think is quite elegant. Wish I had thought of it.
But say that your secret is a text file. If you treat the content as a huge integer number, then you could use that number as your B value. Then you create a random slope. Pick two values along the line and distribute them. And now the two people who have those value can recreate the content of your file.
Unless I am mistaken…
Of course those numbers will be quite large numbers too.
The qualitative/quantitative distinction doesn’t really hold up: the moment any secret is communicated, it becomes a message — a string of bits, which is just a number. So “the key is under the mat” is already quantitative the instant you encode it. Shamir’s method works on any bitstring, not just tidy integers like 42.
We use Shamirs Secret Sharing in a tool that requires 3 people out of 5 to come together to decrypt the upper-root password in case of an all-out disaster. So really useful to account for people being sick, on holiday or otherwise not present
The 2 main questions of interest to humans are “what’s the secret” and “who’s responsible”.
Two people can keep a secret if one of them is dead.