1
$\begingroup$

Just a follow up on this question since I don't have enough point to comment: Does a partial preimage attack imply a preimage attack?

Partial target preimage attack: Given $M$ and t-bit partial target of $d \leftarrow H(M)$, find $M^*$ such that t-bit of $d^* \leftarrow H(M^*)$ is the same as the t-bit of $d$ at the same position.

My question is what best known attacks are.

$\endgroup$
1
$\begingroup$

In the generic setting, a $t$-bit partial preimage attack on an $n$-bit oracle $m \mapsto f(m)$ is the same as a full preimage attack on a $t$-bit oracle $m \mapsto \operatorname{trunc}_t(f(m))$. If $f$ was uniformly distributed in $n$-bit functions, then $\operatorname{trunc}_t \circ f$ is uniformly distributed in $t$-bit functions, so there's no advantage to be had in knowing that it is a truncation of a larger oracle.

Of course, for particular functions $f$, there may be better partial preimage attacks, like $f(0^t \mathbin\| m) = 0^t \mathbin\| \operatorname{trunc}_{n - t}(H(m))$, $f(b \mathbin\| m) = H(m)$. But we would need more particular details about $f$ like this to say.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.