How Does Post-Quantum Cryptography Work?

TL;DR

Post-quantum cryptography replaces systems vulnerable to quantum attacks, such as RSA, with methods believed to resist quantum computers. The presentation identifies six candidate families and illustrates lattice-based cryptography through the closest-point problem, where a good lattice basis serves as the private key and a bad basis serves as the public key.

Transcript

Well, good morning, everybody. My name is Klaus Schmeh. Welcome to my presentation. I'm going to talk about post-quantum cryptography, and I'm going to try to explain post-quantum cryptography with cartoons. And for this purpose, I have invited a couple of guests. And well, for the beginning, let me introduce my first guest. Please welcome a, a qua... Read More

Key Insights

• A quantum bit is able to represent zero and one at the same time until it is read, at which point all but one state are lost. An eight-qubit register can therefore hold 256 simultaneous values, although only one value can ultimately be observed.
• A quantum computer is suited to performing many computations in parallel when the process produces only one result. The examples given include finding an element in a large set, identifying an optimal solution among many possibilities, and performing prime factorization.
• Sorting is not presented as a natural task for a quantum computer because the ordered collection contains multiple required output values. The entire sorted set must be retained as the result, which conflicts with the loss of all but one state during measurement.
• Prime factorization is the reverse of multiplying two prime numbers and is described as a one-way function. Multiplication can be implemented efficiently, while recovering the original factors from a large product becomes difficult for ordinary computers when practical numbers are used.
• RSA is vulnerable to sufficiently capable quantum computers because its security is closely connected to the difficulty of prime factorization. The presentation contrasts current attacks on keys of about five bits with practical public keys of 2,048 bits and warns that future machines may become stronger.
• Post-quantum cryptography includes six families believed to resist quantum computers: lattice-based, code-based, hash-based, non-commutative, multivariate, and isogeny-based systems. None was described as being in widespread use, but adoption may become necessary as quantum computing capabilities improve.
• A lattice is a set of intersection points created by parallel, equally spaced lines extending in different directions. The same lattice can be defined by different bases, including a good basis with nearly orthogonal vectors and a bad basis with nearly parallel vectors.
• GGH uses a good lattice basis as Alice's private key and a bad basis for the same lattice as her public key. The good basis makes closest-point decoding easy for Alice, while the public bad basis makes it difficult for an attacker, especially in 250 dimensions.

Questions & Answers

Q: How does a quantum bit differ from a classical bit?

A quantum bit can be zero and one at the same time until someone reads it. Reading the bit causes all but one state to disappear, leaving only a single observable value. The presentation compares this behavior with Schrödinger's cat, which can be described as dead and alive simultaneously until observation determines which state survives.

Q: What types of problems are quantum computers good at solving?

Quantum computers are described as effective when extremely many computations can run in parallel but only one final result needs to be read. Examples include finding an element in a large set, selecting an optimal solution when many possibilities exist, and performing prime factorization. They are less suitable when the complete output contains many separate values.

Q: Why are quantum computers not well suited to sorting?

Sorting requires the entire collection of ordered elements to remain available as the result, rather than producing only one value. A quantum register can represent many states simultaneously, but measurement causes all but one state to be lost. For that reason, the presentation says sorting is not a first-choice application for a quantum computer.

Q: Why can quantum computers threaten RSA encryption?

RSA is closely related to prime factorization. Alice uses two prime numbers in her private key, while their product is associated with the public key. Multiplication is easy, but reversing the process is difficult for ordinary computers. Because quantum computers are particularly good at factorization, sufficiently powerful versions could recover the factors and break RSA.

Q: Can current quantum computers break practical RSA keys?

The quantum computers discussed can break RSA only up to a key length of about five bits, while practical RSA public keys may have a length of 2,048 bits. This leaves a very large capability gap. The concern is therefore focused on future quantum computers that might become substantially more powerful, rather than the small demonstrations available at the time described.

Q: What families of post-quantum cryptography are discussed?

The presentation identifies six cryptographic families believed to be secure against quantum computers: lattice-based systems, code-based systems, hash-based systems, non-commutative systems, multivariate systems, and isogeny-based systems. None is described as being in widespread use. The session focuses more closely on selected leading approaches, particularly lattice-based cryptography in the available transcript.

Q: How does the closest lattice point problem support encryption?

A lattice can have a good basis made from nearly orthogonal vectors and a bad basis made from nearly parallel vectors, even though both describe the same points. In a 250-dimensional space, finding the closest lattice point is extremely difficult with only the bad basis but comparatively easy with the good basis. Encryption exploits this difference in difficulty.

Q: How does the GGH lattice-based cryptosystem work?

In GGH, Alice's private key is a good basis for a lattice, while her public key is a bad basis defining that same lattice. Bob encodes a message by placing a point near a lattice point in 250-dimensional space. Alice uses the good basis to find the closest point and decode the vector, while an attacker has only the difficult bad basis.

Summary & Key Takeaways

• Quantum computers use quantum bits that can represent zero and one simultaneously until they are read. This enables certain kinds of parallel computation, but measurement leaves only one readable state. Such machines are presented as useful for problems with one resulting answer, including searching, optimization, and especially prime factorization, but not sorting.

• RSA relies on the difficulty of reversing prime multiplication. Its private key uses two prime numbers, while its public key is related to their product. Practical public keys may contain 2,048 bits. Existing quantum computers can only attack very small examples, but more powerful future systems could threaten RSA and motivate alternative cryptographic methods.

• Lattice-based cryptography uses a grid of points that can be described by different bases. A nearly orthogonal good basis makes finding the closest point comparatively easy, while a nearly parallel bad basis makes it difficult in high dimensions. GGH applies this distinction, although GGH itself was broken using a non-quantum attack.

• Key Insights components unavailable; preserved via Key Insights field below.