Filippo:
quantum-resistant cryptography has changed compared to just a few months ago. You might have heard this privately from me in the past weeks, but it’s time to signal and justify this change of mind publicly.
2 Likes
I think regardless of your own personal expectations on the advancements of quantum computers, it should be desirable to move to PQC as soon as possible at this point. All it takes is one good enough breakthrough, and we are going to stop hearing about progress as it gets closer to the finish line.
Can someone clarify for a non-expert what this means for different kinds of encryption? Will this be able to crack full disk encryption of a harddrive for instance? Or is it only encrypted communication?
I think the real danger is that we won’t know it happened until long after the fact.
If you have the ability to decrypt a large amount of the worlds data and you spent billions to get that capability….are you really going to announce it publicly or sell the info to the highest bidder?
2 Likes
I would also like to know.
Does this give a company like Tuta an advantage over Proton?
AFAIK, only asymmetric encryption is severely affected by quantum computing(which is based on prime factorization). Symmetric encryption algorithms such as AES(Rijndael), Serpent, ChaCha, etc are already quantum secure. The post quantum cryptography standard adopted by NIST also involves only replacing the asymmetric encryption algorithms.
1 Like
There are three quantum algorithms that pose threats to classical encryption:
- Shor’s Algorithm
- Grover’s Algorithm
- JVG Algorithm
Shor’s algorithm is the most famous quantum algorithm for breaking public key cryptography. It solves two mathematical problems that hold most internet encryption:
- Integer factorization (RSA):
- Discrete logarithm problem (ECC & DSA)
A sufficiently powerful quantum computer could break a 2048-bit RSA key or a 256-bit ECC key in hours.
After recent optimization in Quantum technology roughly 100,000 – 1 million noisy physical qubits or 1000 - 1400 logical qubits are required to break asymmetric encryption.
Gover’s algorithm is the main quantum threat to symmetric encryption and hash functions.
With Grovers’s algorithm, for symmetric ciphers like AES-256, brute force key search drops to AES-128 security. For cryptographic hashes (e.g., SHA-256), collision or preimage attacks get a similar speedup.
It does not break the algorithms outright but forces key lengths to roughly double for equivalent security (e.g., AES-256 becomes the new baseline). It is less catastrophic than Shor’s but still requires larger symmetric keys and affects protocols relying on brute-force resistance.
For a successful attack of Grover’s algorithm (turning 256-bit security to 128-bit or 128-bit to 64-bit) roughly 3000-7000 logical qubits are required.
So in symmetric encryption if someone is using 256-bit symmetric encryption he is safe for foreseeable future, but 128-bit encryption is in severe danger.
JVG algorithm is a new hybrid classical-quantum algorithm explicitly designed as a more resource efficient alternative to Shor’s for integer factorization (and thus RSA/ECC breaking). It was introduced in a preprint by researchers at the Advanced Quantum Technologies Institute (AQTI) and quickly generated headlines about a potential “cybersecurity apocalypse.”
The paper projects that RSA-2048 could be factored in 11 hours using fewer than 5,000 physical qubits or only 256 logical qubits, a thousand-fold reduction in quantum resources compared to Shor estimates.
But this is still on paper and only experimented in simulations on tiny numbers so if the claims will hold in real world is still not clear and some independent analysis shows that it has major scalability limitations for large keys.
3 Likes
“Severe danger” is quite a stretch. Grover’s algorithm is not very parallelizable [1]. It can reduce the search space of a 128-bit key to 2^64, but it can’t search that 2^64 key space as efficiently as classical attacks would.
There is still some risk, of course, and long-term fixed keys like those used for disk encryption should absolutely be 256-bits as a result, but it is very possible that CRQCs are not able to meaningfully threaten symmetric cryptography in the near-to-mid-term future.
[1] https://quantumcomputing.stackexchange.com/a/5806 (has more citations to specific papers about this too)
1 Like
NIST stated:
Taking these mitigating factors into account, it is quite likely that Grover’s algorithm will provide little or no advantage in attacking AES, and AES 128 will remain secure for decades to come. Furthermore, even if quantum computers turn out to be much less expensive than anticipated, the known difficulty of parallelizing Grover’s algorithm suggests that both AES 192 and AES 256 will still be safe for a very long time. This of course assumes that no new cryptographic weaknesses, either with respect to classical or quantum cryptanalysis, are found in AES.
So, the security of AES-128 will depend on when “much less expensive” quantum computers become available.
In February 2025, Microsoft introduced the Majorana 1 chip prototype.
Although it is still just a prototype, if Microsoft succeeds and their claims turn out to be true, then AES-128 could be in danger in maybe 5–10 years rather than decades.
So yes, “severe danger” is exaggerated, but it is still in real potential danger. That’s why NIST recommended (and many experts continue to recommend) using AES-192 or AES-256 for long-term protection.
Yeah I didn’t say otherwise. Like you said,
Of course, assuming there’s not a limitation no one’s aware of yet, AES-128 will eventually be broken by a CRQC.
However, I think we still disagree here
This timeline is reasonable for breaking asymmetric cryptography. I think that it is still extremely optimistic for breaking AES-128. Grover’s algorithm, in addition to providing much less benefit than Shor’s and being difficult to parallelize enough to provide a meaningful benefit over classical attacks, also requires more logical qubits. Once RSA-2048 is broken there’s still a decent amount of work required to break AES-128.
If a quantum computer becomes stable enough to break RSA-2048, it means the hardest problem (fault-tolerant scaling) has been largely solved. From that point, the gap to attacking AES-128 is no longer about feasibility, but about efficiency. While AES-128 wouldn’t fall immediately, it would move from “theoretical concern” to “practical target,” because the remaining challenges are engineering optimizations rather than fundamental barriers.
1 Like
The same author talked about there being a practical limit to circuit depth https://x.com/FiloSottile/status/1544680637638008833
Direct quote being
This MAXDEPTH is realistically around 2⁴⁰, which makes a quantum attack against a 128-bit cipher take more than 2¹²⁸ anyway.
I’m unsure if they meant 256-bit ciphers take more than 2¹²⁸. But still, from what I gather, O(sqrt(n)) is an ideal runtime, not what’s possible in practice.
MAXDEPTH limits how much of Grover’s theoretical speedup you can extract in a single run, but it doesn’t eliminate the advantage. It just forces you to trade circuit depth for more qubits and repetition.
2⁴⁰ limit doesn’t break Grover, it just makes it expensive in a different way.
So what does that mean in practice? 128-bit cipher breaks in 2⁶⁴ time on Grover running on quantum computer with n qubits? Or on n quantum computers?
It’s not “2⁶⁴ on one machine.”
It’s “~2⁶⁴ total work, spread across time, qubits, and possibly many quantum systems”
Personal curiosity here. Would it be a good idea to use AES-512 or even AES-1024 to protect against possible quantum computing in the near future? (I know that AES-512, 1024 don’t exist currently, but I suppose simply increasing the key size and iteration rounds is easier than devising a totally new algorithm)
Although AES-256 remains secure for the foreseeable future, your intuition is partially correct in theory. However, AES-512 or AES-1024 do not exist as standardized algorithms, and simply doubling the key size or number of rounds on AES is not a trivial fix. It would require a brand-new design, extensive cryptanalysis, and standardization.
Practically:
-
Use ChaCha20-Poly1305 instead of AES-256: Although it offers similar post-quantum key strength, it is a better choice than AES-256 whenever possible.
-
Use Argon2id for password hashing: It is the strongest memory-hard function currently available and can make even relatively weak passwords resistant to brute-force attacks, even against quantum computers.
-
Generate passwords (or keys) with at least 256 bits of entropy where possible. This provides strong protection against quantum threats.
1 Like
Thanks for sharing. Btw, why do you recommend ChaCha over AES? Is there some inherent characteristic of ChaCha (or any other stream ciphers) that makes it better than AES (or any other block ciphers)? Afaik, only AES, has hardware level support, which allows encryption and decryption to be done way faster than similar algorithms.
Edit) Just asked Gemini. It said that ChaCha is naturally more resistant to side channel attacks, and has a speed advantage over AES when running on unsupported hardware.
please correct if I’m wrong
ChaCha20 has higher security margin.
See https://eprint.iacr.org/2019/1492.pdf
Also: Chacha20 is naturally immune to timing attacks on most platforms, while AES requires special care if you don’t have hardware support.
Also:
Security margin. Cryptographic literature shows that increasing the number of rounds in a primitive makes it harder to break. So when we study a primitive, we try and break weaker versions, with fewer rounds. The security margin of a primitive is the difference between the minimum number of rounds required to thwart all known attacks, and the actual number of rounds. Chacha20 for instance has a margin of 12 rounds: as of 2020, 8 rounds stop all known attacks, and we have 20.
1 Like
You are right. Just want to add one more thing:
Plain ChaCha20 is only a stream cipher, it gives you encryption but no authentication or integrity protection. An attacker could flip bits in the ciphertext and you’d never know it was tampered with (classic malleability issue).
Poly1305 is a fast, secure Message Authentication Code (MAC). When you combine them as ChaCha20-Poly1305, you get a complete AEAD (Authenticated Encryption with Associated Data) primitive, just like AES-GCM, but designed from the ground up for software efficiency. Thats why I recommended ChaCha20-Poly1305 not just ChaCha20