Root Causes 235: What Is Lattice-based Cryptography?

Hosted by

Fellow

Original broadcast date

July 27, 2022

The recent winners of the NIST post-quantum cryptography contest are strongly focused on lattice-based encryption. In this episode we explain at a high level what this cryptographic approach entails and why lattice-based algorithms fared so well in the NIST search.

Podcast transcript

Lightly edited for flow and brevity.

TCTim CallanRecent episodes of this podcast have been occupied with NIST’s quite recent announcement of the winners of its post-quantum crypto contest. Go listen to those episodes for more details. As a reminder, the two main winners were Kyber for the KEM and Dilithium for digital signature. And what they have in common – we are told – is that they are both using a lattice-based cryptography approach. We thought today we would break that down and explain what that means.

Jason SorokoLattice-based cryptography. Tim, there’s a lot of ways we could go in this podcast and I’m gonna tell you guys upfront how I’m thinking we should go. I’m gonna try to make some of the brutally difficult math here at least seem a bit more intuitive because the people listening to this podcast are PKI practitioners. More or less. Depending on the use case, business use case, SSL certificates, S/MIME certificates, etc. We all have an extremely vested interest in making sure that we are able to keep our secrets, and so what we are really talking about here is what is the nature of a secret? How do you solve tough math problems? What are appropriate tough math problems that lend themselves to public key cryptography? And I think that even though very few people can really spell out on a chalkboard, on a whiteboard, what are the algebraic expressions of the RSA algorithm? What are the algebraic expressions of ECC? I don’t think that for the practitioners of PKI on a daily basis, those of you who work in the business world, I don’t think you need to be able to spell out all of those algebraic expressions in order to prove out that my S/MIME cert works.

But I do think though, that all of us as technical people, perhaps people with math backgrounds, people with just math interests, I think at the absolute very least one of the things that was good about RSA, one of the things that was also good about ECC, is that people were able to at least have an intuitive expression of what’s going on. What makes these things good tough math problems.

And I think that, of course, we’ve said this a few times in this podcast, RSA and ECC are both basically math problems that come under a similar category of the problem of factorization. And you are factoring different things, but they are factorization problems. In other words, classical non-quantum computers cannot solve these kinds of factorization problems in polynomial time, and that’s what makes RSA and ECC really great when you choose a big enough bit length, right, Tim?

TCTim CallanYeah.

Jason SorokoAnd so, to spell it out. I want people to be able to express this idea about quantum-safe algorithms. RSA is about factorization of large primes. ECC is about the difficulty of the factorization of solving for two points on elliptic curve.

TCTim CallanAnd in that sense, they are easy. Like especially RSA. Like if you had high school algebra then at the easiest level you can understand what RSA does. You get a ridiculously large number and you have to factorize it, which means you break it down to the basic numbers that multiply together to the get to that ridiculously large number and that includes some prime numbers that themselves are hugely large, right? And just figuring out what those are. Like that’s the math problem and we can all understand that. Now we can’t look at the formula written on a whiteboard and make sense of it but, you know, at that level, we can get it. ECC gets a little more math-y than that, but at the end of day it’s an elliptical curve. It’s build right into the name, and what you are doing is you are trying to find a point on that curve. Right?

Jason SorokoSure. But anybody who has ever seen pictures of what various elliptic curve parameters look like, it’s visual. Even if you don’t know any of the math at all, even if you didn’t look at a single algebraic expression, it’s at least visual. You can picture it.

TCTim CallanNow when we get to lattice, that ain’t a thing that I got in Calc, right? So, now all of the sudden, we are into a realm where I think a lot of educated people who are good at math just don’t know what these words mean anymore, and getting us there will help, I think.

Jason SorokoSo, I’m gonna put a few asterisks within this podcast, Tim, and not because there’s a disclaimer, it’s because there’s a takeaway. I’m gonna highlight when sometimes there is a simple takeaway for all of us in this talk. So, here’s the first takeaway, Tim.

Where previously people have been used to the algebraic expressions, the formula. People know what those look like. They are intimidating for non-math people, and they can sometimes be very intimidating to math people. There are levels of difficulty. Everybody has heard E = mc2. Right? A formula. So people are used to that and people certainly in the cryptographic realm are used to seeing algebraic expressions, formulas, that are just pure math that express why a problem is difficult and also, how to break down and solve the problem eventually because, you know, once you have a secret that’s great but once you want to exchange that secret, how do you decrypt something? There are formulas for that as well.

TCTim CallanSure.

Jason SorokoSo, I think, Tim, what we are talking about with lattice-based cryptography is that now we are entering the realm, we’ve chosen to go off and rather than using classical purist algebraic expressions, this is something I learned in math in university when I was living in that world, which is the world of matrices. You can think about it more as a geometric problem than an algebraic problem.

That’s a big takeaway, Tim. That we are moving away from classical formulas and moving towards something that computers really like, which is expressions in matrices. And when you think about a matrix, Tim - - think about a two-dimensional matrix. You know, if anybody has ever looked at an Excel spreadsheet, right, there’s columns and rows and if you were to choose one column and row and another column and row and draw a line between them, that’s called a vector, right?

TCTim CallanRight.

Jason SorokoAnd so for those of you who did any kind of matrix math in high school, in university; any of you who have ever taken any kind of course in linear algebra, you probably spent most of your time dealing with matrices. Probably two-dimensional, sometimes three-dimensional and believe it or not, you can have matrices of N-dimensions. Any number of dimensions you want, in fact. It can get very, very technical and complicated quickly but I think for these purposes right here, think of a matrix as simply being that set of points between the rows and columns. However you want to express it in your head. And those of you who are purists in math, you are probably cringing and going, no, that’s not exactly right. I know it’s not exactly right, but I’m trying to draw the picture verbally in people’s minds.

So, Tim, the reason why I say it’s geometric, more of a geometric based set of problems is because that vector is important to keep in mind. The vector is the expression from one point to another point along that matrix and it points in a direction. There’s an angle to it. There’s a directionality to it and it covers a mathematical space, if you will, and if you are doing it in two and three dimensions, it’s very easy to actually visualize that space in your mind.

So, lattice, if you just think about just that word, we are talking about a matrix. However, the reason why we are choosing the word lattice rather than just matrix is because we are already making hard parameterized decisions about what kind of a matrix we want. And so, therefore, we are talking about integers only. In other words, a matrix can have an infinite number of points in it. You guys who have done linear algebra, you know that. But with lattice-based cryptography, we are choosing to throw away all the infinite number of points between the integer points. So, you know, that sounds very math-y but, again, I think it’s more of a simplification in your mind of – think of a standard two-dimensional matrix and then just think of the integer points, you know, 0, 1, 2, 3, 4, 5. Kind of easy to note. And what’s interesting about that is if you only take the integers and you scale that matrix only by integers, all of the sudden you enter the realm of very tough math problems, and isn’t that interesting?

So, yeah, this is the basis of it, Tim. This is the real basis of, ok, why? Why lattice for cryptography problems? And it’s not matrices, it’s lattice and the only real difference between lattice and all matrices is we are choosing the integers only.

TCTim CallanAnd that’s simply to make solving them harder.

Jason SorokoTim, precisely. Precisely correct.

So, how do we make these lattices really tough math problems. Well, here’s another thought for all of you: There are a lot of tough math problems out there, but they’re only tough math problems if you parameterize them correctly and you make the problem large enough. In other words, if we stick with - - I don’t think that there’s any such thing as a two-dimensional or three-dimensional lattice used in cryptography. We are gonna be dealing with N-dimensional lattices. In other words, the one that I can think of in my head very simply is two-dimensional. If you really stretch your head, you can think three-dimensional, but the real stuff is gonna be in very high dimensions. Like 10,000-dimension lattices.

TCTim CallanGotcha. Can’t imagine that.

Jason SorokoIt’s very tough to imagine that and that’s simply to make the problem of solving for lattices just that much more difficult.

Ok. So, there’s also - - make sure that you also don’t choose a matrix basis, which is really the scale sum of, you know, a couple of factors that you are choosing. Make sure that the basis isn’t too simplistic or is expressed in one of the vectors that you are choosing. In other words, you do have to choose the vectors in your lattice carefully to make sure that they don’t overlap. Just simple mistakes that you shouldn’t make.

And another thing that you really have to do in order to make for tough problems in lattices is you can never allow multiplication by zero to any of the vectors. Otherwise, you just end up at the origin. That’s just too easy to solve.

So, the reason I mention these things, Tim, isn’t - -

TCTim CallanWait. So, all of those rules that are built into the algorithm, you are saying?

Jason SorokoYeah. Precisely. I’m only spelling out some of the rules. It’s just to extend your knowledge of alright, now that you got in a mind a matrix and now that you’ve got in mind a couple of vectors in the matrix and now that you have in mind, oh my God, sorry, Jay, you lost me now that you said 10,000 dimensions. I can only think in two. I’m now trying to say to you, yeah, but there’s a lot more to it as well, which is, because of the fact that the range of problem difficulty is from too overly simplistic to incredibly complicated, I’m telling you, here’s all the safeguards you have to take into account to make it so that it’s not too simple of a problem to solve because a matrix by itself can be extremely easy to solve. Even in your head. That’s how easy a matrix can be to solve, but it can quickly become unbelievably difficult as long as you follow specific rules.

So, Tim, I think what’s interesting and the thing I want to get to now is let’s really talk about things that you’ve probably heard about lattice-based cryptography, and I don’t want to make the connection just yet. I think we should do this in a future podcast but, for example, Kyber, right. CRYSTALS-Kyber and Dilithium, both respectively the KEM and Signature algorithms that were chosen to be standardized by NIST, there are many, many forms of tough math problems within lattice cryptography and so, therefore, there are more than one. The ones that were chosen by NIST so far, the two that I just listed, those are in and around the learning with error system of tough math problems. And I’ll describe that in a moment but there are others. There is the shortest vector problem, which is find the shortest non-zero vector in a lattice given the basis of that lattice. And we don’t have to understand fully what that means. I just want you to understand there is more than one math problem within lattice. Shortest vector problems, the closest vector problem, the bounded distance decoding, the covering radius problem and a very popular one, which is, learning with error.

So, let’s go through learning with error without frying our brains.

TCTim CallanLearning without frying our brains.

Jason SorokoLearning without frying our brains. So, if you think about, you know, draw out a matrix in your head here. Matrix – we are gonna call it A. And that’s a random matrix that is dimensionally n x m. Right? So, in other words, it’s a matrix. It has dimensions. Perfect. And that matrix in itself, Tim – here is something that is interesting. This is where I’m gonna try and connect it back to the real world. That serves as a part of a public key. So, in other words, that choice of random matrix, right, is in itself part of the public exchange.

TCTim CallanOk.

Jason SorokoAnd, obviously, in order to make this a learning with error problem to solve, basically, there are some things that you need to keep into account. In other words, the integer values need to be less than a value which is q and that q value is also public.

TCTim CallanOk.

Jason SorokoSo Alice and Bob who are gonna do business together are gonna exchange a secret. Alice chooses a private vector which is quite often in this called x. Each of its entries is either a one or a zero. Interestingly enough. Ok?

TCTim CallanOk.

Jason SorokoSo, Alice’s public key is essentially the multiplication of that full-blown random matrix – which is n x m – and her privately chosen vector. So, in other words, her public key. Basically, the choice of the matrix, the choice of this private vector, is multiplied together and you get this value which is often called U. And this U-vector is essentially the public key. So, in other words, you know what a is. You know what a is but you have to solve for x given this, and that’s really, really hard.

TCTim CallanThis has the qualities we are expecting from a public/private key exchange which is that result u, that public key can only be derived if you know x but you can’t use u to understand what x is?

Jason SorokoWell, this is the beautiful thing because now if you think about x = a x u, that has a quality of being a collision-resistant hash function. It’s very, very, very difficult to determine x and because of the giganticness of the matrix that you are choosing, basically, it’s not only very, very difficult to determine x and just solve for it, but also, as I say, it’s collision resistant meaning it would be very difficult even for somebody just to stumble upon it. And we have a lot of those properties actually in more classical cryptography within ECC and RSA the way that we create those more classical functions. Those also have collision resistant hash functions as part of how you solve for these problems. So, isn’t it interesting that even though we are now talking about essentially geometry, geometry expressions rather than classical algebraic expressions, these things also have been chosen very carefully in order to have collision resistant hash functions built within. And isn’t it interesting, Tim, that if you think about what I just said, these are new problems that are actually quite easy to construct. All Alice is doing is saying, alright, within this matrix that is known to everybody, I have to choose a private vector, and for people to know what that private vector actually is is incredibly difficult to try to determine. So, it’s even easy to say in words, and if I were in front of a whiteboard, I could actually show you what that would look like in two-dimensions and you’d go, huh, ok; that’s not that difficult. But the real math behind it is just vicious in terms of alright, how do we solve for this and that’s what makes a really good math problem. Easy to construct; easy even to describe; very, very difficult to solve.

So, basically, Bob now, right, he now takes two vectors – B1 and B2. These are both public and then he takes a secret vector. I love it; it’s quite often known as S. The secret random vector. Learning with errors is so interesting because there’s also this concept of an error vector and the beauty of these error vectors, and I think in order to be intuitively more interesting to people but thinking about this error vector is that it should be known to everybody playing this game that the error vectors have a magnitude that is very small. In other words, it’s close to the secret vector. And so, I think from here it gets almost a little too math-y except to say - - and again, this is where I’m gonna it a point. Here’s one of your takeaways.

Really what you are trying to do is anybody who is able to figure out (a) you know this public choice of a matrix – I should say a lattice because it is integer based. This randomly chosen matrix I think what you are really trying to solve for is a point on this matrix being asked to find the point on the grid that is close. So, in other words, Alice and Bob have just enough information between each other and the publicly-based information that would be to say, or available to say Eve, she has just enough to know the size of the matrix, where the matrix is, what the bounds and basis of the matrix are. She even knows for a fact that this error point is close to the actual point that’s been chosen as a secret, but the problem is that to actually solve for it even given all that information is actually very, very, very difficult. And this is the learning with errors problem explained extremely poorly without math. Basically, this combination of publicly chosen matrices and publicly given out information about chosen vectors but also secretly chosen vectors that are tough to solve for given what’s publicly available.

So, Tim, isn’t it interesting that a lot of this rhymes with things that we’ve known from the classical world.

TCTim CallanYeah.

Jason SorokoBut really, we are flipping the problems on its head and saying, yeah, but instead of factorizing based on prime numbers, instead of factorizing based off of points on an elliptic curve, we are now dealing with geometric vector choices that are literally the basis of your public and private secrets. And that is, you know, there is a lot more to go through with lattice-based cryptography but I think that’s about as far as you can go in terms of what is intuitively understandable just with, you know, words explained in such a way to think about, hey, it’s geometry, it’s points on a geometric shape and, you know, the basis of the secrets are essentially these tuples or vectors or whatever you would like to call them. Just points on a matrix.

TCTim CallanYeah. So, without trying to get into gnarly math that none of us is gonna understand, let me ask a couple of questions.

You said that there are multiple different lattice-based problems.

Jason SorokoCorrect.

TCTim CallanI guess it’s not a coincidence that both Dilithium and Kyber are built on the same one of those lattice-based problems. Is that a fair statement?

Jason SorokoThat is a fair statement.

TCTim CallanOk. Because for some reason, the nature of this particular problem is very well suited to what we are trying to accomplish here. Is that right?

Jason SorokoYeah. So, Tim, I’m gonna take a look at the ISARA website that describes the advantages of lattice-based cryptography and I’m just gonna read off some of these things, and there’s no secret as to why these were chosen. It’s because lattice-based algorithms are fast. So, speed. The key sizes are not super small, but they are reasonable.

TCTim CallanYeah. Giant keys.

Jason SorokoI think, Tim, also, they stand up to unbelievably heavy scrutiny. Also, you had talked in previous podcasts about well, you know, perhaps we should have other post-quantum algorithms as well simply because there is gonna be a diversity of use cases and which one you choose should really fit the use case. Well, the beauty of lattice-based cryptography is that it’s very suitable for a very diverse set of usages. And also, like the mathematical foundation and the understandability, the fact that we were even able to attempt a podcast to verbally go through what the basis of it is, those are all positive aspects to lattice-based cryptography.

TCTim CallanOperative word being attempt but yes.

Jason SorokoAttempt. I fully accept that, you know, those of you who really know this stuff will tell me I failed miserably.

TCTim CallanThere’s a group of people who are saying I have no idea what you are talking about and there is a group of people who are saying you have no idea what you are talking about and nobody else. Right. Exactly.

Jason SorokoJust to make this more interesting and more - - not more difficult but just more interesting. Keep in mind, Tim, even within lattice, we have different sets of problems and the proposed cryptographic algorithms that are out there are all based on one or more or some of those problems just within lattice-based cryptography, but keep in mind, there are other forms of post-quantum based cryptographies as well. I’ll name some of them off. Hash-based cryptography and isogeny-based cryptography are entire other categories of math that are not lattice-based and there have been proposed post-quantum-based cryptography based completely on completely different forms of math as well.

TCTim CallanAnd as we mentioned, at least one of the motivations of Phase 4 is having all of our eggs in this lattice basket and even though nobody thinks it’s gonna happen, what if it turns out that that basket has a hole in it. Right? So, under those circumstances, to have a different basket that we can throw our eggs in if I just want to really stick with that metaphor. And so, because they are the same and they are built on the same basic premise.

Jason SorokoWhat I will say is that Kyber and Dilithium - you know, I will call those out individually – let’s say you start doing a browser-based search on these things and you might to say to me, Jay, you said it was learning with errors but it’s not. It’s module- based or ring-based. Just keep in mind that these other forms of problems quite often are based on learning with error. So, before you google and say I’m immediately wrong, just keep in mind I’m trying to oversimplify to the point of keeping it down to what’s the root term? What’s the root math behind where Dilithium and Kyber are? Yes, there are some incredibly innovative cool new stuff that doesn’t even fit into the categories of what I’ve said but if you scratch the surface and you look at the math problems that those particular algorithms are based on, what you are gonna find are things that not just rhyme with learning with error but are simply based on it.

So, for those of you looking it up, that’s the level of oversimplification that I’ve just given you. There’s a lot to this.

TCTim CallanAlright. Cool. Well, there’s a lot to this. Props to you for taking what is an extremely difficult topic and getting to the point where at least I think I can go to a cocktail party and tell somebody who also doesn’t understand this some interesting facts, and I think that’s great. I think that’s a great level of ambition to set for this podcast. I think you did a great job, Jay. So, thank you.

Jason SorokoThank you, Tim. I think the real clincher is once you start talking about two dimensions, three dimensions, 10,000 dimensions, put that in your mind. Right?

TCTim CallanI know.

Jason SorokoThat’s where I think the sip of Jack and Coke will be needed to just try to digest that.

Stay informed with expert insights

Subscribe to Root Causes for engaging discussions on PKI, digital security, and best practices for protecting your organization's critical assets. Don’t miss an episode!