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.

• Note that this only works because the decryption algorithm recreates $C_1$ after recovering $\sigma$. Modern schemes do without recreating $C_1$.
– K.G.
Mar 27 '14 at 8:30
• Clear and confirmed wording,Thx Mar 27 '14 at 9:04
• Still in this paper Lemma 11, what does the event Inv mean? And I can't understand the several claims. Can you explian it for me ? Thank you so much Apr 3 '14 at 15:24
• Hint: Inv stands for inversion. Check the meaning of $c_1^*$ and the claim on Pr. Apr 3 '14 at 21:54
• I am also confused with Pr. Does $c_1^*$ mean the $c_1$ in decryption answers? Apr 4 '14 at 6:08