Sematically Secure McEliece

Question

I am read the Lemma 2 (pp13) in the paper "Kazukuni Kobara and Hideki Imai: Semantically Secure McEliece Public-Key Cryptosystems –Conversions for McEliece PKC– (PKC 2001)".

Related to the question "Why… for any $Hash_z$ and any $Gen$?", the author of the paper replies;

The reason why "for any $Hash_z$ and any $Gen$" is that if the sentence is not included the cryptosystem may be broken due to weak $Hash_z$ or $Gen$.

I know the hash strong definition:

There exist no x and x' with x != x' so that h(x) = h(x')

In this case are $x=Hash_z$, $x'=Gen$" and $h=A$?
Are the $Hash_z$ and $Gen$" from Lemma 2 the same that $Hash_z$ and $Gen$" of Figure 5 of that paper?

Answer 1

I assume that the paper you have read is the paper by Kobara and Imai in PKC 2001 (or its journal version), which proposed a padding scheme for the McEliece PKE scheme. In Lemma2, the authors showed CPA security of the padded scheme.

• The first answer is NO. They are not. Let $C(n,t) = \{z \mid z \in \{0,1\}^n, Hw(z) = t\}$, where $Hw(z)$ denotes $z$'s Hamming weight. As the authors defined in Section 4.1, $Hash_z: \{0,1\}^* \to C(n,t)$ is a cryptographic hash function and $Gen: C(n,t) \to \{0,1\}^*$ is a PRG.
• The second answer is YES. They are same.

In Lemma 2, the authors assume that there exists an adversary A "for any $Hash_z$ and $Gen$" breaking the padded scheme. Here, the authors assume that the adversary works even if we separate $Hash_z$ and $Gen$ as oracles (instead of giving their codes to the adversary). Indeed, the authors modeled $Hash_z$ and $Gen$ as the random oracles in the proof.