The Modern Crypto Primitives

The quantum crypto folks are threatening the cryptographic infrastructure that runs the world. I summarize the main functions.

Hash. Any digital message can be transformed to a 32-byte hash. It is believed that no one will ever find two messages with the same hash.

Public key pairs. A 32-byte private key can be converted to a 32-byte public key. No one can invert the operation.

Signature. A private key and a message hash can be signed to a 64-byte signature. The public key can verify the signature. No one can forge the signature without the private key.

Encryption. A 32-byte secret key can encrypt an arbitrary digital message. No one can decrypt without the secret key.

Key agreement. Two public key pairs can be combined to give a 32-byte shared secret, using the private key of one and the public key of the other. Both ways give you the same shared secret. No one can get it from just the public keys.

These functions are quite efficient and underlie the security of nearly everything on the internet today, notably https and ssh. They also underlie Bitcoin. There is broad agreement that they cannot be cracked with conventional Turing computers for the foreseeable future. There are widely available free libraries to do all these things.

Quantum computers threaten the public keys, making it possible to deduce the private key. Google predicts this will happen on what they call Q-Day, maybe as early as 2029. I doubt it will ever happen.

There are post-quantum public key pairs that are resistent to quantum algorithms, but they are much bigger and not as well tested.

Microsoft and Google are hard at work replacing their public key pairs with post-quantum ones. Some high-value targets want to switch now, because of the possibility that transmissions are being recorded now so that the Chinese can decrypt ten years from now. For a typical user ordering an online product, this is not a concern.

This reminds me a little about how IPv6 was designed to replace IPv4 internet protocol in 1998. Most of you reading this are probably still using IPv4. The reasons for change are different, but it shows how the networks are slow to change, if the old system is working just fine.