5
$\begingroup$

I'm trying to find a simple way to explain M of N keys to end users, where 2 keys would unlock something.

So far, all I found was this complex example where the key threshold was 1 (just one key of any lock will unlock this):

Photo of physical locks implementing solution with key treshold of one.

Larger version here.

Lacking any commonly accepted illustration, or image, is there any visual way to express M of N keys (Shamir Secret Sharing)?

$\endgroup$
  • $\begingroup$ I would suggest researching visual secret sharing, there you can find examples which are really easy to grasp without any numbers at all. $2,2$ VSS schemes are quite simple, and then show how to go to more general $k,n$ schemes. You probably won't find a proper illustration for arbitrary $2,n$ schemes. $\endgroup$ – tylo May 4 '17 at 9:57
  • $\begingroup$ If you want other examples then I link some in an answer on the puzzling stack. $\endgroup$ – Peter Taylor May 4 '17 at 14:30
2
$\begingroup$

I've used the following a number of times in lectures, and it always goes over well with a technical audience.

  1. I start by asking them How many points do we need to uniquely define a line? The answer I get back is always 2.

  2. Next I ask If I give you a single point in the X,Y plane, how many lines can you draw through that point? The answer I always get back is infinite.

  3. Finally I say, Let's consider I have some secret (usually I use 42 for the obvious reason) and I want to share this secret with many people so that any two of them could get together and reconstruct the secret.

At this point, depending on the audience, I will either ask how I could accomplish this, hoping they get the idea to somehow encode 42 into the line (e.g., as the y intercept). Or, I will just tell them how it works.

All of this can be shown visually, which I would try to add pictures here, but I don't have time at the moment.

For even non-mathematical audiences, if I start with #2 above (draw a point on the board or in a slide and ask how many straight lines can be drawn that pass through this point), it works well. Then I move to #1, then #3.

| improve this answer | |
$\endgroup$
0
$\begingroup$

I think I misinterpreted the question. This answer describes how to visualise the cryptographic working of threshold schemes. It is not really good for visualising the idea of these kinds of schemes to laymen.

I think the best way to explain Shamir secret sharing is by using graphs. Most readers will have a basic understanding of low-order polynomials, so you could do something like this:

Share creation

Let us explain a simplified form of Shamir Secret sharing with $5$ shares and a threshold of $3$. We will pick our secret in the range $0 \ldots 50$ (modulo $50$). I like the number $42$, so we will use that as the secret.

First we will generate a random polynomial of order $3$. This polynomial will be randomly generated, except for the lowest term, where we will fill in our secret ($42$). My random generator gave me the nice parabola $4x^2 + 25x + 42 \pmod{50}$. We will take this parabola and evaluate the five points with values of $x$ in the range $1\ldots6$.

Evaluating points on a polynomial

The exact values of these points are: $(1, 21), (2, 8), (3, 3), (4, 6), (5, 17)$ and $(6, 36)$. We will divide the points under the participants, and we hope they will keep them safe.

Note that the point $(x,y) = (0,42)$ is off limits, because this would reveal our secret.

Share combination

We'll say that the participants with the points $(4, 6)$, $(1, 21)$, and $(2, 8)$ want to use their shares to get the original secret back. Recall that we had used a polynomial that was in the form $a_2 x^2 + a_1 x + a_0$. So essentially, we only have to solve the following equation:

$$y = a_2 x^2 + a_1 x + a_0$$

Filling in the three points gives us the following system of linear equations:

$$ \left\{ \begin{aligned} a_2 4^2 + a_1 4 + a_0 &= 6 \\ a_2 1^2 + a_1 1 + a_0 &= 21 \\ a_2 2^2 + a_1 2 + a_0 &= 8 \end{aligned} \right. $$

Visualising this in a picture:

Three points describe a polynomial

Solving this system gives us $a_2 = 4, a_1 = 25, a_0 = 42$, a.k.a. the polynomial $4x^2 + 25x + 42$.

You may get actually get $4x^2 - 25x + 42$, but remember that the coefficients where defined modulo $50$, so this is equivalent to $4x^2 + 25x + 42$.

The participants remember that they encoded the lowest coefficient $a_0$ as the secret. So now they know that their original secret was $a_0 = \mathbf{42}$:

Filling in x = 0, gives us y = 42.

| improve this answer | |
$\endgroup$
  • 1
    $\begingroup$ Actually, I would suggest using a line (e.g. a polynomial of order 1), rather than a parabola. I would expect that "a line can be defined by two points" to be more intuitive to a nonmathematician than "a parabola can be defined by three" $\endgroup$ – poncho Jul 28 '17 at 14:41
  • $\begingroup$ I was thinking about a thresold $t = 2$, but I tought it would simplify the scheme too much. I could do a line $t=2$, and then stretch by saying "Lagrange interpolation allows us to expand this (...)"? $\endgroup$ – dsprenkels Jul 28 '17 at 14:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.