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?


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

  • $\begingroup$ Dear @xag What's a didactic book to learn about security notions? $\endgroup$
    – juaninf
    May 1, 2013 at 16:09

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.