0
$\begingroup$

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)

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ Welcome to Cryptgraphy.se. What is the origin of this question? What does $[1..n-1]$ means here? $\endgroup$
    – kelalaka
    Nov 7, 2020 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$
    – SAI Peregrinus
    Nov 7, 2020 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, 2020 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, 2020 at 17:50
  • 1
    $\begingroup$ While not a direct duplicate, I think this answers your question. $\endgroup$
    – Maeher
    Nov 8, 2020 at 9:21

0

Reset to default

Your Answer

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

Browse other questions tagged or ask your own question.