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

Let $ f : \{0,1\}^* \rightarrow \{0,1\}^n$ and $ g : \{0,1\}^* \rightarrow \{0,1\}^m$. $h$ is created by concatenate f and g: $ h : \{0,1\}^* \to \{0,1\}^{n+m}$ with $h(x) = f(x) || g(x)$. How do I prove that both $f$ and $g$ must be preimage resistant if $h$ is to be preimage resistant? Is the same true for 2nd-preimage resistance?

share|improve this question
Is this homework? Either way, what have you tried? Where do you have troubles proving it? – mikeazo Feb 8 '14 at 14:43
Yes, it is homework. I know that if h is preimage resistant it must be hard to find x such that h(x)=y with y belongs to Im(h), that means it is hard to find x such that f(x)=p and g(x)=q with y=p||q. I don't know how to proceed from this. – user3283751 Feb 8 '14 at 16:17
Are you sure both have to be preimage resistant for $h$ to be? Say $g$ is not. That means given a digest $y=y_1||y_2$ from $h$ where $y_2$ is the output of $g$, we can find a value $x'$ (which may or may not be $x$) such that $g(x')=y_2$. What we don't know is if $f(x')=y_1$. Likely it isn't if $f$ is preimage resistant. Then $h(x')=f(x')||g(x')=f(x')||y_2$ which is likely not $y$. – mikeazo Feb 8 '14 at 18:24
What is $m$? $\:$ (in the opening post) $\;\;\;\;$ – Ricky Demer Feb 8 '14 at 20:39
@fgrieu : $f(x) =0^n$ is not preimage resistant ,suppose $g(x)$ is a preimage resistant function. $h(x) = 0^n \| g(x)$.So $h(x)$ must be preimage resistant because otherwise $g(x)$ will not be preimage resistant. Is that a right counterexample? – user3283751 Feb 9 '14 at 10:03

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.