# Sematically Secure McEliece

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?

-

• 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.
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.