Creating Secret Messages & Keys with Polynomials

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
2
3
4
import {lstsq} from "adv_math.cf"
import {Tensor, arange} from "ds.cf"

data Point = (Num x, Num y)

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
2
polynomial :: Tensor.1D, Tensor.Scalar ->> Tensor.Scalar
P, x => zip P [0..] >\ (y, (p, i) => y + p * x ** i) 0

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

1
2
polynomial_with_secret :: Num, Int ->> Random (Tensor.Scalar ->> Tensor.Scalar)
secret, n => polynomial Tensor.1D [secret, ... random_weights n-1] <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))$

1
2
3
4
5
get_keys :: (Tensor.Scalar ->> Tensor.Scalar), Int ->> Random [Tensor.Scalar]
f, n ~> {
f, n => f, Tensor.Random.rand KEY_LOWER_BOUND KEY_HIGHER_BOUND [n],
f, r => r @\ (x => Point(x, f x))
}

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
2
3
polyfit_weights :: Tensor.1D, Tensor.1D, Int ->> Tensor.1D
xs, ys, n => lstqs (_vm xs) ys
where _vm = vandermonde_matrix n

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
2
3
try_to_get_secret :: [Point] ->> Num
keys => polynomial (polyfit_weights xs ys keys.length) 0
where xs, ys = points_to_xy_tensors keys

And we’re done !