Let $H$ be a hash function that is both hiding and puzzle friendly. Consider $G(z) = H(z) \Vert z_l$ where $z_l$ is the last bit of $z$. Show that $G$ is puzzle frielndly but not hiding.

This question is from this book, page 50). I'm stuck at proving $G$ as non-hiding.

A hash function is hiding if: when a secret value $r$ is chosen from a probability distribution that has a high min-entropy, then given $H(r \Vert x)$ it is infeasible to find $x$.

Now for given function $G$, we have:

$G(r \Vert z) = H(r \Vert z) \Vert z_l$

I don't see how $G$ fails to be hiding. If we are given $G$'s output, we just know about one fixed bit of the input. $H(r \Vert z)$ (the part of the output excluding the last bit) still makes it infeasible to determine $z$ since $H$ is hiding. How can one bit of input prevent $G$ from hiding?


1 Answer 1


What if the input $x$ is only one bit? Would not $G$ leak all of $x$?

In otherwords, the hiding property should work for all plaintext spaces, even if your plaintext space is $\{0,1\}$. $G$ is not hiding for that plaintext space.

  • $\begingroup$ So am I right in understanding that if input's sufficiently large, $G$ still holds the hiding property? $\endgroup$
    – abhink
    Aug 1, 2017 at 19:11
  • 1
    $\begingroup$ @abhink, but the typical definition of a hash function is that it should be able to hash anything. That said, even if the input is 2 bits $\{00,01,10,11\}$, then it would be hiding. If you know the last bit of the input, you would be able to throw out two of the 4 possible inputs, but you would not know which of the remaining it was (beyond any apriori information about distributions about the inputs). $\endgroup$
    – mikeazo
    Aug 1, 2017 at 19:16

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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