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'm reading a proof of the proposition of CollisionResistant Hashing Towards Making UOWHFs Practical

Suppose there exists a compression function $F: \Sigma^k\times\Sigma^{c+m'} \rightarrow \Sigma^c$ with $m'>k$ such that $F$ is $(t',\epsilon')$-resistant to target collisions. Then there exists a compression function $H$ such that $H$ is $(t,\epsilon)$-resistant to target collisions for $t=t'- \Theta (k+m') $ and $\epsilon' = \epsilon + 2^{-k+1}$

To show that, the author constructs the following hash function: $$H(K,x||y||z) = H_K(x||y||z)= \begin{cases} F_K(x||y||z)||K & \text{if }y\neq K \\1^c||1^k & \text{if }y = K \end{cases}$$

Here is the proof:


My questions:

  • I don't understand why a $CF'$ run in time $t+O(k+c+m)$ I know why he add $t$ but I don't undertand Why $O(k+c+m)$?

  • Why a $ProbSuccess(CF',F)\geq 1-2^{-k+1}$? I understand that means $2^{-k}$ but I don't Why $2^{-k}*2$

share|improve this question
@jauninf- I've suggested a couple of minor edits for clarity (writing the hash function in cases, - into bullets), hope they're helpful – figlesquidge Nov 14 '13 at 13:19
@user8911 thanks – juaninf Nov 14 '13 at 13:42

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.