Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It's 100% free, no registration required.

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 reading this example:

A random oracle is an ideal object.

What makes a random oracle convenient for proofs is the part about knowing nothing on the output for a given input if you do not try it. For instance, consider the following encryption scheme:

  • $H$ is a random oracle which outputs $n$-bit values.
  • The key is a $K$, a string of $k$ bits.
  • A single message $m$ is encrypted by computing $c = m \oplus H(K || 1) || H(K || 2) || ...$ (you repeatedly "hash" with the random oracle the successive strings obtained by concatenating $K$ with a counter, and you concatenate the oracle outputs into a big stream which is XORed with the message to encrypt).

If $H$ is a random oracle, then it is reasonably easy to prove that the encryption is secure up to a work factor of $2^{k-1}$ invocations of $H$.

How I will be able to prove that that the encryption is secure up to a work factor of $2^{k-1}$?

pdta: I think that the encryption is secure up to a work factor of $2^{k}$.

share|improve this question
Look up what "secure up to $x$" means. (The details might differ for each author.) I suppose it means something like "with $x$ invocations, the attacker has a chance of 50% to break the scheme". – Paŭlo Ebermann Apr 14 '13 at 17:51
in this case $50\% = 2^{k-1}$ invocations? – juaninf Apr 14 '13 at 20:18
The plain old bruteforce key search will need $2^k/2 = 2^{k-1}$ invocations on average, or for a 50% chance. Your job would be to show that there can't be a faster algorithm. – Paŭlo Ebermann Apr 14 '13 at 20:22
attacks are made ​​with the same hash function $H$ or could be another?. I make this question because I am read other example Lemma2 (pp13)[1], and here use two random oracles: $Hash_z$ and $Gen$ [1] – juaninf Apr 29 '13 at 18:34
In that paper $Hash$ is a function with fixed length output (and variable length input), while $Gen$ has a fixed length input and arbitrary length output. (Se section 4.1 for the notations.) Normally we name the latter one Random number generator, not hash function, though we want similar security properties for both. – Paŭlo Ebermann Apr 30 '13 at 11:07

Your Answer


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

Browse other questions tagged or ask your own question.