Part of the bitcoin mining proof of work is associated with solving a partial preimage problem. For example, output a preimage message $M′$ which computes to a hash value $Y$ with $|Y| = n$ bits where half of the output bits are fixed to 0, $Y =0^{n/2} ∥ Z$ for any $Z$ with $|Z| = n/2$ bits.

• Formalize this partial preimage task for an adversary A (as an advantage probability function).

This is the answer I landed at:
$Adv(A) = Pr(z \leftarrow Z,\ |Z|=n/2,\ Y=0^{n/2} || Z,\ H(M') = Y)$

Am I correct? If not, how can I improve my answer?

  • $\begingroup$ Please remove the useless bolding and use LaTeX, since you seem to know how to use it. $\endgroup$ – fkraiem Nov 22 '16 at 13:44
  • $\begingroup$ The adversary $A$ does not appear in your probability. I'd more likely write this as $\mathsf{Adv}(A) = \mathsf{Pr}[y \gets A(H): \exists z \in \{0,1\}^{n/2}, H(y) = 0^{n/2}||z]$, where $H$ is the hash function, which is given as input to the adversary $A$ in this experiment. $\endgroup$ – Geoffroy Couteau Nov 22 '16 at 18:00

Your Answer

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

Browse other questions tagged or ask your own question.