Cryptography Stack Exchange is a question and answer site for software developers, mathematicians and others interested in cryptography. It only takes a minute to sign up.
Sign up to join this community
I'm looking for examples of a proof by reduction. For example:
Let $A=(Gen, H)$ be a hash function. We define a new Hash function $A'=(Gen',H')$ with $Gen=Gen'$ by $H'_s(x)=H_s(H_s(x))$.
It should be shown that if $A$ is collision resistant, then $A'$ is collision resistant too.
I am not looking for a solution for this question.
I'm looking for an idea of how to construct a reduction so that I can solve this problem on my own.
When you try to reduce the security of one primitive (H') to the security of another primitive (H), you assume that there exists an adversary that could break H'. Then you show that existence of said adversary implies an adversary against H by describing an algorithm (the reduction) that uses the adversary to break H.
as a very simple example, consider the hash function $H$ and the hash function $H'(x) = H (x \oplus 1^{|x|})$ (with $\oplus$ being XOR and $1^{n}$ denoting the string of $n$ ones).
Now assume there exists an adversary $\mathcal{A}$ against the collision resistance of $H'$, i.e. there exists a ppt algorithm $\mathcal{A}$ that on input $s$ (and potentially a security parameter) will output $x$, $x'$ such that $H'(x)=H'(x')$ (with non-negligible probability).
Now your reduction needs to transform such a collision into a collision for $H$. If you look at how $H'$ is constructed, you can easily see that this can be done by computing $y = x\oplus 1^{|x|}$ and $y' = x'\oplus 1^{|x|}$ and outputting $y,y'$.
So your reduction is the algorithm that runs $\mathcal{A}$, flips all the bits in $\mathcal{A}$'s output and returns it. You can easily verify, that this reduction is successful whenever $\mathcal{A}$ is successful. As $H$ is collision resistant, the probability that $\mathcal{A}$ is successful must therefore be negligible and thus $H'$ is collision resistant.
So the problem you need to solve for your case is basically the question "How can I turn a collision of $H'$ into a collision of $H$?" When you think a moment about the way $H'$ is constructed, I am sure you will see an obvious way to do that.
In order to show that A' is collision resistant, you start with an attacker on the collision resistance of A' and show that you can build an attacker which will break the collision resistance of A. Specifically, you're given an oracle B' which will give values x' and y' such that H(H(x')) = H(H(y')) and you then need to construct an attacker B with the use of B' such that B returns two values x and y where H(x) = H(y).
