Input existence proof for known partial input and hash

Question

Let $h$ signify the hash (Merkle–Damgård construction) generated from some input of known length $n$. Given $h$ and an input $k$ of length $n_1$, is there a way to prove that there exists (does not exist) some (any) $r$ of length $(n-n_1)$ such that $h=H(r||k)$?

Answer 1

It depends on what exactly do you ask for:

1. You know such $r$ that $h$=$H(r||k)$ and want to provide someone proof that you know it or
2. You have only $h$, $H$, $n$ and $k$ and you want to check if $r$ exists

First case should be possible with something like zkSNARKs.

In second case there's no way to do it in polynomial time for any $H$ that is second-preimage attack resistant. Proof:

Let $n_a$ means bit length of $a$. We have some secret input $M$ and $h=H(M)$. Let's assume there exists algorithm $A(H, h, n, k)$, polynomial in terms of security parameter $n$, that :

returns $1$ if there is $r$ such that $h=H(r||k)$ and $n_r=n-n_k$

returns $0$ otherwise.

We can use $A$ to efficiently create collision with $M$ with the same length. In pseudocode:

$M' = \{\}$

for each $1\le i \le n$ do: $M'=A(h, n_M, 1||M')||M'$

After that you have $M'$ that satisfies $H(M')=h=H(M)$ and $n_{M'}=n_M$. So $H$ wouldn't be second-preimage attack resistant.

You can of course iterate through every value of $r$ and check if $h=H(r||k)$ but that takes $2^{n_r}$ steps (in case there's no such $r$).