Hey ! I’m sure you all have heard of good techniques of creating secret keys, and to encrypt secret messages. Here’s a fun one (idea by xor#4528)

# The Goal

We can create a polynomial function of degree $k$, with a y-intercept of $m$, our secret message. Then, we can give each person a “key”, which is a point on the graph, far from 0. To unlock the message, they’ll have to share $k+1$ keys to recreate the function, using the Math below.

# The Math

## Generating the Keys

Alright, we can write our polynomial of degree $k$ as:
$$p_0 * x^0 + p_1 * x^1 + … + p_{k} * x^{k}$$
We’ll then define our function $f$ as:
$$f(x) = \sum^{k}_{i=0} p_i * x^i$$
And we can systematically create one such function like:
$$\text{poly}: \lambda p . \lambda x . \sum^{k} _{i=0} p_i * x^i$$
Creating a function with a set of params would simply be $f = \text{poly } p$

Creating the message is quite simple, we just have to make $p_0 = m$, since all the other terms would cancel when calling $f(0)$, we’d only have our y-intercept left.

Generating random keys is as easy as calling the function on random values.

## Finding the Message

Now that you can generate any number of keys, you need to be able to find back the message. With $k+1$ keys ($(x, y)$ pairs), you can get back the original polynomial using a system of equations:
$$f(x_0) = \sum^{k} _{i=0} p _i * x^i _0 = y _0, \quad f(x_1) = \sum^{k} _{i=0} p _i * x^i _1 = y _1, \quad…$$
I’ll spare you the rearranging, but this can be solved using matrices. The $x$ can be put into a vandermonde matrix $V$, and the $y$ & $p$ can stay as vectors: $Vp = y$
Finally, we can solve this equation for the least-square error for $p$, and find back our coefficients, evaluate $\text{poly p 0}$, and get back our secret.

Yeah, it was a lot, let’s see how this looks when coded up !

# The Code

I’ll be using CF, as it’s my own language. (full code here)
Let’s start by importing some things, and setting up our data types:

Btw, we’re using Tensors here, since we’re juggling with Vectors & Matrices.

Alright, now, we can create our polynomials. Remember that fancy lambda function we had earlier ? It’s super easy to convert to CF, as it’s a FP language, we can replace the $\sum$ by a foldl, or >\.
This: $$\text{poly}: \lambda p . \lambda x . \sum^{k} _{i=0} p_i * x^i$$
Becomes this:

We can then generate polynomials as we wish, with whatever length for $p$, and with whatever message $m = f(0)$:

Here, <0?> helps us define the polynomial, without calling it, to store the function, not the result of what it’d compute. It can be considered as a placeholder.

Then, we can create this little code block used to get keys. It’ll generate random numbers $r$, and for each number $r_i$, return one key $(r_i,\quad f(r_i))$

Alright, we have the generation part, let’s now solve it with our keys !
As I said earlier, all we have to do is to solve lstqs ($\text{Least-Squares}$) for the equation $Vp = y$, solving for $p$.
Since we’re given $x$ & $y$, we just have to generate $V$ from $x$, which can be done easily (details not provided, as it’s just a range, but transposed, see full code), and plug that into a lstsq function.

For those of you who are confused, here, vandermonde_matrix n just specifies the size of the vondermonde matrix, since it can vary (which impacts precision). We chose $n$, to have $100%$ precision.

To finish, we can code a tiny function which will try to get the secret from a set of points.
$secret(P) = \text{poly} \quad \text{find_weights}(x, y) \quad 0$
which is a $poly$ with weights $p$ evaluated at $0$.
In code, it looks something like this: