  The Fiat-Shamir transformation is a famous technique to turn identification
schemes into signature schemes. The derived scheme is provably secure in the
random-oracle model against classical adversaries. Still, the technique has
also been suggested to be used in connection with quantum-immune identification
schemes, in order to get quantum-immune signature schemes. However, a recent
paper by Boneh et al. (Asiacrypt 2011) has raised the issue that results in the
random-oracle model may not be immediately applicable to quantum adversaries,
because such adversaries should be allowed to query the random oracle in
superposition. It has been unclear if the Fiat-Shamir technique is still secure
in this quantum oracle model (QROM).
  Here, we discuss that giving proofs for the Fiat-Shamir transformation in the
QROM is presumably hard. We show that there cannot be black-box extractors, as
long as the underlying quantum-immune identification scheme is secure against
active adversaries and the first message of the prover is independent of its
witness. Most schemes are of this type. We then discuss that for some schemes
one may be able to resurrect the Fiat-Shamir result in the QROM by modifying
the underlying protocol first. We discuss in particular a version of the
Lyubashevsky scheme which is provably secure in the QROM.
