Complexity of solving systems of linear equations with hash preimages

Introduction: I'm researching a decision problem that I thought was in NP because there are certificates for its instances that have a polynomial number of elements. However, I realized that there are subproblems one can construct by using hash functions that would probably make this problem fall in a higher complexity class.

Problem: Let $$H$$ be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients

$$\boldsymbol A \boldsymbol x = \boldsymbol c$$

$$\boldsymbol x = \left[\begin{array}{c} x_1 \\ \vdots \\ x_n \end{array}\right]$$

where the values assigned to the variables are required to be integers and are restricted by the following constraints

$$H(x_i) = z_i, \hspace{1cm} \text{for } i = 1 \dots n$$

where $$z_i$$ are arbitrary but fixed hashes.

Question: What is the time complexity of finding values for $$\boldsymbol x$$ that fulfill these constraints? Are there any references that look into problems similar to this one?

Notes: The problem of finding an $$x$$ that fulfills $$H(x) = z$$ for an arbitrary $$z$$ is in $$O(1)$$ because all outputs of $$H$$ have the same size and one could have a table with a precomputed preimage for each hash. Therefore, the additional difficulty would stem from the fact that each hash can have multiple preimages with unbounded sizes. It's pretty easy to see that if any solvable system like this had polynomial-sized solutions the problem would belong to NP. Nevertheless, the fact that there probably isn't any upper bound on the size of the solutions probably means that the problem is infeasible but I can't think of any obvious way to prove this.

• I forgot to clarify that both the coefficients and the variables need to be integers. – treisenegger Feb 28 at 18:00
• OK I've deleted my comment as it no longer applies... So a main thing you are asking is whether any such system always has a solution whose encoding size is polynomial in the size of $A$. I think the description of $H$ is a bit unclear / distracting. It seems we may as well just think of $H$ as an arbitrary function with $O(1)$ distinct outputs -- essentially a partitioning of the integers into $O(1)$ parts, where $H$ is given via an oracle for computing it, and $H(i)$ tells you the part that a given integer $i$ is in. – Neal Young Feb 28 at 18:19

It depends what you mean by "arbitrary cryptographic hash function". If you care about practical cryptography, I think the most natural interpretation is to model $$H$$ as a random oracle (i.e., the random oracle model for hash functions).

In this setting, the problem is hard. As a lower bound, it requires exponential running time.

To prove this, let $$u=(1,2,4,\dots,2^{n-1})$$ and let $$A$$ be a $$n\times n$$ matrix of rank $$n-1$$ such that $$\operatorname{Ker} A$$ is spanned by $$u$$. (Such a matrix exists.) Let $$c=0$$. Then the problem amounts to: find a constant $$\alpha \in \mathbb{Z}$$ such that $$x=\alpha u$$ and $$H(x_i)=z_i$$ for $$i=1,\dots,n$$. Treating $$H$$ as a random oracle, any candidate value of $$\alpha$$ has a $$1/d^n$$ chance of meeting all the $$H(x_i)=z_i$$ requirements, where $$d$$ is the size of the range of $$H$$; so you'll need to try about $$d^n$$ different values of $$\alpha$$ before finding the first that is satisfactory [*]. The size of all integers is at most $$n \log d = \Theta(n)$$ bits, so the time to try each is polynomial. Thus, the total running time is $$2^{\Omega(n)}$$ for this case.

I don't know what the complexity is. I suspect that for a random matrix $$A$$ you might be able to solve this by enumerating solutions to $$Ax=c$$. You can enumerate solutions using Hermite normal form. This equation has either 0 solutions, 1 solution, or infinitely many solutions. If it has no solutions, you can immediately conclude that your problem has no solutions. If it has 1 solution, you can find it with Hermite normal form and then test whether it meets your $$H(x_i)=z_i$$ requirement. If it has infinitely many solutions, you can use Hermite normal form to sample from the space of all solutions and check for each whether it satisfies all of the constraints. There are degenerate cases where this approach might be very inefficient or may never terminate. I suspect for a random matrix $$A$$ it will typically take at most exponential time, but I have no proof of this.

Alternatively, suppose you intended for "arbitrary cryptographic hash function" to mean that $$H$$ is an arbitrary function from the integers to a finite domain. I'll assume $$H$$ is represented as an oracle.

In this case, the problem is undecidable: there is no algorithm that is guaranteed to always terminate and always output the correct answer.

To show this, it suffices to consider the one-dimensional case, $$n=1$$, where $$A=0$$, $$c=0$$, $$z=1$$. Then the problem amounts to: find $$x \in \mathbb{Z}$$ such that $$H(x)=1$$. Consider running the algorithm with the hash function $$H_0$$ defined by $$H_0(x)=0$$ for all $$x$$. Let $$m$$ be the largest number that is queried to the oracle (i.e., the largest number that we use as input to $$H_0$$) when the algorithm is run with $$H_0$$. Define $$H_1$$ by $$H_0(x) = 0$$ if $$x\le m$$, or $$1$$ otherwise. Then the algorithm's behavior on $$H_0$$ and $$H_1$$ is identical, so the algorithm is wrong on at least one of those two.

If neither of those capture what you intended by "arbitrary cryptographic hash function", then you'll need to define your setting more precisely (what are the inputs? how is $$H$$ modelled? how is it represented and provided as input to the algorithm? etc.).

Footnote [*]: I over-simplified a little bit: technically, the attacker could potentially gain up to a $$2n$$ improvement in success probability by using the fact that $$H(\alpha u)$$ tells you something about $$H(2 \alpha u)$$. But this can be accounted for in the proof by treating each query $$w$$ to $$H$$ as providing $$2n$$ guesses at a good $$\alpha$$, for free (namely, $$w/2^{n-1},\dots,w/2,w,2w,\dots,2^{n-1}w$$). In this way, one can adapt the proof to show that you'll need at least about $$d^n/(2n)$$ queries to $$H$$ to have a good chance of finding a valid solution, and that is still $$2^{\Omega(n)}$$.

• Re: the lower bound. Assuming "Id" is the identity matrix, for the given $A$ and $c$, for the constraints $Ax=c$, the solutions are the $x$ of the form $x=(0,0,\ldots,0,\alpha)$ for some integer $\alpha$. Since you are given $z$, you can just check $H(0)$, and if there exists an $i<n$ such that $H(0) \ne z_i$, there cannot be any solution, and you are done. Otherwise, the constraints $H(x_i) = z_i$ for all $i<n$ will be satisfied for any $x$ of the desired form. So you just need to find one $\alpha$ such that $H(\alpha)=z_n$, which seems to be possible in $O(1)$ time. ? – Neal Young Feb 29 at 16:15
• Re: the upper bound. You seem to be assuming $H$ is random. But per the problem statement, $H$ is arbitrary, isn't it? But even for random $H$, for two different $\alpha$, $\alpha'$, and $x=d+\alpha e$, and $x'=d+\alpha' e$, the vectors $x$ and $x'$ may share some values, so the set of events $H(x_i) = z_i$ (for all $i$) and $H(x'_i) = z_i$ (for all $i$) are not independent. So what's the argument that "with high probability one will satisfy all of the $H(x_i)=z_i$ constraints"? – Neal Young Feb 29 at 16:19
• @NealYoung, thanks for all the feedback! I've edited my answer and I think addressed all of your feedback. My lower bound proof was indeed correct; I've fixed it. I made my assumption about the random oracle model explicit, gave some justification, and also studied the only other reasonable assumption I could come up with. Hopefully this improves things? Let me know if I missed anything more. Thank you again! – D.W. Feb 29 at 20:03
• Re: the upper bound for random $H$, it seems to me there is still the technical issue of conditioning that I mentioned in my previous comment. Re: the lower bound for arbitrary $H$, from statements in the post, it seems to me OP has in mind that $H(x) = z_i$ should have a solution for every $z_i$. Or, perhaps another way to think of it is that $H$ is a fixed parameter to the problem. For fixed $H$, the problem is not undecidable. I do think OP needs to clarify the role of $H$ in the problem definition. Re: lower bound for random $H$, can you instead take $u$ to be the first $n$ primes? – Neal Young Feb 29 at 23:14
• @NealYoung, thanks for debugging my answer. I weakened my claims about the upper bound, to focus on the lower bound. – D.W. Mar 1 at 19:03