**Abstract:** The Fiat-Shamir construction (Crypto 1986) is an efficient
transformation in the random oracle model for creating
non-interactive proof systems and signatures from
sigma-protocols. In classical cryptography, Fiat-Shamir is a
zero-knowledge proof of knowledge assuming that the underlying
sigma-protocol has the zero-knowledge and
special soundness properties. Unfortunately,
Ambainis, Rosmanis, and Unruh (FOCS 2014) ruled out non-relativizing
proofs under those conditions in the quantum setting.

In this paper, we show under which strengthened conditions the
Fiat-Shamir proof system is still post-quantum secure. Namely, we
show that if we require the sigma-protocol to have computational
zero-knowledge and *perfect* special soundness, then Fiat-Shamir is a
zero-knowledge simulation-sound proof system (but not a proof of
knowledge!). Furthermore, we show that Fiat-Shamir leads to a
post-quantum secure strongly unforgeable signature scheme when additionally assuming a
"dual-mode hard instance generator" for generating key pairs.

Finally, we study the extractability (proof of knowledge) property of Fiat-Shamir. While we have no proof of the extractability itself, we show that if we can prove extractability, then other desired properties such as simulation-sound extractability (i.e., non-malleability), and strongly unforgeable signatures follow.