Let's say I have a collision resistant hash function $H: \{0,1\}^* \rightarrow \{0,1\}^n$ and I want to create another collision resistant hash function $H': \{0,1\}^* \rightarrow \{0,1\}^n$ using $H$ that leaks a bit of input. Would this still constitute a collision resistant hash function?

$$H'(x\mathbin\Vert b) = H(x)_{[1\ldots n-1]} \mathbin\| b$$

(Here, $b$ is a single bit)

  • 1
    $\begingroup$ Welcome to Cryptgraphy.se. What is the origin of this question? What does $[1..n-1]$ means here? $\endgroup$
    – kelalaka
    Nov 7 '20 at 15:06
  • 1
    $\begingroup$ There's no general answer. If n is just on the border of being collision resistant, then truncating 1 bit could make finding a collision feasible. If n is well above that bound, then truncating 1 bit wouldn't hurt. $\endgroup$ Nov 7 '20 at 15:19
  • 2
    $\begingroup$ Hint: assume $G: \{0,1\}^* \rightarrow \{0,1\}^{n-1}$ is a random oracle/function (or perhaps, is to $n$ what SHA3-512 is to 513), thus collision-resistant. Make $H$ a small variation of $G$ that's still collision resistant, but with $H'$ that trivially collides. $\endgroup$
    – fgrieu
    Nov 7 '20 at 15:33
  • 3
    $\begingroup$ @SAIPeregrinus is answering a different question from fgrieu - you are addressing "if $H$ is a random collision resistant hash function, is $H'$ likely to be as well; fgrieu is hinting towards answering the question "if $H$ is an arbitrary CR hash function, is $H'$ guaranteed to be one as well" $\endgroup$
    – poncho
    Nov 7 '20 at 17:50
  • 1
    $\begingroup$ While not a direct duplicate, I think this answers your question. $\endgroup$
    – Maeher
    Nov 8 '20 at 9:21

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.