simple-threshold-encryption.md

A Simple Threshold Encryption Scheme

I have a secret number and want to construct a scheme where I can give away a "piece" of this number to my friends and any two of them can get together and reassemble the number. I also want to be sure that knowing only one piece of the secret, reveals nothing about its true value.

To do this, I construct a line who's y-intercept is my secret number. Say my number was $2$, the line would look like this:

The "pieces" of my secret are points along the line. I give each of my friends a point.

$$ Alice, Bob \leftarrow (1, 3), (-1, 1) $$

One point does not make a line, so any one of my friends can't discover the secret. In fact, infinitely many lines can be drawn between a single point and the y-axis, so one piece of the secret reveals nothing about the secret.

To illustrate this, here's a line that goes through Alice's point, but would encode a different secret than our earlier one one.

Two points do make a line, so both of my friends can get together to recover the secret by drawing their points and a line between them. The secret is the y-intercept of this line.

This is one version of Threshold encryption. A line is a degree one polynomial. Any polynomial of degree $n$ is uniquely defined by $n+1$ points, so to construct a secret that requires $N$ people to reveal, one can create a degree $N-1$ polynomial with the secret being the y-intercept, and give out at least $N$ points. If $N$ people get together, they can reconstruct the polynomial, determine the y-intercept, and decrypt the secret.

As an example, say our secret was the word "hello". Using ASCII, the word "hello" is encoded as a binary string 01101000 01100101 01101100 01101100 01101111. We can interpret this binary string as number, yielding $448,378,203,247$. So, to encode the secret "hello" under this scheme, we'd construct a polynomial with a y-intercept of $448,378,203,247$.

In practice, there are many ways to do Threshold encryption. If you'd like an advanced example Penumbra's is cool. This method though is valid, and might help build intuition for how something like threshold encryption could be possible.

This description is Threshold encryption is inspired by page 10 of Privacy and Verifiability in Voting Systems: Methods, Developments and Trends by Hugo Jonker et al. Thanks to readymellon for feedback and review.