Testing of PQC NIST round3 submissions

I am new to this field and have some concerns regarding PQC;

How does NIST do a comparison that a particular algorithm is efficient and its security can not be broken by future quantum attacks? I am enthusiastic to understand the criteria.

Had NIST tried to break the Encryption algorithm by applying Shor's algorithm using the available IBM's quantum computer?

What is the NIST's criteria to check the PQC algorithms submission?

How does NIST do a comparison that a particular algorithm is efficient and its security can not be broken by future quantum attacks?

How efficient an algorithm to implement is easy - these algorithms run on classical computers, and so people have made implementations of these algorithms, and it is straight-forward to measure the performance.

Security is measured by using the same method we use for non-quantum algorithms - people design the best cryptanalysis algorithms they can think of to break them, estimate running time of those cryptanalysis algorithms, and so we can select security parameters that make all such known cryptanalysis algorithms take an infeasible amount of time to run.

The only difference between a PQC and a non-PQC algorithm is that, for a PQC algorithm, we also consider cryptanalysis algorithms that run on a Quantum Computer. This is somewhat more tricky, because we don't have anything that can run a nontrivial cryptanalysis algorithm (the IBM quantum computer and similar are far too small, and are unable to perform the error correction needed), and quantum simulators (which run on classical computers) are also limited in the number of qubits they can handle. On the other hand, we really do have a good understanding on what operations a Quantum Computer can do, and so we can design algorithms that can run on a Quantum Computer. NIST doesn't do all this design work - the vast majority of this work is done by academics and cryptographers outside of NIST - NIST closely monitors this work, and takes this into account.

It is worth mentioning that concrete estimations of the quantum hardness of various problems is still a very new research area, and certain questions are still unresolved. A good example of this is Piekert's paper He Gives C Sieves by the CSIDH. Besides being a great pun, this paper uses something called the colliniation sieve (developed in 2013 by Greg Kuperberg iirc) to attack the CSIDH assumption. Note that this assumption is distinguished among all post-quantum assumptions as it directly yields non-interactive key exchange, something that it is

• fairly easy to get from classical problems (discrete log variants), but
• getting from things like LWE either requires very large parameters, or appealing to an advanced primitive (either FHE or function encryption) --- either case the resulting scheme is inefficient.

The main point of the paper is noting that the colliniation sieve doesn't require access to a large ($\approx 2^{30}$) amount of quantum memory directly, but instead can use "quantum-accessible classical memory" (the final estimate is for more, $\approx 2^{40}$). I remember there being some debate (I am guessing between Dan Bernstein and Chris, but don't precisely remember) either on twitter/the nist PQC google group about the practical implications of this changed estimate.

Very roughly, one can characterize classical security in terms of a pair of (time, memory) required to break a primitive. Quantum security is then related to the 4-tuple (classical time, classical memory, quantum time, quantum memory). Precisely how to extract a single security estimate out of such a 4-tuple is still a matter of debate, and even two experts in post-quantum cryptography can have their disagreements.