Today, I want to mention two open problems that I have been thinking about. These are offshoots of my work with Matt Coudron on the power of quantum depth (arXiv:1909.10503; see, also, arXiv:1909.10303).
There does not seem to be a clear metric in quantum cryptanalysis. For example, we say that the security level of AES256 is 256 bits, and the quantum security level of AES256 is 256/2 = 128 bits. But, that number 128 does not capture the hardness of the attack. The classical attack can be trivially parallelized, but the quantum attack (which uses Grover’s algorithm) cannot be parallelized well. NIST (2016) tries to account for this in their PQC competition by introducing a variable MAXDEPTH, corresponding to the maximum depth of the quantum circuit in the attack, set to a value between $2^{40}$ and $2^{96}$. But, this might still understate the security of the schemes (think of memoryintensive quantum algorithms). Jaques and Schanck (2019) solve this problem with their DWcost metric (depth of the circuit times the width of the circuit). I like the DWcost metric because it makes more sense from a quantumnative perspective. But, this raises new a problem, what about hybrid attacks? It turns out that this can be easily remedied by using the DWcost for the quantum part and the traditional number of ops cost for the classical part.
The setting is the following, the MAXDEPTH is set to be $2^{32}$ (say each layer (depth1 circuit) takes $1000$ nanoseconds to apply^{1}, and we can run a computation for an hour) and MAXWIDTH is set to $2^{32}$ (that is about 4 giga(qu)bits). From this setting it is obvious that you cannot do a purely quantum attack, you need a hybrid attack (and that is my intention.) Just to be clear, a hybrid quantum attack is a classical circuit with embedded quantum circuits with depth at most MAXDEPTH and width at most MAXWIDTH, and the output of a quantum circuit is a classical bit string (or, to be more precise, a probability distribution.) Let’s define the hybridDWcost as the sum of the DWcosts of the embedded quantum circuits and the number of gates in the classical circuit.
Question 1: Hybrid Generic PreImage Attacks on AES?
Question. Is there a nontrivial hybrid generic preimage attack on AES?
Conjecture. The security level of AES256, under hybrid quantum attacks in the hybridDWcost model, is essentially the same as the its classical security level.
A good starting point: arXiv:1512.04965, 2019/854, and 2019/1146.
Question 2: Hybrid Generic ClawFinding Attacks on SIKE?
Question. Tani’s (2007) algorithm, which is used for generic clawfinding attacks, is based on quantum walks which seem to have the same parallelization difficulties as Grover’s algorithm. (See Section 5.6 in Jaques and Schanck (2019).) Is there a nontrivial hybrid generic clawfinding attack on SIKE?
Conjecture. The security level of SIKE(503610751), under hybrid quantum attacks in the hybridDWcost model, is essentially the same as the its classical security level.
A good starting point: arXiv:0708.2584 and 2019/103.
Why These Questions?
 They force one to think about hybrid attacks.
 They seem to model nearterm attacks.
 They don’t seem too hard. Question 1 might even be easy because we know explicit bounds on how Grover parallelizes.
 They are fun math problems. :)

At first glance, this number might seem absurd—surely we can apply a gate in less than $1000$ nanoseconds, but I am trying to account for the lost nearest neighbor property. For now, it seems easier to make this number larger than to impose a nearest neighbor constraint. (Also, I am trying to be architecture agnostic.) ↩