  Shor's quantum factoring algorithm and a few other efficient quantum
algorithms break many classical crypto-systems. In response, people proposed
post-quantum cryptography based on computational problems that are believed
hard even for quantum computers. However, security of these schemes against
\emph{quantum} attacks is elusive. This is because existing security analysis
(almost) only deals with classical attackers and arguing security in the
presence of quantum adversaries is challenging due to unique quantum features
such as no-cloning.
  This work proposes a general framework to study which classical security
proofs can be restored in the quantum setting. Basically, we split a security
proof into (a sequence of) classical security reductions, and investigate what
security reductions are "quantum-friendly". We characterize sufficient
conditions such that a classical reduction can be "lifted" to the quantum
setting. We then apply our lifting theorems to post-quantum signature schemes.
We are able to show that the classical generic construction of hash-tree based
signatures from one-way functions and and a more efficient variant proposed
in~\cite{BDH11} carry over to the quantum setting. Namely, assuming existence
of (classical) one-way functions that are resistant to efficient quantum
inversion algorithms, there exists a quantum-secure signature scheme. We note
that the scheme in~\cite{BDH11} is a promising (post-quantum) candidate to be
implemented in practice and our result further justifies it. Finally we
demonstrate the generality of our framework by showing that several existing
works (Full-Domain hash in the quantum random-oracle model~\cite{Zha12ibe} and
the simple hybrid arguments framework in~\cite{HSS11}) can be reformulated
under our unified framework.
