Hash “Preimage by product” resistance

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.

• 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? – Dillinur Feb 20 '15 at 10:31
• 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... – cygnusv Feb 20 '15 at 11:52
• @Dillinur: yes, modulo. If not you don't have a group – Cédric Van Rompay Feb 20 '15 at 11:59
• BTW, maybe more than "collision by product resistance", your problem is "second preimage by product resistance", since you are fixing $a$ in your problem. – cygnusv Feb 20 '15 at 12:06
• @cygnusv: agreed; I just coined the term quickly for the SE question, I don't intend to use that name anywhere anyway. – Cédric Van Rompay Feb 20 '15 at 12:09

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.