  Applying the Fiat-Shamir transform on identification schemes is one of the
main ways of constructing signature schemes. While the classical security of
this transformation is well understood, it is only very recently that generic
results for the quantum case have been proposed [DFMS19,LZ19]. These results
are asymptotic and therefore can't be used to derive the concrete security of
these signature schemes without a significant loss in parameters.
  In this paper, we show that if we start from a commit-and-open identification
scheme, where the prover first commits to several strings and then as a second
message opens a subset of them depending on the verifier's message, then there
is a tight quantum reduction for the the Fiat-Shamir transform to special
soundness notions. Our work applies to most 3 round schemes of this form and
can be used immediately to derive quantum concrete security of signature
schemes.
  We apply our techniques to several identification schemes that lead to
signature schemes such as Stern's identification scheme based on coding
problems, the [KTX08] identification scheme based on lattice problems, the
[SSH11] identification schemes based on multivariate problems, closely related
to the NIST candidate MQDSS, and the PICNIC scheme based on multiparty
computing problems, which is also a NIST candidate.

Quantum Physics