NIST’s Post-Quantum Cryptography Program Enters ‘Selection Round’

I think McEliece and Sphincs+ are both excellent applications for typical PGP use cases-- and have great security properties. Their weaknesses don't matter as much in low throughput applications.

(e.g. McEliece's slow key generation is a big problem when you're creating 1000 connections per second and want good perfect forward secrecy. It's a non-issue for a long term key that is rotated at most once a year.)

I'm sad that sphincs+ is only an alternate.

Things like software signing and human scale communication don't care if signing is somewhat slow and the signatures are long-- but they do have extremely long lived keys that are difficult to rotate.

The problem with classic mceliece is the size of the public keys, which is measured in megabytes

> All of Bernstein's submissions (except the joke one) are in the finalist or in the alternative list.

What was the joke one?

I have heard that too, but us it really a big deal to have 65KB+ keys these days?

I hope it makes it through the selection. Either way i'll be using it.

This is the 3rd round, not the second.

Of course, NIST compliance is a circus.

I use it as a list of what not to use.

Once a senior cryptographer in Citi's R&D lab was grilling me on my use of 25519 being without NIST's blessing. I asked him what he would use, he said, "cryptographically speaking 25519", Ok.jpg.

RSA isn't that easy to understand. It's a trap: it seems simple on the surface because the core mathematical operation is easy, but the actual complexity (padding) often gets omitted.

RSA-KEM (key encapsulation mode) is easy. There's no padding, the only thing is you can't encrypt a message, only a random number < the modulus. Then you run that number through a Key Derivation Function (KDF) and use it with an Authenticated Encryption with Associate Data (AEAD) cipher. That's just simple enough I'd teach it to high-school students.

RSA encryption is hard. It requires OAEP padding, which is by no means simple. I'd not try to teach it to high-school students.

RSA signing is hard. It requires PSS padding, which is by no means simple. I'd also not try to teach it to high-school students.

Every other use of RSA is insecure, often in very subtle and hard to understand ways. Using RSA as a teaching tool about public-key cryptography does a disservice to students, since they (like you) tend to think that RSA alone is useful for cryptography.

And if you can treat an operation like the padding as a "black box" and ignore understanding, then you can understand code-based cryptography the same way: treat the code as a black box, and the math is very simple.

You can intuitively reduce RSA to model problems that you can do by hand, or trivially implement it in Python, but it's debatable how much your intuition is actually serving you; do you really have your head around why RSA works, what its limitations are, and how it can be applied? I think you have to get that through careful study, not from the kind of "machine sympathy" you often acquire through implementing algorithms and systems code.

In reality, most programmers cannot implement RSA safely without much difficulty; the opposite thing is rather the case. There's a reason the term "schoolbook RSA" has the connotations it does.

Because post quantum crypto algorithm are based on completely different breed of hard problems. Lattice problems and they are not straightforward to visualize as we were with RSA. Visualizing a lattice of large dimension, calculate its shortest vector or various other properties is not straightforward.

My bachelors was in Math and my master thesis was about lattice problems and post quantum cryptography. For my Ph.D. I switched to completely different subject because I couldn't write good papers in this area. So I understand your concern.

I am actually not sure if this isn't more of a problem of RSA than a feature.

I have seen many simple introductions to some cryptography that try to explain RSA. The problem is: They're almost always wrong and explain some insecure variation of RSA. (Most of the time they talk about a "Message" as the input to the RSA function without ever explaining the concept of padding and why this is important in RSA.)

The thing is: Implementing some form of RSA is relatively easy. Implementing RSA in a secure way is far from trivial.

I think it's likely that your understanding of RSA is mostly fake. E.g. You could do some totally insecure 'RSA' on paper, but it would be insecure.

Eventually people will write intuitive explanations of other algorithms (it's fairly easy to do them for sphincs+ and mceliece, for example) and you'll feel you understand them too. (and, in fact, I think those understandings will actually be less dangerous than the RSA ones!)

> with a bit of work I'd expect almost any programmer to be able to implement RSA without too much difficulty.

Implement RSA incorrectly without too much difficulty.

You should be dubious that even world class cryptographers will get it totally right, as many RSA implementations -- even ones written by experts-- have had serious flaws.

Would you consider elliptic curve cryptography conceptually difficult? It's certainly more complex than RSA, but over time great educational resources have been developed. The same will happen for these post-quantum schemes.

Lattice based cryptography can actually be made pretty accessible and can be taught to highschoolers and fresh undergraduates (I have done this with students at my job) as long as you give them a couple of math tools they may not have: matrix transforms, Gaussian distribution, vector dot product, and the one time pad. While this is a longish list, none of the topics are particularly hard and are accessible. I'll take a crack at an explanation (with schoolbook Regev-like LWE) and you can let me know how I did. It is better with pictures and probably can be shaped over the years, but I do think that people can adapt this explanation to turn it into something as easy, if not easier, than RSA.

1. Start with a random (secret) n-dimensional vector, s, that lives on a lattice (a square grid like pattern). This is your (small) secret key.

2. Hit that vector with a randomly generated matrix A (written As for multiplying matrix A with vector s), which basically just scales, skews, rotates, and projects that lattice into m-dimensional space (we want m to be much bigger than n). For those in the know, the new vector, As, is almost a "psuedorandom", "random looking", or hard to predict value. This is a way of taking your small key and turning it into a large key.

Intuition: Note that each component of As is basically an individual dot product. On a simple level, you can think of the dot product as a generalization of XOR, parity, or something that creates a checkerboard pattern using that lattice. This basically creates a high dimensional grid (lattice) with many colors that alternate. The end goal is to get some samples of these colors and reconstruct what the grid pattern looks like. If you have tried to learn a checkerboard (XOR, parity) pattern with a linear classifier, you know that this is hard. Here, we are generalizing this concept into something even harder.

3. Add (Discrete) Gaussian noise to As to get As + e. This is just adding "small" random noise to each of the components. You do this is to turn the almost "random looking" large key into an actually "random looking" large key.

Intuition: The reason for doing this is that if you have A and y where As = y, you can solve for s using Gaussian elimination. This is equivalent to the process that gradeschoolers use to solve systems of equations with multiple variables (where they subtract one row from another or solve then substitute variables).

Turns out that Gaussian elimination and other algorithms suck bad at getting the right answer if you have noise or small sources of error. The process gets thrown off wildly and gets no where close to s. The situation is so bad that even quantum computers are assumed to not be able to do it. This is what makes your large key resistant to being reverse engineered by powerful computers.

4. Use your As + e as a one time pad. To encrypt a message m, your ciphertext is the pair A and As + e + m. To decrypt, someone takes the key, s, computes As, then subtracts that off. This leaves you with m + e.

5. Decryption in (4) is bad because the small error, e, is leftover. This makes the process noisy and makes you lose a little information when you encrypt or decrypt. You fix this by using a noise correction encoding that makes the e go away.

Your new ciphertext is (A, As + e + encode(m))

EDIT: Note that to make this actually secure you need to pick good parameters for your lattices and your noise distributions. If your error is too small, it wont fool attacks and is easy to solve. If your error is too large you cant decrypt. The problem is easy unless you are in high enough dimensions (for instance, LWE is easy in 2 dimensions, which is what we use to visualize things).

It's entirely possible that QC will arrive but will be more of a special purpose accelerator for certain algorithms (think of the way custom ASICs can accelerate specific operations) rather than a general purpose thing. Some form of general purpose QC may happen eventually but that might take quite a bit longer, and it may take longer still for it to be commonplace.

In the meantime there will be a strong need for classically computable cryptographic algorithms that are strong against attack by any known quantum computable algorithm.

Symmetric encryption (AES, ChaCha) and hashing (SHA, Blake2) are mostly safe as long as at least 256 bit keys are used and the algorithm doesn't have weaknesses that QC might open wider. Asymmetric encryption based on conventional Diffie-Hellman, RSA, or elliptic curve methods is absolutely not safe. There are known quantum algorithms that on paper can crack them in reasonable amounts of time if you have the right type and size of quantum computer, and at this point we have reason to believe that such a quantum computer can probably be built.

Post-quantum cryptography efforts are about developing asymmetric encryption (key exchange and signatures) that can be computed on a classical computer but for which there are no known quantum attacks.

The biggest danger by far is that somebody figures something out and builds such a quantum computer in secret, allowing them to snoop on all kinds of secret communication and steal vast amounts of money before anyone figures out something funny is going on. Unlike an atomic bomb or a new kind of aircraft or satellite, such a quantum computer could be built and operated without creating physical effects that anyone could see at a distance. Unless somebody talks it could remain secret for quite a while.

> be a lot of development of new algorithms based on whatever that computer can do.

This whatever should only change the performance by constant factors.

In theory, cryptographic algorithms give the defender an exponential advantage against the attacker, so any small constant factor can be overcome by adding a few bits of security margin.