How to Let Everyone Keep a Secret

-

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.



from Blog – Hackaday https://ift.tt/mbZ7WI0

Comments

Post a Comment

Popular posts from this blog

Modern Radio Receiver Architecture: From Regenerative to Direct Conversion

-
Image
Modern radio receivers have a distinct advantage over the common early designs which I covered in my previous article . Most of the receivers you will have worked with over the past couple decades are designs by Edwin Armstrong ; regenerative, superregenerative, or most commonly superheterodyne. These are distinguished by a few fascinating key traits that bring both benefits and drawbacks. Today let’s dive into Mr. Armstrong’s receivers. I’ll also talk about DC receivers which, despite the name, are not made to listen to batteries. These are receivers you are much more likely to encounter in modern equipment. Regenerative and Superregenerative The regenerative receiver is all about doing more with less. You still see some of these in simple applications like RF remote controls. The idea derives from how an oscillator works. In a simple way of thinking, an oscillator is an amplifier with enough positive feedback that any tiny signal at the right frequency will amplify and then, throu...
Get this one»

Custom Macro Keyboard Looks Good in Wood

-
Image
There’s more than one way to make a mechanical macro pad, and this wooden wonder represents one of our favorites . [Tauno Erik] had an old rubber dome rectangle keyboard lying around that still worked, but the poor thing was missing some of its caps. After salvaging the controller, [Tauno Erik] got to work on the tedious task of figuring out the mapping of the matrix, which was made easier with a Python script. Almost every component of this beauty is wood, including the mounting plate and those thicc and lovely keycaps — their top layer is solid oak, and the bottom bit is birch plywood. In order to interface the ‘caps with the switches, [Tauno Erik] designed and printed connector pieces that sit inside the extra large keycaps and accept the stems of the key switches. Speaking of switches, we’re not sure if [Tauno Erik] ended up using Cherry green switches, browns, or a mix of both (that would be interesting), but each one is mounted on a custom PCB along with a diode and a pull-up ...
Get this one»

Build this Cyberdeck in a Cave with a Box of Scraps

-
Image
Desktop 3D printing has been a big enabler for the cyberdeck community, as it’s allowed individuals to create unique frames and enclosures which would have been far more difficult and time consuming to produce using traditional methods. But what if you don’t have access to a well-stocked workspace, and need to do your building with the bare minimum of equipment? In that case, [ALX] recently put together a minimalistic design that can be assembled with off-the-shelf components and basic tools. It’s the ideal cyberdeck for the neophyte, as all the parts are widely available and relatively inexpensive. While it might not be a customized as something with a fully 3D printed frame, we think it nails the look and utility that are the hallmarks of a proper deck. The key to this build is the SmartiPi Touch case, which puts the Raspberry Pi and touch screen on a hinged panel. These hinges happen to be compatible with GoPro-style mounts, so with a few extension pieces, the panel can be lifted...
Get this one»