OK, so I know that this is somewhat really basic in "post-quantum discourse", but unfortunately I did not find any textbooks/entry level papers specific to the topic of reductions in the quantum setting.
It seems that there are two main caveats regarding quantum adversaries:
- The possibility to ask a "superposition query" => hence, no "off-the-shelf" way to lazy sample functions.
- The inability to clone an unknown quantum state => hence, no "rewinding" in general.
The second pitfall is more tricky for me to understand. Some of the questions, for instance:
Why cant we (as in the usual proofs with rewinding) just fix a random tape and some initial quantum state of the adversary and clone it (if necessary), and then rewind? I.e., can we assume (WLOG) that all adversaries starts from some fixed quantum state (e.g., |0..0>), and then rewind the whole process compeletely to this initial state and tape?
Why only rewinding technique fails? Because there are other cases where we have to restart adversary to boost probability (for example, Goldreich-Levin theorem on hardcore bit (amplification), or some non-black-box reduction, when we run the advesary a number of times dependent on its initial advantage in some problem) -- why there are no problems with these guys?
Is there any paper/textbook on what we CAN and CANNOT do in general when dealing with post-quantum reductions and why can't we do that?
OK, so after some little dive into the topic, I have the following feelings about it.
Currently this is mostly Work-In-Progress. The very first article concerning specific problem of quantum reductions happens to be [1] (~2011), so it is somewhat young field, and most recent results may "turn a table".
There are currently a number of mainstreams, i.e. a number of articles devoted to the specific theme. It seems that NIST PQ challenge was an inspiration for some of those streams, because they are somewhat tailored to the specific needs of KEMs and digital signatures.
The first line of works is lifting theorems. Basically, it says something roughly of the form "if you have a cryptographic scheme S and you prove the property X for it in the ROM model using reduction of type Y, then your reduction can be lifted into QROM model, i.e. negligible stays negligible (assuming quantum hardness of basic primitives)". Some examples are [1,2,3,4].
Second line of work is trying to show that quantum rewinding can be done in special circumstances (such as collapsing sigma-protocols, special/strict soundness, etc). Some of the examples are papers by D. Unruh, M. Zhandry, etc.
The third line is trying to determine how one should modify classical schemes to obtain guarantees in QROM (see lossy identification schemes, Fujisaki-Okamoto transform, Unruh transform, etc).
Unfortunately, maybe due to the fact that the topic is somewhat young, there are not so many entry-level discussions. One should definitely check this winter school [5] (somewhat entry-level, assuming you are OK with first six chapters of this guy [6]), PhD thesis on quantum adversaries [7] (especially, chapter 4), and these series of workshops [8] (feels more hardcore).
As for the answer to starting questions:
Seems that quantum algorithms are inherently probabilistic due to the inner randomness of quantum mechanics, hence we cannot completely de-randomize it (i.e. fix a random tape completely).
Seems that we do not need to rewind to a specific state in these cases, i.e. we are OK if the adversary will start completely afresh (this is not OK in case of rewinding -- usually we want the transcript to be exactly the same until some fixed position where we fork).
[1]. Boneh, Dan, et al. "Random oracles in a quantum world." International conference on the theory and application of cryptology and information security. Springer, Berlin, Heidelberg, 2011.
[2]. Song, Fang. "A note on quantum security for post-quantum cryptography." International Workshop on Post-Quantum Cryptography. Springer, Cham, 2014.
[3]. Zhang, Jiang, et al. "On the (quantum) random oracle methodology: New separations and more." Cryptology ePrint Archive (2019).
[4]. Yamakawa, Takashi, and Mark Zhandry. "Classical vs quantum random oracles." Annual International Conference on the Theory and Applications of Cryptographic Techniques. Springer, Cham, 2021.
[5]. The 11th BIU Winter School on Cryptography. "Cryptography in a Quantum World", https://cyber.biu.ac.il/event/the-11th-biu-winter-school-on-cryptography/
[6]. Nielsen, Michael A., and Isaac Chuang. "Quantum computation and quantum information."
[7]. "Quantum Security of Cryptographic Primitives" by Tommaso Gagliardoni, https://arxiv.org/abs/1705.02417
[8]. Lattices: Algorithms, Complexity, and Cryptography. Jan. 14–May 15, 2020
https://simons.berkeley.edu/programs/lattices2020