  QROM (quantum random oracle model), introduced by Boneh et al. (Asiacrypt
2011), captures all generic algorithms. However, it fails to describe
non-uniform quantum algorithms with preprocessing power, which receives a piece
of bounded classical or quantum advice. As non-uniform algorithms are largely
believed to be the right model for attackers, starting from the work by Nayebi,
Aaronson, Belovs, and Trevisan (QIC 2015), a line of works investigates
non-uniform security in the random oracle model. Chung, Guo, Liu, and Qian
(FOCS 2020) provide a framework and establish non-uniform security for many
cryptographic applications.
  In this work, we continue the study on quantum advice in the QROM. We provide
a new idea that generalizes the previous multi-instance framework, which we
believe is more quantum-friendly and should be the quantum analogue of
multi-instance games. To this end, we match the bounds with quantum advice to
those with classical advice by Chung et al., showing quantum advice is almost
as good/bad as classical advice for many natural security games in the QROM.
  Finally, we show that for some contrived games in the QROM, quantum advice
can be exponentially better than classical advice for some parameter regimes.
To our best knowledge, it provides some evidence of a general separation
between quantum and classical advice relative to an unstructured oracle.

Quantum Physics;Cryptography and Security