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?


1 Answer 1



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.

  • 1
    $\begingroup$ Note that this only works because the decryption algorithm recreates $C_1$ after recovering $\sigma$. Modern schemes do without recreating $C_1$. $\endgroup$
    – K.G.
    Mar 27, 2014 at 8:30
  • $\begingroup$ Clear and confirmed wording,Thx $\endgroup$ Mar 27, 2014 at 9:04
  • $\begingroup$ 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 $\endgroup$ Apr 3, 2014 at 15:24
  • $\begingroup$ Hint: Inv stands for inversion. Check the meaning of $c_1^*$ and the claim on Pr[1]. $\endgroup$
    – xagawa
    Apr 3, 2014 at 21:54
  • $\begingroup$ I am also confused with Pr[1]. Does $c_1^*$ mean the $c_1$ in decryption answers? $\endgroup$ Apr 4, 2014 at 6:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.