Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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.

share|improve this answer
Dear @xag What's a didactic book to learn about security notions? – juaninf May 1 '13 at 16:09

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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