  Formulating and designing authentication of classical messages in the
presence of adversaries with quantum query access has been a longstanding
challenge, as the familiar classical notions of unforgeability do not directly
translate into meaningful notions in the quantum setting. A particular
difficulty is how to fairly capture the notion of "predicting an unqueried
value" when the adversary can query in quantum superposition.
  We propose a natural definition of unforgeability against quantum adversaries
called blind unforgeability. This notion defines a function to be predictable
if there exists an adversary who can use "partially blinded" oracle access to
predict values in the blinded region. We support the proposal with a number of
technical results. We begin by establishing that the notion coincides with
EUF-CMA in the classical setting and go on to demonstrate that the notion is
satisfied by a number of simple guiding examples, such as random functions and
quantum-query-secure pseudorandom functions. We then show the suitability of
blind unforgeability for supporting canonical constructions and reductions. We
prove that the "hash-and-MAC" paradigm and the Lamport one-time digital
signature scheme are indeed unforgeable according to the definition. To support
our analysis, we additionally define and study a new variety of quantum-secure
hash functions called Bernoulli-preserving.
  Finally, we demonstrate that blind unforgeability is stronger than a previous
definition of Boneh and Zhandry [EUROCRYPT '13, CRYPTO '13] in the sense that
we can construct an explicit function family which is forgeable by an attack
that is recognized by blind-unforgeability, yet satisfies the definition by
Boneh and Zhandry.
