Security proof of FO(Fujisaki-Okamoto) hybrid encryption The proof of FO hybrid encryption is hard to understand. $\:$ Especially, how does the challenger

respond to the decryption queries when the challenger can only have some encryption queries?
Intuition

The intuition behind the proof is that a valid ciphertext is correctly generated and, thus, an adversary should query to the random oracles to generate random strings in the ciphertext. 
In addition, notice that the hash value on an unqueried string is undetermined (to the adversary) in the random oracle model. Therefore, the chance to construct a valid ciphertext without querying to the random oracles is negligible.

How to answer a decryption query

Lemma 11 is the core of the proof. The knowledge (or plaintext) extractor without a secret key but with the tables of the random oracles successfully simulates the real decryption oracle with the secret key following the above intuition. In Appendix B, the knowledge extractor is described.

A ciphertext of the converted PKE is of the form $$(C_1, C_2) = (\mathsf{PKE.Enc}_{pk}(\sigma; H(\sigma,m)), \mathsf{SKE.Enc}_{G(\sigma)}(m)).$$
The knowledge extractor has the tables $T_G, T_H$ of the random oracles $G, H$.
The table $T_H$ contains $(\sigma_j,m_j,h_j)$, where $h_j$ is a returned value on the query $(\sigma_j,m_j)$. The table $T_G$ contains $(\sigma_i,g_i)$, where $g_i$ is a returned value   on the query $\sigma_i$. 

the knowledge extractor, given a ciphertext $(C_1, C_2)$, picks up consistent pairs $(\sigma, m)$ from the tables $T_G$ and $T_H$, which satisfy the equation, $$(C_1, C_2) = (\mathsf{PKE.Enc}_{pk}(\sigma; H(\sigma,m)), \mathsf{SKE.Enc}_{G(\sigma)}(m)),$$
by re-encryption with $h$ and $g$ in the tables.
If discovered, the knowledge extractor returns $m$. Otherwise, it returns $\bot$.

You can find the proof in Appendix B of the paper.