Skip to main content
added 349 characters in body
Source Link
kodlu
  • 23.7k
  • 2
  • 28
  • 59

Really a comment but more room here for displaymath:

Regarding @MaartenBodewes request for a closed form expression, we can proceed as follows. Since $$(1-2^{-k})^{2^k}\rightarrow \exp(-1)$$ for even moderately large $k$ we can write $$(1-2^{-k})^{2^v}=[ (1-2^{-k})^{2^k} ]^{2^{v-k}}=\exp(-2^{v-k}) $$ so the required expression is $$ 1-\exp(-2^{v-k}) $$ which is extremely sensitive to the difference between $k$ and $v$.

Also, I think the remark about this question having nothing to do with input entropy is a bit too strong. This expression is independent of the input entropy since it essentially uses the random oracle model for the hash function. For a specific hash such as SHA, the entropy would matter but modelling it would be devilishly difficult, I think

Really a comment but more room here for displaymath:

Regarding @MaartenBodewes request for a closed form expression, we can proceed as follows. Since $$(1-2^{-k})^{2^k}\rightarrow \exp(-1)$$ for even moderately large $k$ we can write $$(1-2^{-k})^{2^v}=[ (1-2^{-k})^{2^k} ]^{2^{v-k}}=\exp(-2^{v-k}) $$ so the required expression is $$ 1-\exp(-2^{v-k}) $$ which is extremely sensitive to the difference between $k$ and $v$.

Really a comment but more room here for displaymath:

Regarding @MaartenBodewes request for a closed form expression, we can proceed as follows. Since $$(1-2^{-k})^{2^k}\rightarrow \exp(-1)$$ for even moderately large $k$ we can write $$(1-2^{-k})^{2^v}=[ (1-2^{-k})^{2^k} ]^{2^{v-k}}=\exp(-2^{v-k}) $$ so the required expression is $$ 1-\exp(-2^{v-k}) $$ which is extremely sensitive to the difference between $k$ and $v$.

Also, I think the remark about this question having nothing to do with input entropy is a bit too strong. This expression is independent of the input entropy since it essentially uses the random oracle model for the hash function. For a specific hash such as SHA, the entropy would matter but modelling it would be devilishly difficult, I think

Source Link
kodlu
  • 23.7k
  • 2
  • 28
  • 59

Really a comment but more room here for displaymath:

Regarding @MaartenBodewes request for a closed form expression, we can proceed as follows. Since $$(1-2^{-k})^{2^k}\rightarrow \exp(-1)$$ for even moderately large $k$ we can write $$(1-2^{-k})^{2^v}=[ (1-2^{-k})^{2^k} ]^{2^{v-k}}=\exp(-2^{v-k}) $$ so the required expression is $$ 1-\exp(-2^{v-k}) $$ which is extremely sensitive to the difference between $k$ and $v$.