In the process of applying for my research fellowship, I had a phone conference-interview with the people there. One of the things that we talked about was about cryptographic schemes that distribute parts of data between, say, nodes, in a way that the data can only be read if at least, say, of those nodes come together; for instance, you have a bank with 10 managers and you, as the owner, don’t trust them enough to give each one of them a key to the vault, so you want to deploy a scheme that lets them open the vault only if at least 3 of them are present 1. Since long ago, I knew a trivial answer to this problem for 2, but adding to is not easy in my solution.
So I looked in my copy of Applied Cryptography book 3 and found a few solutions. Among the solutions two of them caught my attention, one by Karnin-Greene-Hellman that used Linear Algebra (and I’d love to write about in the future), and another one by Adi Shamir, hence its name, Shamir’s Secret Sharing scheme, that deploys polynomial equations and LaGrange’s interpolation algorithm, which I’ll explain in the next section.
Introduction to the Solution:
Shamir’s Secret-Sharing Scheme (aka. LaGrange’s Interpolation Polynomial Scheme)
The solution was to first generate a degree polynomial equation and call it . Now, as those of you who remember quadratic equations know, if I give you 2 points in a plane, you can give me a line — a first degree equation:
In the picture above 6 points from the line are shown, but only two of them are enough to find the exact equation of the line. Similarly, if I give you 3 points, you can give me a quadratic equation, or a degree 2 equation:
To generalize, if I give you points, you can give me a degree polynomial equation! Got it? Each share is a point in the graph of , and since is of degree , at least points — one for each of the key-holders — are needed to find the line — aka. the key! Sounds easy, right?
The Problem with the Solution
The problem is that a strong polynomial equation for this scheme have integer solutions, and of course, it’s hard to work with non-integers in computers; you know, floats are a mess! So basically I ignored this solution and only worked with the Linear Algebraic one; but little did I know about how smart the idea behind using this polynomial equation solution is!
The Solution to the Problem of the Solution (!):
Parallel Math Worlds (aka. Finite Fields)
Disclaimer: the following section is intended for non-math people; I’m a math major student and when I explain this idea to a math-friend I do it right, but hey, this is just a blog post!
Suppose we live in a world where the biggest number possible is 4! The ONLY numbers you can use are . We call that a finite field or a cyclic group of order five and denote it as 4. Now, let us say we live in this world; how do you think kids learn math in such a universe? First we need to teach them a modulo or modulus operator:
Let us define a simple division:
is the nominator, is the denominator, is the integer solution of division, and finally the one that we mostly interested in: is our remainder. Now we define modulo operator as:
Got it? Simple as that! So what else do they learn in school?
- First thing they learn is addition, of course:
- Then, in subtraction, in order to solve , we need to find such that:
Then we can say that:
And since we already know addition:
For instance, since:
We work out as:
- Next they learn multiplication:
- Similarly for division, in order to find , we need to find such that:
This idea of calculating the reciprocal of a number in is quite interesting for me, you’ll see why soon. Using it, we can say that:
Now since we already know multiplication:
For instance, since:
We work out as:
Note that not all numbers in a group are invertible. We’ll get to this later.
- Next big thing is exponentiation and finding e-th root. I’ll get to e-th root for $latex 2
I think that’s enough for now. For the record, this is what we call Modular Arithmetic in this world, of course, in the parallel world this is just normal arithmetics!
Let us see a wonderful application of everything above, shall we? Here is the question, solve the quadratic equation below: (yes, of course I mean in !)
Any ideas where to begin? Well, it’s actually not as hard as you think! In fact you can solve it exactly the way you would have done it in this world! Solutions of a quadratic equation are:
Just like this world! Except that we need to use modular arithmetic to find x. Enough talking, let’s work it out:
At this point you may say: “Wow! We are about to have 4 solutions!! Because has 2 answers in and we have two final solutions based on each answer of the square root!” (because of the ). I thought so in the beginning too. However, if you think about it, even when you are solving a quadratic equation in this world, the discriminant () always has two square roots: and ; but since radical is defined to always return the positive root, we have to put a to count for the negative root too. However, in our parallel universe, since we don’t like negative numbers, we add multiples of the group size to them so they become positive, and because of that, in the parallel universe, numbers can have two positive square roots! So technically we could ignore the and just try both square roots and that would give us both answers; so let’s see, in our example:
- First let’s try adding :
- Now let’s try subtracting :
- First adding :
- Then subtracting :
See? we have the same solution! Now for the other one:
Ta-Daah! Now that we have the two roots of the equations, we can factor it as:
Now let’s check them, just for the fun of it:
For my fellow math people: I found it very interesting that the proof of impossibility of a general algebraic solution to polynomial equations of degree five or higher — aka. Abel–Ruffini theorem — uses groups too and I finally gasped the importance of the Galois theory and Galois group! All thanks to a friend of mine, Amirali Moinfar.
Polynomial Equations in Parallel Math Worlds
Now why did I just spend an hour writing about a parallel universe 5? Because this is exactly the beautiful idea that lets us use the Shamir’s scheme in computers without being forced to mess with floaties! If I define my key polynomial in a finite field of order, hmmm, say, (which, by the way, just so happens to be a Mersenne Prime), then you can generate a key polynomial of any degree with points a 126-bit coordinate system 6. All done without touching any floaties in the process!
See? This is when you’ll need to know how to solve quadratic equations in the future!
I think that’s pretty much enough for this part …. In the next part I’ll talk about more applications of Finite Fields.
I chose Mathematics because at most (but not all) universities, the Computer Science major is designed to create computer *engineers* — yes, even in the ones that have two different majors one for engineering one for science, the courses are almost identical –, but I don’t want to be an engineer! We created computers, but for many people they are slowly becoming a new specie that we have to adapt ourselves with it rather than changing it the way we want. I want to learn about the algorithms and mathematical ideas behind them, potentially change them, not just learn Java and C++! And as a Math major I can do so!
Last thing I want to do now is to rant about how poor our education system is … because it actually turned out to be useful for me! It’s a hard thing to debate about; you see, I learned a lot of things that I know in the library of my high school. On one hand, I still find what I learned in school to be useful. On the other hand, I don’t remember a single exam that I didn’t spend the time I was supposed to be studying for it on reading some random book that I borrowed from the library!
One thing that I’m sure of is that I don’t rely on the formal education, but I don’t underestimate it either. For instance, why do you think Calculus is the first major math course in college? Because it’s [arguably] the easiest one! There is much much more [interesting] stuff in Mathematics than many people think there is and it’s sad to know that even many college students don’t have any clue about it!
- By the way, this is a simple (n,m)-threshold scheme; there are many other secret sharing schemes out there as well. ↩
- My solution was a basic secret splitting scheme:
Say, you want to split the key , first create a random key with the same bitsize, then you have . Now, give to Alice and to Bob. If they come together they can XOR their keys and calculate the original key as: ↩
- I haven’t read a lot of cryptography books, but I’ve heard that no other book even compares to this comprehensive introduction to cryptography. ↩
- In math books you may also find it denoted as or ↩
- That reminds me, maybe I can expand this later to write a math novel, like Flatland; I might call it “Finiteland” or something, I’ll see … ↩
- Ignore this, it’s just a reminder for me: think about how you can involve public-key cryptography with this … the polynomial is the master key which gives each person an X-coordinate that can be the private key and a Y that can be the public key … cool! I should think about it … ↩