Take the 2-minute tour ×
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.

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
4  
Is this homework? Either way, what have you tried? Where do you have troubles proving it? –  mikeazo Feb 8 at 14:43
1  
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 at 16:17
1  
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 at 18:24
1  
What is $m$? $\:$ (in the opening post) $\;\;\;\;$ –  Ricky Demer Feb 8 at 20:39
1  
@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 at 10:03

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.