  In this paper, we continue the line of work initiated by Boneh and Zhandry at
CRYPTO 2013 and EUROCRYPT 2013 in which they formally define the notion of
unforgeability against quantum adversaries specifically, for classical message
authentication codes and classical digital signatures schemes. We develop a
general and parameterised quantum game-based security model unifying
unforgeability for both classical and quantum constructions allowing us for the
first time to present a complete quantum cryptanalysis framework for
unforgeability. In particular, we prove how our definitions subsume previous
ones while considering more fine-grained adversarial models, capturing the full
spectrum of superposition attacks. The subtlety here resides in the
characterisation of a forgery. We show that the strongest level of
unforgeability, namely existential unforgeability, can only be achieved if only
orthogonal to previously queried messages are considered to be forgeries. In
particular, we present a non-trivial attack if any overlap between the forged
message and previously queried ones is allowed. We further show that
deterministic constructions can only achieve the weaker notion of
unforgeability, that is selective unforgeability, against such restricted
adversaries, but that selective unforgeability breaks if general quantum
adversaries (capable of general superposition attacks) are considered. On the
other hand, we show that PRF is sufficient for constructing a selective
unforgeable classical primitive against full quantum adversaries. Moreover, we
show similar positive results relying on Pseudorandom Unitaries (PRU) for
quantum primitives. These results demonstrate the generality of our framework
that could be applicable to other primitives beyond the cases analysed in this
paper.
