2
$\begingroup$

Let H() be a hash function that achieves collision resistance
as well as first and second preimage resistance.

Let's equip the output set of H of a multiplicative group structure, more precisely a cyclic group.

The question

My question is: Is it hard, given $a$ to find $(b,c)$ such that $H(b) \times H(c) = H(a)$ ?

Heuristic / Intuition

Before trying a reduction to one of the hash properties, I tried to realize this function myself:

Given $a$, I take a random $b$, then I'm looking for $c$ satisfying: $H(c) = H(a) \times H(b)^{-1}$.
Then preimage resistance of H prevent me from finding $c$.

Then my intuition is that my target function is as hard as preimage resistance, but I cannot end up
with a reduction: given $H(a)$ and an Oracle that solve my problem, I don't find a way to obtain $a$.

Identically, given such an Oracle I cannot find a way to create a collision.

$\endgroup$
  • $\begingroup$ Do you include modulo in your product, or do H(b) and H(c) have to be small enough so that H(a) remains in the valid output range? $\endgroup$ – Dillinur Feb 20 '15 at 10:31
  • $\begingroup$ I don't think your problem is as hard as preimage resistance. In fact, I don't think it is as hard as collision resistance... $\endgroup$ – cygnusv Feb 20 '15 at 11:52
  • $\begingroup$ @Dillinur: yes, modulo. If not you don't have a group $\endgroup$ – Cédric Van Rompay Feb 20 '15 at 11:59
  • $\begingroup$ BTW, maybe more than "collision by product resistance", your problem is "second preimage by product resistance", since you are fixing $a$ in your problem. $\endgroup$ – cygnusv Feb 20 '15 at 12:06
  • $\begingroup$ @cygnusv: agreed; I just coined the term quickly for the SE question, I don't intend to use that name anywhere anyway. $\endgroup$ – Cédric Van Rompay Feb 20 '15 at 12:09
4
$\begingroup$

Collision and preimage resistance does not imply this; suppose we select a collision and preimage resistant function $H$ with a known value $I$ with $H(I) = 1$ (the group identity); this additional assertion does not contradict the assumptions of collision or preimage resistance. Then, given $a$, we can easily output the tuple $(I, a)$; as we have $H(I) \times H(a) = H(a)$.

In addition, we can see that this problem is strictly easier than preimage or second preimage problems. Suppose that $H$ is a random Oracle, and that the group size is $n$; then, we can solve the problem by selecting $\sqrt{n}$ values of $b$, $c$, and computing two lists consisting of the values $H(b)$ and $H(a)^{-1} \times H(c)$ and looking for a value that occurs in both of the lists, that is entry $i$ of the list $H(b_i)$ is the same as entry $j$ of the list $H(a)^{-1} \times H(c_j)$. If the random Oracle is acts randomly, then with good probability we find a common value; this gives us a pair $(b_i,c_j)$ in $\sqrt{n}$ time; this is faster than we can solve either the preimage or second preimage problem against a random Oracle (which takes $O(n)$ time). If we had a reduction that took fewer than $O(\sqrt{n})$ calls to this problem, this would imply that we could solve the preimage problem faster than $O(n)$, which we know we can't do.

[Note: I updated this paragraph since the answer was accepted]

As for whether this problem is easier than the collision resistance problem (assuming we don't know a magic $I$ with $H(I)=1$), neither problem can be reduced to the other, as one can devise hash functions where one problem is difficult, and the other is easy.

For a hash function for which collision is hard and "preimage by product" is easy, take an RSA modulus $N$ (of secret factorization) and a value $g$ of order $lcm(p-1, q-1)$, and define the hash function $H(x) = g^x \bmod N$ for positive values of $x$ (and asking for $H(0)$ is not allowed; 0 is not positive). Finding two distinct values $x, y$ with $H(x) = H(y)$ is equivalent to factoring $N$, and so that's difficult; however given any $a>1$, we can find the pair $a-1, 1$ with $H(a-1) \times H(1) = H(a)$.

For a hash function for which collision is easy and "preimage by product" is hard, take a random Oracle, and define $H(x) = Oracle(trunc(x))$, where $trunc$ strips off the lsbit of $x$. Then, finding collisions is easy (just output two values that differ only in the lsbit), however solving the "preimage by product" for H is equivalent to solving it for the random Oracle.

My intuition says for realistic hash functions, these problems are likely to be approximately equally difficult; certainly, the generic attacks against collision resistance (forming a list, rho-based approaches) can be adapted to work against your problem.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.