# How can I prove that this encryption scheme from a random oracle is secure?

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}$.

• 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), and here use two random oracles: $Hash_z$ and $Gen$ citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.5.9666 – 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