At this point, it does not appear that (reasonably strong and modern) symmetric cryptography (ciphers, hash functions, etc.) is realistically threatened by quantum computing: https://words.filippo.io/128-bits/

Thanks for the great link! This has been vexing me, as intuitively it seems like if quantum computers can test all factors they should be able to test all keys.

But the article helps. Basically Grover’s is not as potent as Shorr’s. And it seems like everyone is convinced there is no dramatically better quantum algorithm than Grover’s?

No. Not quite. In fact, that blog post ignores something important from the very papers it cites.

Grover's assumes the function is a black box that you cannot look inside and that your only way of finding a certain result is through repeated invocation.

Under this assumption, Grover's is optimal in the number of invocations of the function required to find the result.

However, this assumption may be quite wrong for AES and friends. It may be the structure allows for non brute force attacks that are totally impractical classically but not subject to Grover's optimality limitation quantumly.

The only thing you are guaranteed here is that if you cannot take advantage of structure at all then Grover's is the best you can do.

Given that we have pretty much always found a way to take some advantage of structure, I would bet we will do so here.

That may or may not make it viable to break at all, I just wouldn't bet that it must be treated like a black box forever.

To me that would be a very bad bet.

Thank you again! That’s exactly what my intuition was reaching for by my expertise was too short to support.

And, if I’m following you, that’s the key difference in Grover’s and Shorr’s: Shorr’s takes advantage of structure?

Yes. Structure comes in many forms. In this case, Shor is turning the function into a strongly periodic algebraic structure.

I'll explain it without going too far into why any of this is true, which is much more complicated to prove. This will let me use relatively simple math.

Let's say you want to factor N. Pick some number that is coprime to N, which we'll call a, and consider f(x) = a^x (mod N).

Since it's a modular function, it repeats at some point. Shor calculates the period of this function (r), rather than seeing which of the 2^n numbers is "the answer".

Once you know the period of this function, there is a high chance that the factors fall out of gcd(a^(r/2) - 1, N) and gcd(a^(r/2)+1, N).

The point here is not to explain Shor's as much as to point out it is finding a strong amount of structure to take advantage of, quantumly.

This is actually the same way the oracle separation of BQP and the entire polynomial hiearchy works[1] - It depends on forrelation, which is a problem where quantum computers can extract a global property of the function without needing to learn all the individual values, by taking advantage of structure.

Which is why i go to "The idea that there is literally no structure that can be taken advantage of in AES strikes me as a bad bet".

In part because it's already false if you go literature searching. For example, https://www.sciencedirect.com/science/article/abs/pii/S00200...

There are already reduced round quantum attacks on AES as well. Again, more to the point, the idea that symmetric key ciphers and cryptographic hashes in general are safe because grover's is slower than shor's is not a thing i would bet on at all. Even if AES ends up relatively safe, that tells you basically nothing about the other practically-used ciphers and functions since there are a lot of different construction mechanisms being used.

[1] People still seem to believe there are no functions which quantum computing models have been been proven to be faster at than classical computing models. This is false. Forrelation is the canonical example - and shows that BQP can perform things exponentially faster than you can classically even given access to an infinite polynomial hierarchy.

It is the current physical actualization of these computing models that have the "is it really faster than classical computers" issue, not the theory ;)

(IE it is a perfect example of "in theory there is no difference between theory and practice, and in practice, there is")

Thanks so much for the patient and accessible explanation. So much more useful and grounded than the naive “quantum is faster because it can consider all possible solutions at once” canard.

Good point here I had never thought about, but it's still good to upgrade to 256 bits when possible for peace of mind.

This has nothing to do with SHAttered

But their post-quantum-algorithm also uses sha256. Afaik only asymetric crypto is in danger from quantum computers.

Ah it's interesting, AIUI cryptographic hashes are safe from quantum attacks (for there's an infinity of secrets that, once hashed, give a specific hash and hence somehow it's not possible to use a quantum computer to forge what you'd want).

And from the other comment, symmetric cryptography is safe too from QC attacks.

So it's apparently as you wrote: it's really only asymmetric crypto that is at risk.

> AIUI cryptographic hashes are safe from quantum attacks (for there's an infinity of secrets that, once hashed, give a specific hash and hence somehow it's not possible to use a quantum computer to forge what you'd want).

Quantum algorithms require some sort of quantum 'trick' to actually have any speedup over classical computers. The most general quantum trick is Grover's algorithm, which lets you find f⁻¹(x) (given f and x) in sqrt(N) queries rather than N queries, where N is the size of the set from which x is drawn. This cuts the bit security of every algorithm in half, although for things like cryptographic hashes, it really means that a second preimage is now only as 'easy' as finding a collision (due to the birthday attack).

The other really well-known quantum trick is QFT, which allows you to find the period of an unknown periodic function really quickly. This is what allows quantum computers to break asymmetric algorithms based on integer factoring or elliptic curves, since they can both be expressed in terms of the QFT.

As far as I understand, quantum computing can cut it in half, to 128 effective bits. Still way too large to brute force from there.