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)$?
It depends on what exactly do you ask for:
- You know such $r$ that $h$=$H(r||k)$ and want to provide someone proof that you know it or
- 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$).
-
$\begingroup$ Thanks for the clarification. I was looking for the second case. $\endgroup$ – robinw Jan 21 '18 at 3:57