We regularly hear news about breakthroughs leading to the advent of working quantum computers. For now, such a computer doesn’t exist, so nobody can use one to crack encryption. But when it does arrive, it’ll already be too late to address the problem. That’s why new encryption algorithms that are resistant to both classical hacking methods and quantum-computer attacks are being standardized today. These algorithms are known as post-quantum or quantum-resistant. Support for these algorithms is gradually appearing in everyday devices and applications — they were recently integrated into Google Chrome. This, by the way, immediately exposed compatibility issues within standard organizational IT infrastructures. So, where have post-quantum algorithms already been implemented, and what should IT teams prepare for?

Which services already support post-quantum algorithms?

Amazon. The cloud giant introduced a “post-quantum” variant of TLS 1.3 for its AWS Key Management Service (KMS) back in 2020. Since then, the solution has been updated, adapting its configuration settings in line with NIST recommendations.

Apple iOS/iPadOS/macOS. In February 2024, Apple announced an update to the iMessage protocol, which will use the PQ3 quantum-resistant protocol for key exchange. It’s based on the NIST-recommended Kyber algorithm, but also utilizes classical elliptic-curve cryptography, providing dual-layer encryption.

Cloudflare. Since September 2023, Cloudflare has supported post-quantum key agreement algorithms for establishing connections to origin servers (client websites), and is gradually rolling out support for post-quantum cryptography for client connections. The technology is used when establishing a TLS connection with compatible servers/clients, applying a dual key agreement algorithm: classical X25519 for one part of the key, and post-quantum Kyber for the other. This popular combination is known as X25519Kyber768.

Google Chrome. Test support for post-quantum cryptography for establishing TLS connections appeared in August 2023, and as of version 124 in April 2024, it’s enabled by default. The algorithm used is X25519Kyber768.

Mozilla Firefox. Support for X25519Kyber768 for TLS and QUIC appeared at the beginning of 2024, but it’s still not enabled by default and must be activated manually.

Mullvad. This popular VPN service uses the following PQC method: first, a traditional encrypted connection is established, after which a new key agreement is conducted using the Classic McEliece and Kyber algorithms. The connection is then re-established with these keys.

Signal. The messenger implemented the PQDXH protocol in September 2023, using the same X25519Kyber768 mechanism.

Tuta(nota). The popular secure email service allows users to send post-quantum encrypted emails using the X25519Kyber768 algorithm. However, the obvious drawback is that this only works when communicating with other Tuta users.

Although not yet a commercial product, it’s also worth mentioning Google’s implementation of FIDO2 hardware security keys, which use a combination of classical ECDSA and post-quantum Dilithium.

In addition to these, PQC is supported by numerous libraries that serve as the foundation for other products, from email and web servers to operating systems. Notable libraries include OpenSSL and BoringSSL, as well as the experimental branch of Debian. Many of these implementations have been made possible thanks to the Open Quantum Safe initiative, which supports post-quantum forks of popular cryptographic utilities and libraries, available for a variety of popular programming languages.

The main drawbacks of quantum-resistant cryptography

1. The algorithms haven’t been sufficiently analyzed. Although the broader scientific community has been conducting cryptanalysis for several years, the mathematical principles behind post-quantum cryptography are more complex. Moreover, experience with classical cryptography shows that serious flaws or new attack methods can sometimes be discovered decades later. It’s almost certain that vulnerabilities will be found in modern PQC algorithms — not just implementation vulnerabilities, but fundamental algorithmic defects.
2. Key sizes are significantly larger than in RSA and ECC. For example, the Kyber768 post-quantum algorithm has a public key size of 2400 bytes. This leads to a significant increase in data transmission volumes if key renegotiation occurs frequently. In tightly designed or low-power systems, there might not be enough memory for such large keys.
3. The computational load of PQC is also higher than classical, which slows down operations and increases energy consumption by 2–3 times. However, this issue may be resolved in the future with optimized hardware.
4. Compatibility issues. All updates to encryption standards and protocols — even classical ones — create complications when some systems have been updated and other related ones haven’t.

Post-quantum compatibility problems

Practical issues will primarily affect services using the TLS protocol for connections. TLS is implemented in numerous ways across thousands of products — sometimes with errors. As soon as Google enabled Kyber support by default in Chromium 124, administrators started reporting that Chrome and Edge couldn’t establish connections with web servers, as they would immediately disconnect with an error after the ClientHello TLS handshake. This issue was caused by problem number two: the large key size. As a result, the ClientHello TLS message, which always fitted into a single TCP packet, expanded into multiple packets, and so servers, proxies, and firewalls not prepared for this larger ClientHello message would immediately terminate the connection. Appropriate behavior would involve reading the following packets and agreeing on an older, classical encryption algorithm with the client. A list of incompatible web servers and firewalls affected by this issue is being tracked on a dedicated site, with Cisco notably listed.

If an organization suddenly can’t open any websites, the problem is likely with the proxy or firewall, which needs an update. Until the developers of incompatible applications and devices release patches, a temporary solution is to disable PQC:

• using MS Edge and Chrome group policies
• in Chrome’s advanced settings: chrome://flags/#enable-tls13-kyber
• in Firefox’s settings: about:config -> security.tls.enable_kyber

Administrators are advised to check their websites and web applications by enabling Kyber support in Firefox or Chrome and attempting to access the site. If an SSL/TLS error occurs, the web server needs to be updated.

Quantum-resistant cryptography standards

Standardization is key to preventing a “protocol mess” and compatibility issues. For PQC, this process is ongoing but far from complete.

NIST recently introduced the first full-fledged standards for post-quantum cryptography — FIPS 203, FIPS 204, and FIPS 205. Essentially, these are CRYSTALS-Kyber for key exchange, along with CRYSTALS-Dilithium and SPHINCS+ for various digital-signature scenarios.

European organizations  from — ENISA and ETSI to BSI and ANSSI — intend to adopt NIST’s standards but are open to considering additional algorithms if they prove to be better. They all emphasize the necessity of double encryption for critical data — using both post-quantum and classical algorithms simultaneously. Given the novelty of post-quantum algorithms, innovative methods of breaking them may emerge, which is why the second layer of encryption is recommended.

China plans to standardize post-quantum algorithms in 2025. The Chinese Association for Cryptologic Research (CACR) announced the finalists in 2020: Aigis-sig and Aigis-enc (modified relatives of CRYSTALS-Kyber and CRYSTALS-Dilithium) and LAC.PKE.

Meanwhile, the IETF working group responsible for internet protocols will likely endorse the use of cryptography standards proposed by NIST in these protocols.