Can quantum hardness be demonstrated?

Question

I am disturbed by assertions that this or that classical cryptographic primitive is "quantum resistant", but my understanding is that no one knows yet how to demonstrate quantum hardness, or even if such demonstrations are possible. At best, there may be cryptographic primitives for which no quantum attack has yet been found (but of course the world does not have much experience yet with quantum computers!)

Is this correct? Or, is there a rigorous way to demonstrate quantum hardness that I have not yet seen?

Answer 1

"Classical hardness" is demonstrated in the very same way, namely, we find a problem that is believed to be hard then we reduce the task of breaking the security of the scheme to the task of solving that problem.

So, it is kind of the same situation, because maybe there exist classical polynomial-time solutions to the problem used and those solutions simply were not discovered yet.

The main difference is that, in general, we are far more used to classical computers than to quantum ones and maybe saying that a problem is believed to be classical hard is more meaningful than the quantum analogous because we have really studied those problems a lot in the classical setting...

Answer 2

I'm going to interpret your question as follows:

How can we understand the capabilities of a quantum computer, without having built one?

or, equivalently:

How good is our understanding of quantum information theory?

---

[disclaimer: I am not a quantum information theorist, so this is a layman's understanding]

Quantum information theory

Even though we've never built one big enough to break real-world RSA, we understand that the building blocks will be qubits and quantum logic gates. While there will undoubtedly be advances in quantum algorithms, we can model things that ought to be easy and things that ought to be hard with these building blocks.

My 2nd year physics understanding is that quantum computers fundamentally operate on waves, so anything that can be described as a wave problem becomes easy for a QC.

For example, both RSA and ECC have periodic group structures, ie finding the period of repetition of

$f(x) = m^x (mod N)$,

exploitation of which would lead to reduced-time brute-forces. Fortunately, period-finding is a hard problem on a classical computer, but periods, wavelengths, frequencies ... waves, and presto! We have Shor's algorithm.

Alright, so armed with this understanding, we can set out to find computation problems that do not have nice periodic wave-like properties. *To the best of our knowledge*, these will be quantum secure. Arguing the exact number of bits of post-quantum security that a given algorithm has is a bit of a crap-shoot at the moment, but I think we have enough understanding of quantum information theory to go "roughly 64 bits, roughly 128 bits, or roughly 256 bits".

Classical information theory

"To the best of our knowledge" holds for classical crypto too. Look at MD5, which was thought to have 128 bits of security when it was introduced, but we now have attacks that can find collisions in $< 2^{64}$ operations. Or RSA, which keeps getting weaker as better integer factorization techniques are discovered.

So there is no rigorous way to demonstrate hardness; all we can do is launch a new algorithm and guess at the number of bits of security against the best-known attacks of the day, this is of both quantum and classical crypto.