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.
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)}$.