Redirecting you to
Podcast Jan 16, 2023

Root Causes 269: Did a Patent Dispute Nearly Derail Post Quantum Cryptography?

On July 5, 2022 NIST announced its Round 3 PQC winners. What most people don't realize is that same day, the interested parties cleared a patent dispute that had the potential to prevent several of the winning primitives from moving forward. Join us as we explain who held that patent, what the potential impediment was, and how everything was resolved.

  • Original Broadcast Date: January 16, 2023

Episode Transcript

Lightly edited for flow and brevity.

  • Tim Callan

    Let’s take a little trip to earlier in history, the middle of 2022. There was a pretty landmark day in the world of post quantum cryptography and that day was July 5, 2022 and something big happened on July 5. What happened on July 5, Jason.

  • Jason Soroko

    Oh geez. My short-term memory and medium term memory is rusty these days, but you know what, the one thing from that era of time that comes to me is the NIST announcement. That was Round 3 I believe.

  • Tim Callan

    Absolutely. NIST Round 3, July 5, the day after Independence Day in the U.S. 2022 NIST announces that we have the Round 3 winners. Big day. Possibly the single most important day in the world of post quantum cryptography so far. However, what most people don’t know is that there was another very meaningful event that occurred on the exact same day, July 5, and in fact, that without that event the other event – the one you and I know – probably couldn’t have happened. So what I thought might be fun today is we would talk about that other event and what occurred and what the back story is and how that enabled the NIST announcement to occur on July 5.

    So one thing that was known, it was available to the public and if you were reading the right bulletin boards you could see it, but it wasn’t really big in the press or in the public research, was the idea of clearing potential obstructing patents.

    If you think about this, NIST ran this global effort to come up with these cryptographic algorithms that would survive and meet all of the court criteria that we needed and we’d be able to use them rolling forward and roll this around the whole globe. And people weren’t just coming up with these things out of the clear blue. They were building on work that had been done and in some cases had been done for decades. Where people were working on these things and trying to figure out these encryption methods and how would I break them and there’s a whole tradition of research and knowledge and papers that went into these original set of nearly 100 NIST candidates. One of the worries and one of the things that had to be cleared out was do people hold patents that will prevent us from using these algorithms?

    Because think about this: If I’m NIST, I’m not gonna declare a candidate as a winner for everybody to standardize on and it turns out that someone somewhere in the world holds a bulletproof patent and they’re gonna turn around and charge every single body in the world a nickel every time they connect to a website. That would be a non-starter and under those circumstances if you are running the program at NIST you would have to say, I can’t use this solution because I can’t have a system. It’s not economically viable. It’s not pragmatically viable to standardize on something if someone holds a patent that they could use to force, let’s say, every single technology vendor in the world to pay them a significant amount of money every year. Right?

  • Jason Soroko

    Yep.

  • Tim Callan

    And so this went on in the background and it didn’t get a lot of attention, n but it needed to happen and in the end of the day as the candidate pool was narrowing down it was narrowing down on a small number of lattice-based techniques and there was a worry. There was a patent from 2010. So the patent holders were the University of Limoges and the CNRS, which is a French governmental institution. What’s CNRS stand for Jay?

  • Jason Soroko

    In French, is the Centre National for Research Scientific, which is basically the French National Center for Scientific Research.

  • Tim Callan

    National Center of Scientific Research. That’s what it would be in English. And the two of these organizations held this joint patent from 2010 on what was feared to be one of the fundamental techniques in the lattice-based short list candidates and this was a worry. I’m gonna go so far as to say that I believe that NIST was not prepared to announce winners until this had been resolved and part of the reason for that is because it just makes common sense. You don’t want everyone to go work on something and at the end of the day they can’t use it. And the other part of it, of course, is what we talked about at the beginning, at the top of the podcast, the timing.

    So, on July 5, NIST announced their winners. The other thing that happened on July 5 is that NIST, the CNRS, and the University of Limoges signed a license agreement in which the second two – the CNRS and the University of Limoges – basically agreed in this context to make this technology available freely to the entire public without any kind of restrictions or limitations.

    Now they didn’t give up their patent. They didn’t walk away from their patent. They may use the patent in other contexts, but in this particular context they basically made the entire world free and clear for perpetuity to use this. And you think about, that’s really necessary. There’s no way that we can run a global PKI infrastructure without real clarity that we will be free of this kind of legal impediment.

  • Jason Soroko

    That’s correct. You know, Tim, I’m thinking about what you are saying and other echoes of this. There are other forms of encryption that could be or will be, should be, very important in the future. I’m thinking of things like homomorphic encryption – something that we’ve talked about on previous podcasts.

  • Tim Callan

    Yeah.

  • Jason Soroko

    You know, the ability to send up encrypted data into the cloud, have it worked on, you know, by a very scalable cloud system and have it never leave an encrypted state. It’s actually kind of magical in that sense but it’s just good math and there’s a lot of patents around that that stop it from being more widespread in use. We reported not that long ago about ISARA and you know, releasing or open sourcing the hybrid certificate concept and so there’s a lot of things out there. I’m not surprised about this with the post quantum work and NIST and the timing of the story we know that it took NIST an awfully long time for them - - you know, that July 5 date wasn’t their intended date I don’t think. They wanted to go a lot earlier and this really does help to explain what was going on behind the scenes.

  • Tim Callan

    I remember when I was at RSA seeing Dustin Moody on stage and someone asked him when you are gonna announce and he gave a very non-committal answer. He said, well, you know, it’s the government and governments gotta take government’s time to do government’s thing. And I think what he couldn’t say was we are in negotiation on this patent and we’ve gotta work this out before we announce winners. But that certainly appears just to an outsider – and I don’t know anything that you can’t just read on the internet – but it appears to me that that was specifically what was required and that’s what they had to come together on before they could move ahead and I don’t know if there was any compensation or not but either way, surely it was nothing close to we are gonna hold everybody in the world hostage between now and the end of time. And so, you know, that definitely looks like these patent holders to some degree chose the good of the public over their short-term ability to maximize profit and good for them. On the one hand, it's a government institution and a University. So if anybody is gonna be high-minded about it, you’d hope these would be the people. Looks like they were and I think they deserve some credit for that and at the same time, you know, it’s good that we did find ourselves in a situation where everybody can move forward with cryptography that we believe in. And otherwise, if they hadn’t been able to come to that solution one wonders if we’d still be waiting for the results today.

  • Jason Soroko

    It could be. Isn’t that scary but it could be. But I’m glad it got resolved and I’m glad we can tell the tail. So that’s great.

  • Tim Callan

    So there you are. Just a short story there but it’s interesting to understand and also I am sure this is not the last time in the world of cryptography and evolving cryptographic standards that the patent beast will rear its head because that’s always an issue that has to be dealt with, especially if you want to spread something out broadly, and if we are gonna standardize on it, it’s gotta be unimpaired. It’s gotta be something that’s unfettered and open and people can use it, and if there’s a patent in the way that’s a problem. So, anyway, that one is resolved and we are very glad and, you know, let’s move ahead.