The next step in the post-quantum cryptography project came last Tuesday when the National Institute of Standards and Technology (NIST) announced its first post-quantum standard algorithms, new encryption algorithms that will become the standard for protection against quantum computer attacks. The four algorithms are CRYSTALS-Kyber for general-purpose encryption and three schemes for digital encryption: CRYSTALS-Dilithium, FALCON and SPHINCS+.

On July 9, Dr. Dustin Moody, head of NIST's post-quantum cryptography standardization project, analyzed in detail the third round of selected algorithms and the basis for NIST's selection at the 2nd Yanqi Lake International Quantum-Resistant Cryptography Standardization and Application Forum and the 6th Asia Quantum-Resistant Cryptography Forum. What? The latest interpretations by NIST officials

193ab6f75b88c506366bc05177956c61

Last week, Moody was also interviewed by IEEE Spectrum magazine [1], and the following is a translation of the full article.

Q: What is a post-quantum cipher and why does NIST need a standardization process?

Dustin Moody: Researchers from different backgrounds have been working on building so-called quantum computers. If a sufficiently large quantum computer is constructed, then an algorithm can be run on that quantum computer that will crack several of the most widely used cryptographic systems that we implement and use around the world today. Thus, post-quantum ciphers are preparing new cryptosystems to replace those that are vulnerable to attacks by sufficiently large quantum computers. And NIST is doing this because some of the cryptosystems that we have standardized on, for example, cryptosystems that deal with public key ciphers, it would be vulnerable to attack. Therefore, we want to replace these standards with new standards that are less susceptible to quantum computer attacks.

Even if (high-performance) quantum computers do not yet exist, you may actually be at risk from quantum computers. This is often referred to as "steal now, decrypt later.

Q: As I understand it, now you're replacing two different things; both the key and the signature. Can you talk about the two and the difference between the two?

Moody: With cryptography, you need many different types of tools to protect your information. The first thing people think of is encrypting and scrambling your data so your enemies can't read it. This is usually enabled using public key encryption. Then you create a shared key that you will actually use as the key for another encryption system that allows for faster encryption, a grouped cipher called AES. But this public key encryption is used to create the initial key. So that's the first feature that we need to replace. The second is digital signatures. Instead of signing at the bottom of a letter to prove that you are the author, you can perform the same operation digitally using cryptography. This is also known to be vulnerable to attacks by quantum computers. So this is the second feature that we are trying to replace.

Q: The largest quantum computers today have about 200+ quantum bits, and they are not fault-tolerant. One of the largest numbers calculated by one of the machines using Shor's algorithm is 21. There are various estimates out there for the time it would take to crack RSA 2048, but you need at least thousands of quantum bits, and they all need to be very, very high quality. Why is there such a rush? Why are we doing this now? You started this process in 2016. That's probably years, if not decades, ahead of schedule.

Moody: First of all, it takes a long time to standardize cryptographic systems and then to apply them to products around the world. In our past experience, switching from one cryptographic algorithm to another can take 10 to 20 years. Since we need to do this before quantum computers are available, we have to do all the work ahead of time. And there is no rush. If the cryptosystem was invented two weeks ago, you wouldn't have confidence in it. We need experienced people to analyze these algorithms to have confidence in their security. That's one reason: it takes time to prepare. And then reason number two is that you can actually be threatened by a quantum computer, even if it doesn't exist yet. This is often referred to as "steal now, decrypt later". This is the idea that your enemies can copy your data that is encrypted, and they can get hold of it now, even if they can't read it now. But maybe in 10 years there will be a quantum computer, and then they can access your data. If the information you're trying to protect is valuable enough, then you're already in trouble because of that threat. That's another reason why we need to be ready for quantum computers well in advance of them being built.

Q: How realistic is it to steal it now and decrypt it later? I know it's a possibility, but is it really happening? Are people downloading data and storing it so that they can access it when their quantum computer is up and running?

Moody: I don't have access to classified material. nist is not at that level like the NSA and other departments. But the people I've talked to have said that it's definitely a threat and it's happening at the national level right now.

We're going to standardize things so that we have a variety of different mathematical problems to base our security on.

Q: The vulnerability of public key encryption is because quantum computers are eventually able to decompose large prime numbers at an almost exponential rate. What types of strategies are being used to create these new public keys? Can you describe a few of them?

Moody: In the crypto space, we like to use ideas that have been around for a while. Researchers have been working on this problem since Peter Shor's algorithm was discovered in the 1990s. Many solutions have come from all three families. The most popular one involves what's called a lattice (lattice), which is a mathematical structure where you take basis vectors, you combine them integrally linearly, and you can do some very interesting things with cryptography. There is no known quantum algorithm that does a better job than a classical attack on a lattice based cryptosystem. Lattice based cryptosystems seem to be the strongest contender in terms of key size and efficiency. It is therefore not surprising that we receive a large number of lattice based submission schemes. The second family is based on so-called error-correcting codes or code-based cryptography. These codes have been used in information security for a long time because data is sent over noisy channels. If you use error-correcting codes, you can interpret the error and recover the message that was originally intended to be sent. We use an idea similar to the dot matrix used in these codes. There, they seem to be only half a step behind the grid scheme in terms of key size and efficiency, but they are also quite good. So we see a number of code based submissions. The third big family includes some multi-variable ciphers based on the so-called signature schemes. You will use a large number of variables, x1 to xn, and create a system of quadratic equations. And while it's very easy to define and evaluate one of these systems, it's very difficult to solve. So it turns out that it works for digital signature schemes.

Q: Kind of like when you have a big wavy line on a chart? It's easy to draw, but it's actually hard to figure out what function is being used to plot it.

Moody: Yes, that's the idea of a lot of cryptosystems. One thing is one-way, if you know the secret, you can do that quickly and easily. This allows you to decrypt or sign. The attacker doesn't know the secret, they can't do anything.

Q: I have a general understanding of how you test classical cryptosystems, because we have classical computers. But we don't have quantum computers. So how do you verify that these methods are actually quantum secure?

Moody: There's no guarantee that really no one will come along and come up with some new idea. The same is true of the cryptosystems we use in classical computers today.

Q: Of course, I know that RSA is not that hard to prove.

Moody: When you add quantum computers to the mix, you can use more tools, you can use more quantum algorithms. The best we can say is that a lot of smart people spend time looking at these and no one finds any attacks and they don't seem to come close. These pathways don't seem to work at all. That's how we set up the competition - making sure we have experts in the field, spending years working on these cryptosystems, and making sure there are no attacks.

Q: So in the process, you've really narrowed it down from the initial selection to a few finalists. (Editor's note: Prior to the July 5 announcement)

Moody: Yes, we started with 82, and now we have seven finalists and eight alternates at the end of the third round, which will be over in a very short period of time, maybe a week or two, or we'll have standardized.

Q: What's the next step?

Moody: We will start writing standards. These will be the most widely used algorithms. We will also enumerate some algorithms and continue with the fourth round of evaluation so that we have some other algorithms. Because this is a new area of research, we don't want to put all our eggs in one basket, such as only the lattice algorithm, and then the attack comes and we have nothing else. We will standardize many things so that we have a variety of different mathematical problems to base our security on. We will start writing standards, which will take a year or two, and there will be some that continue to be evaluated and may be selected for standardization at the end of the fourth round.

Q: What is the difference between the finalist algorithms and the standardized algorithms?

Moody: Once we standardize these algorithms, people know that they will be widely used. There are already implementations available, but people will be able to focus on the standardized implementations. That's an important step on the road to adoption. The industry needs standards to really get widespread adoption.

Q: I understand that there are some patent disputes related to algorithms.

Moody: In the crypto space, most people don't like patents because they tend to discourage adoption. Companies don't like to adopt algorithms that might be patented. At the beginning of our process, all submitters have to let us know of any patents they have. We know that some patents do not come from the submitter, but from some third parties. nist has been negotiating with these other parties to negotiate a mutually beneficial solution. I think you'll see in our announcement that we're pleased with the results. We think these algorithms will be able to be widely adopted by people around the world.

Reference link:

[1]https://spectrum.ieee.org/post-quantum-cryptography-nist