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:

1 | import {lstsq} from "adv_math.cf" |

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:

1 | polynomial :: Tensor.1D, Tensor.Scalar ->> Tensor.Scalar |

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

1 | polynomial_with_secret :: Num, Int ->> Random (Tensor.Scalar ->> Tensor.Scalar) |

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))$

1 | get_keys :: (Tensor.Scalar ->> Tensor.Scalar), Int ->> Random [Tensor.Scalar] |

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.

1 | polyfit_weights :: Tensor.1D, Tensor.1D, Int ->> Tensor.1D |

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:

1 | try_to_get_secret :: [Point] ->> Num |