Root Causes 439: PQC Onramp Narrowed Down to 15 Candidates

Hosted by

Fellow

Original broadcast date

November 15, 2024

NIST has narrowed its PQC onramp contest to 15 candidates. We go over who remains and the makeup of the remaining candidates.

Podcast transcript

TCTim CallanSo the month of October saw an interesting announcement about PQC, post-quantum cryptography, from NIST. And this regards the onramp.

Jason SorokoSure does. We now have the list of the second round. And what's great about this, Tim, is it does seem to be quite varied in the math. We got everything from code-based, lattice-based, MPC in the head, multivariate symmetric-based, isogeny-based. I'm almost out of breath. And the list is growing, which is great.

TCTim CallanSo a little bit of background for the listeners. NIST, of course, ran its original PQC contest. They had three rounds. They came up with the four winners that we all talk about a lot – ML-KEM, MLDSA, etc. They continued on a round four, which will probably give us one additional winner that we can add, which we may hear about, may still hear about this year, although the year is getting near the end. And then in 2022 NIST started up - I think it was ’22 - NIST started up what they called the onramp, and that was a way to get other forms of PQC algorithms into the consideration set. And the main thing they were looking for with the onramp was to diversify. There was so much lattice that the worry was, what if some heretofore or so far, completely undreamt of technique gets thought of by somebody, and lattice becomes kind of just fundamentally untrustworthy. And under those circumstances, all of our eggs are in the lattice basket. And so, we need some other baskets for eggs. And so that was the real motivator, was to try to get other kinds of math, as you say, in there as the basis.
So there was an announcement in October, and I think the number is 15. Let's do a quick count, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14. By my count, 15 algorithms of the original - little over twice that - have gone on to the next stage. So with that background, you were saying, you were pointing out, Jason, that there's a lot of variety in here in terms of the math.

Jason SorokoI'm really impressed. There's at least 1, 2, 3, 4, 5, 6. There's at least six different mathematics basis with it that I'm counting in here, Tim. And there's quite a few in some of them. Like right now, under lattice-based, we have Hawk, which I think you've got a few words you want to say on, but I'm very interested to see that we do still have one isogeny-based SGI sign in there, which is interesting. So wow. We are starting to see diversity, Tim. I think that's the big message here.

TCTim CallanYou and I were told by Dustin Moody, who, of course, is running this effort that he was focused on isogeny-based encryption for his PhD thesis, and that he feels fundamentally that isogeny-based ought to be a solid approach.
And so, when we see that there, we know that Dr. Moody is quite up to speed and quite schooled on that particular technique. So seeing isogeny there you feel good about the fact that that has been properly considered and properly vetted. The other ones - so there's two in code base, and one is called Cross and one is called Less. There is a single lattice-based left, which is Hawk. We should return to that. There's a symmetric-based one called - how would you pronounce that? Feast? Faced? It's spelled F-A-E-S-T. So I'm not sure if we're going to call it Feast. Maybe Faced. MPC in the head has six algorithms moving on.

Jason SorokoVery interesting to get that non-interactive, zero knowledge, arguments of knowledge based any of this zero knowledge type of cryptography, Tim, this is something I think we need a few podcasts on to explain what the underlying concepts are. But wow, this is not something I expected to see this early on really take a lead. I thought that a lot of these might get booted. But here we are very, very strong representation from the zero knowledge based stuff.

TCTim CallanAbsolutely. And I already warned you of this in the past. If you started to geek out on this, I was gonna accuse you of having MPC in the head. So I have now done that. Like you said, there's one isogeny space that's called SQI sign and then multivariate has 1, 2, 3, 4. So also, a lot of candidates have survived in multivariate, although I'll point out the interesting thing. If you say okay, MPC in the head six, multivariate four, those seem very close to each other. The thing to bear in mind is there were only seven candidates originally in MPC in the head. So if you look at the survival right there, it's incredibly high.

Jason SorokoThat was surprising.

TCTim CallanAnd then there were a bunch that were just kind of called other which were entirely other techniques that didn't fall in any of these groups. Those have all been eliminated. So it doesn't mean that those are necessarily not fruitful paths for cryptography, but those are not going to yield a standard as part of this exercise.

Jason SorokoExactly. Now, Tim, it seems like acronym soup or something, I think I want to go right back to first principles here, in terms of what we're saying, is this second round seems to be very, very still rich in mathematics diversity. So we're going now into future rounds with a lot of different a lot of different math out there. And I think, Tim, we've talked about lattice in the past, obviously. We had a couple of episodes where we explained what the underlying basis of lattice is. We've had a few episodes where we talked about some of the failures in the implementations of isogeny and the fact that the underlying math, was not the problem. But I would like to have an overall episode where we talk about what is the fundamental problem underlying each of these math types.

TCTim CallanI would like to do that. I think the lattice episode that you and I did was well received. I think our commentary on the fundamentals of RSA and ECC have been well received, and that is something we definitely want to do. I agree that's important.

Jason SorokoSo let's plan for that. And I think for those of you who are tuning into this and you're very curious about the NIST process, I think it's just as important to understand the diversity of math that's coming here, because that really is the story coming out of the second round.

TCTim CallanSo you and I have had Dustin Moody on the show, and we've asked him about the onramp, and his take is that you should expect to see not a lot, like at most, a few algorithms coming out of this. And I think that has to do with the fact of, just like, how many of these things can we build out, because every one of them requires work. It requires a standardization process. It requires scrutiny, and then if it's going to go out and be used in the world, it has to be very thoroughly vetted, and it has to be implemented correctly, or those are potentially vulnerabilities. And as we've seen just with the ones we've had, we've seen things like Raindro and Psych fall very late in the process. We've seen implementation errors with existing algorithms, where the algorithms were fine, but the way they were implemented, left side channel attacks open. All of that stuff has to be vetted. And every time you add another algorithm, you're adding to the work that's required to make sure that our holistic cryptographic systems are solid and reliable. And one of the benefits we've had by being so focused on just two algorithms, RSA and ECC, is the concentrated effort on those was much more than we're gonna get in the new world. So for that reason, NIST doesn't really want to spring another six of these on us.
So we should only expect two, at most three, to come out of this, and as few as zero if none of them is cutting the mustard. And I think that's, that's what we should kind of expect to come out of this at the end of this process.

Jason SorokoExactly right. That's what Dr. Dustin Moody told us, and I'm really, really glad to see the diversity here. I'm really glad. I am very interested to see how this will progress but we're starting from a very interesting base at the moment, and I think our homework, Tim, is to really help the audience to understand what the underlying basis is for each of these, beyond just lattice.

TCTim CallanI think so. I think so. I think so. Now, do you want to talk about Hawk a little?

Jason SorokoLet's hear it, Tim.

TCTim CallanSo Hawk is a lattice-based strategy. And of course, as I mentioned, the point of the onramp is to get other strategies in there. So we asked Dr. Moody about this. We said, how come there's a bunch of lattice-based strategies? And there were a bunch. There were like - let me look at the list. There were 1, 2, 3, 4, 5, 6, 7. And he said, people submitted lattice-based strategies and we said, fine. You may submit them if you'd like. And so they didn't go out, they didn't ask for them. They didn't seek them. Hawk, as the name may imply, is intended to be a better version of Falcon. The group that submitted Hawk considered Falcon and what had been discovered in the process of examining it and felt that it could be done better. And we see this in NIST’s write up. In just a little bit, they have a write up on each one of these algorithms in their paper. So I'm just going to quote a little bit from the bit about Hawk. “NIST has chosen to keep Hawk under consideration because of its strong performance.” So that is really the gist of it. They go on to say, however, the security arguments for Hawk are not as well studied as those for Falcon, etc. So, where they're going with this is, look, Hawk might turn out to be like Falcon, but better. And under those circumstances, maybe we'd rather use Hawk than Falcon. Why not? It's better. And that's also something that Dustin said to us when we talked to him. He's like, look, if they give us a better lattice- based algorithm, we would be remiss not to consider it. But the other thing he emphasized, it would have to be a lot better, because, if it’s just a little better, the cost of giving up what we have now, and switching isn't worth it. And so apparently Hawk is good enough that it's still alive. I think it's unclear if it's going to get over that bar, and if it does, I think it's unclear what happens with Falcon. Does Falcon go away? And I will point out that Falcon does not yet have a released FIPS standard associated with it. So at this point - and I don't have any inside information - I look at it and I wonder, is it possible that how Falcon gets delayed while we figure out if Hawk is what we want to use instead? So, those are still some questions in my mind that we'll want to see what happens.

Jason SorokoI think, Tim, I'd like to start reaching out to some of the authors, some of the people who are on the working teams of these schemes, because a lot of times these folks are very passionate about the reasons why they are pushing these, some of these alternative methods. And I think part of the story you're going to hear - I don't want to put words into people's mouths - but I'd like to verify this question, which is, I think we've had enough time pass since the original first round, going way back X number of years, and there have been Eureka moments. In other words, the amount of work that's been done and the amount of really beautiful collaboration that's happened between certain types of groups, and this whole NIST process has yielded for us just better thinking. And enough time has passed, the people have developed that better thinking into this on ramp set of rounds. And I'd like to hear from some of the authors as to what some of those interesting Eureka moments have been. I think the devil's in the details here.

TCTim CallanAbsolutely. Of course, the devil is in the details. 100%. And so this is going to be just interesting to follow, just like the first process was very interesting to follow and just try to watch to see which of these mathematical schemes makes it or not. Like I'm hopeless at the math behind this. So I just have to trust what other people tell me. I don't have that level of understanding of the mathematics. But just as a person who knows how the standards process works, seeing so much MPC in the head make it through is really interesting. You just have to say, boy, does that? Does that mean that MPC in the head looks like it's the strategy at the head of the class right now? Also, if you think about this idea of absolutely not more than three of these and even that would have to be justified to being a much more likely number making it to the end, and if you think about the basic idea here to have a diverse set of strategies, it's hard to imagine that more than one of these MPC in the head strategies moves on. So there's going to be a brutal process of cutting the six down to one, because they're going to want to get other things in other fundamental mathematical strategies. Because if you now come out with three MPC in the head strategies, you haven't really solved your problem. I mean, you've got two baskets instead of one basket, so it's twice as many baskets but wouldn't you rather spread it out and have something code-based, and something multivariate and something MPC in the head, or something along those lines, where you're really diversifying your approaches. And so you think that those are going to have to get cut down pretty harshly in the next round.

Jason SorokoI think that as many of these as that has survived into a future round, I'm sure that somebody within that team, those sets of teams, know which are the ones that will probably move on. But the fact that we have so many, Tim, you thought the US elections were going to be interesting, I think that what moves on to the next, next round is actually going to be even that much more interesting. This is great stuff, Tim.
I am really happy with this NIST process. I think we've got a fantastic diversity. The process is doing exactly what it should, and I'm really thankful for it.
The transparency is terrific. The global community involvement is terrific. We really, like, honestly can say that we have the best of humanity working on this. And how rarely can you say that? So this is good and at the end of the day, it's easy to imagine us having some other alternatives that are, even if they're not in common use, that are ready to go so in the event there's some kind of major catastrophic failure of the lattice approach that the world can switch over without it being an eight year process again.
Stay tuned. This is an ongoing process, and we don't get these drops of information too, too often, but when we do, we like to cover them.
I am really happy with this NIST process. I think we've got a fantastic diversity. The process is doing exactly what it should, and I'm really thankful for it.
The transparency is terrific. The global community involvement is terrific. We really, like, honestly can say that we have the best of humanity working on this. And how rarely can you say that? So this is good and at the end of the day, it's easy to imagine us having some other alternatives that are, even if they're not in common use, that are ready to go so in the event there's some kind of major catastrophic failure of the lattice approach that the world can switch over without it being an eight year process again.
Stay tuned. This is an ongoing process, and we don't get these drops of information too, too often, but when we do, we like to cover them.

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!