<p>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 <span class="math-container">$H$</span> as a random oracle (i.e., the random oracle model for hash functions).</p>

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

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

<p>I don't know what the complexity is.  I suspect that for a random matrix <span class="math-container">$A$</span> you might be able to solve this by enumerating solutions to <span class="math-container">$Ax=c$</span>.  You can enumerate solutions using <a href="https://en.wikipedia.org/wiki/Hermite_normal_form" rel="nofollow noreferrer">Hermite normal form</a>.  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 <span class="math-container">$H(x_i)=z_i$</span> 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 <span class="math-container">$A$</span> it will typically take at most exponential time, but I have no proof of this.</p>

<hr>

<p>Alternatively, suppose you intended for "arbitrary cryptographic hash function" to mean that <span class="math-container">$H$</span> is an arbitrary function from the integers to a finite domain.  I'll assume <span class="math-container">$H$</span> is represented as an oracle.</p>

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

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

<hr>

<p>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 <span class="math-container">$H$</span> modelled?  how is it represented and provided as input to the algorithm? etc.).</p>

<hr>

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

CC BY-SA 4.0
2020-02-29T16:15:04.880Z
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
CC BY-SA 4.0
2020-02-29T16:19:55.163Z
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
CC BY-SA 4.0
2020-02-29T20:03:06.643Z
@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.
CC BY-SA 4.0
2020-02-29T23:14:57.477Z
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
CC BY-SA 4.0
2020-03-01T01:27:15.990Z
@NealYoung, sure.  For the upper bound, I think if $\alpha,\alpha'$ are randomly chosen from some large enough space, the chances that they share an input to $H$ are small.  For the lower bound, perhaps the argument (particularly, the footnote) can be modified to accommodate that; I don't know.  I found it easiest to think about with the choice of $u$ I gave.
D.W.
CC BY-SA 4.0
2020-03-01T18:40:21.047Z
Re: the upper bound for random H. (i) Consider the case that the $e$ chosen by your method happens to be, say, $(0,0,0,\ldots,0,1)$.  Then the vectors $d+\alpha e$ it tries will all agree in the first $n-1$ coordinate -- sharing an input to $H$ is guaranteed, and your prob. est. is wrong.  (ii) Looking at https://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pdf, the algorithm described there for putting a matrix in Hermite normal form requires a change of variables.  With the change of variables, the constraints $H(x_i) = z_i$ can no longer be expressed in this form.
Neal Young
CC BY-SA 4.0
2020-03-01T19:03:55.130Z
@NealYoung, thanks for debugging my answer.  I weakened my claims about the upper bound, to focus on the lower bound.
D.W.
CC BY-SA 4.0
2020-02-29T01:30:08.457Z
2020-03-01T19:02:00.797Z
2020-03-01T19:02:00.797Z
D.W.
<p><strong>Introduction:</strong> 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.</p>

<p><strong>Problem:</strong> Let <span class="math-container">$H$</span> be an arbitrary cryptographic hash function. The goal is to solve the following system of linear equations with integer coefficients</p>

<p><span class="math-container">$$\boldsymbol A \boldsymbol x = \boldsymbol c$$</span></p>

<p><span class="math-container">$$\boldsymbol x = \left[\begin{array}{c}
x_1 \\
\vdots \\
x_n
\end{array}\right]$$</span></p>

<p>where the values assigned to the variables are required to be integers and are restricted by the following constraints</p>

<p><span class="math-container">$$H(x_i) = z_i, \hspace{1cm} \text{for } i = 1 \dots n$$</span></p>

<p>where <span class="math-container">$z_i$</span> are arbitrary but fixed hashes.</p>

<p><strong>Question:</strong> What is the time complexity of finding values for <span class="math-container">$\boldsymbol x$</span> that fulfill these constraints? Are there any references that look into problems similar to this one?</p>

<p><strong>Notes:</strong> The problem of finding an <span class="math-container">$x$</span> that fulfills <span class="math-container">$H(x) = z$</span> for an arbitrary <span class="math-container">$z$</span> is in <span class="math-container">$O(1)$</span> because all outputs of <span class="math-container">$H$</span> 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.</p>

CC BY-SA 4.0
2020-02-28T18:00:23.863Z
I forgot to clarify that both the coefficients and the variables need to be integers.
treisenegger
CC BY-SA 4.0
2020-02-28T18:19:00.420Z
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
<cc.complexity-theory><time-complexity><hash-function>
Complexity of solving systems of linear equations with hash preimages
treisenegger
# Complexity of solving systems of linear equations with hash preimages

(Asked by: username_0 on 2020-02-09)

**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.

**Tags:** cc.complexity-theory, time-complexity, hash-function

> **Comments:**
> **username_0**: I forgot to clarify that both the coefficients and the variables need to be integers.  
> **username_1**: 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.  

---

## 1 answers

### Answer by username_2 on 2020-02-29. Score: 1

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](https://en.wikipedia.org/wiki/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)}$.

> **Comments:**
> **username_1**: 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. ?  
> **username_1**: 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_"?  
> **username_2**: @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!  
> **username_1**: 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?  
> **username_2**: @NealYoung, sure.  For the upper bound, I think if $\alpha,\alpha'$ are randomly chosen from some large enough space, the chances that they share an input to $H$ are small.  For the lower bound, perhaps the argument (particularly, the footnote) can be modified to accommodate that; I don't know.  I found it easiest to think about with the choice of $u$ I gave.  
> **username_1**: Re: the upper bound for random H. (i) Consider the case that the $e$ chosen by your method happens to be, say, $(0,0,0,\ldots,0,1)$.  Then the vectors $d+\alpha e$ it tries will all agree in the first $n-1$ coordinate -- sharing an input to $H$ is guaranteed, and your prob. est. is wrong.  (ii) Looking at https://sites.math.rutgers.edu/~sk1233/courses/ANT-F14/lec3.pdf, the algorithm described there for putting a matrix in Hermite normal form requires a change of variables.  With the change of variables, the constraints $H(x_i) = z_i$ can no longer be expressed in this form.  
> **username_2**: @NealYoung, thanks for debugging my answer.  I weakened my claims about the upper bound, to focus on the lower bound.  

---

