Cryptography: I’m going to show how it’s possible for two people to have different private keys, and yet both be able to decrypt the same documents. Prerequisite: you should know that this is what a polynomial equation looks like: y = 4x^0 + 3x^1 + 7x^2 -3x^3, and you should be able to vaguely visualize such equations as graphs (in your mind or on paper). You should probably also be familiar with the term “private key”. I don’t want to get into its definition, but you can think of it like a password, or some other piece of secret information that one person has, and doesn’t share with anyone else. Summary: It’s gonna be an informal proof consisting of two steps: 1) Demonstrate an equivalence between data and polynomial equation and 2) Show how it’s possible for two people to “solve” equations despite having different information.

Motivation: Imagine that Alice and Bob both have their own private keys, and that there are 3 documents: Alpha, Beta and Omega. Alpha is is encrypted such that only Alice is able to read it (i.e. only Alice has the key which will “unlock” that document), Betta is encrypted such that only Bob is able to read it, and Omega is encrypted such that both Alice’s key can decrypt it, and Bob’s key is decrypted, but no one else in the world is able to decrypt it. How can this be possible?

Step 1: Equivalence between data and polynomials. Note that any file you can store on a computer is representable as a bit stream consisting of a sequence of 0s and 1s. You can take this bitstream and interpret it as a (binary) number. Thus there exist a computer file corresponding to the number 82099932. There exists another computer file corresponding to the number 92. In practice, these numbers are likely to be huge. For every megabyte your file consists of, the corresponding number will have around 2.5 million digits.

For every number, there exists at least one polynomial of any arbitrary degree such that the value of that polynomial at x = 0 is the given number. For example, if I wanted a polynomial of degree 0 to represent the file 82099932, I could use this one:

y = 82099932 x^0

If I wanted a polynomial of degree 1 to represent the file 82099932, I could use one of these:

y = 82099932 x^0 + 0x^1

y = 82099932 x^0 + 1x^1

y = 82099932 x^0 + 2x^1

y = 82099932 x^0 + 3x^1

…

And if I wanted a polynomial of degree 2, I could use any of these:

y = 82099932 x^0 + 0x^1 + 0x^2

y = 82099932 x^0 + 0x^1 + 1x^2

y = 82099932 x^0 + 1x^1 + 0x^2

y = 82099932 x^0 + 1x^1 + 1x^2

y = 82099932 x^0 + 0x^1 + 2x^2

…

I won’t prove it, but I’ll just assert that for any degree greater than 0, there are always infinitely many polynomials that could be produced such that the value at x = 0 will be some specific value.

I also won’t prove it, but I’ll just assert that if I tell you I’m secretly thinking of a polynomial of a specific degree N, and I tell you the values of the polynomial at N+1 different points, then you’ll be able to figure out what polynomial I’m thinking of. For example, if I tell you that my polynomial is of degree 0, and I give you 1 value of the polynomial (In this example, giving you 1 value is equivalent to giving you N+1 values, because N = 0), then you’ll know what the polynomial is. More concretely, if I tell you that my polynomial is of degree 0, and that the value of the polymonial at x = 32 is 82099932, then you’ll know the polynomial I’m thinking of is y = 82099932, because that’s the only polynomial at degree 0 which as a value of 82099932 at x = 32.

In contrast, if I tell you that I’m thinking of a polynomial of degree 1, and that the value of the polynomial when x = 10 is 20, then that’s not enough information for you to be able to figure out the polynomial. There are infinitely many different polynomials of degree 1 such that at x = 10, the value is 20. Here are just a few of them:

y = 10x^0 + 0x^1

y = 0x^0 + 1x^1

y = -10x^0 + 2x^1

y = -20x^0 + 3x^1

…

However, as soon as I tell you a second value of the polynomial, for example, that at x = 20, the value is 30, then you can immediately narrow it down to only one possible polynomial:

y = -10x^0 + 2x^1

Notice also that once you “know” the polynomial, you can tell me the value of the polynomial at any other point. So if I ask you what’s the value at x = 0, you can tell me that it’s -10 in this case.

Step 2: Application to encryption. Let’s say you have a file you want to encrypt. We saw earlier that you can transform any file into a polynomial of any degree you want, so let’s take the file and transform it into a polynomial of degree 1. That means that if you wanted to figure out what the polynomial was, you’d need to know its value at at least 2 different points in order to decode it. So one way of designing an encryption system would be to publish 1 of these points online (e.g. the value at x = 3282 (I picked this number randomly)), and keep the other number secret, as your password or private key (e.g. the value at x = 9238 (I also picked this number randomly)). Now, whenever you want to be able to access the number, you just look up the value online (which gives you 1 point), and then you use your secret knowledge of the second point, and bam, you’ve retrieved the polynomial. From the polynomial, you can figure out what it’s value is at x = 0, which gives you a number, which you can then turn into a file, and that’s the file that was originally encrypted.

Now let’s say Alice and Bob both want to have access to a specific file, but they don’t want to share keys with each other. All you have to do is generate an polynomial of degree 1 such that at x = 0, the value is the file, at x = 9345, the value is Alice’s key, and at x = 9284, the value is Bob’s key, and the value at x = 2883 is published online. All those numbers (other than 0) were chosen randomly. Since the polynomial is degree 1, you need 2 points to be able to “decrypt” it. Alice knows 2 points (the value at 2883 and the value at 9345) so she can decrypt it. Bob knows 2 points (the value at 2883 and the value at 9284) so he can decrypt it. The rest of the world only knows 1 point (the value at 2883), so no one else can decrypt it.

Note that if Alice knew that Bob’s key was the value at 9284, then once she figures out the polynomial, she can figure out what Bob’s key was. That’s why the fact that bob’s key is the value at 9284 should be kept secret. In other words, the private key is the entire geometric-point on the polynomial, both the x and the y coordinate, and not just the y coordinate at a given point. That way, even though Alice can compute the y-value of any point on the polynomial, since she doesn’t know what Bob’s x-value is, she doesn’t know which of the infinitely many y-values is Bob’s key.

Further reading: Note that I’ve talked about the decryption part, but glossed over the encryption part. In fact, with the scheme I explained, the person doing the encryption has to know everyone’s keys, as well as the original file. I.e. to create a polynomial that Alice and Bob can decrypt, that person would need to know Alice’s key and Bob’s key.

The reason for this is that the algorithm I described is a “symmetric key” style algorithm. You can design a algorithm such that Alice can encrypt a document that both she and Bob can read, without having Alice know Bob’s secret key. Such algorithms are said to use “asymmetric keys” or “public keys” (the two terms are synonymous), but that’s outside the scope of this blog post.