Let $F$ denote a function that returns the first $800$ bits of the input.

Let $G(N)$ denote a function that returns the last $800$ bits of the binary encoding of the given number $N$. For example,

$$\begin{array}{l} G(0) = 00\underbrace \ldots _{{\rm{796\;zeroes}}}00,\\ G(1) = 00\underbrace \ldots _{{\rm{796\;zeroes}}}01,\\ G({2^{800}} - 2) = 11\underbrace \ldots _{{\rm{796\;ones}}}10,\\ G({2^{800}} - 1) = 11\underbrace \ldots _{{\rm{796\;ones}}}11 \end{array}$$

etc (we are only interested in the interval $0 \le N \lt {2^{800}}$ ).

Let $P$ denote Keccak permutation function that operates on $1600$-bit blocks.

Choose (arbitrarily or randomly) any 800-bit sequence. Denote it by $S$.

Consider the following collection (set) of bitsequences:

$$\begin{array}{l} {C} = \{ &F(P(G(0)|| S)),\\&F (P(G(1) || S)),\\&F(P(G(2) || S)),\\&\ldots ,\\&F(P(G({2^{800}} - 2) || S)),\\&F(P(G({2^{800}} - 1) || S))\;\;\} \end{array}$$

(it contains $2^{800}$ elements, and each element is a $800$-bit sequence).

Let $Y$ denote the number of different (unique) elements in $C$.

Question: what is the expected value of $Y$? And why?

Edit: I have read Expected number of different birthdays, and found the following formula:

$$\begin{array}{l}\\& D = 2^{1600},\\& n = 2^{800},\\& \varphi = (D-1)/D,\\& Y = D\times (1-\varphi^n) \end{array}$$

Is this the correct formula for $Y$?

  • $\begingroup$ What do you think that Y should be and why? Because home work dumps are usually not met with a great deal of enthusiasm without some kind of indication of effort. $\endgroup$
    – Maarten Bodewes
    Oct 18, 2017 at 20:49
  • $\begingroup$ Hint: a permutation will result in a unique output for unique input. However, part of a permutation will not be unique. For cryptographic permutations you would expect well distributed output. So for calculating the number of collisions you need to take the birthday paradox into account. $\endgroup$
    – Maarten Bodewes
    Oct 18, 2017 at 20:54
  • $\begingroup$ this might also help you. $\endgroup$
    – Biv
    Oct 19, 2017 at 8:31

1 Answer 1


Every input $G(i) \mathbin\| S$ to $P$ is distinct. If $P$ were a uniform random permutation, the random function $x \mapsto F(P(x))$ would have almost uniform distribution. So the answer can't be much different from the number of distinct 800-bit strings in an independent uniform random sampling of $2^{800}$ of them, which is a fraction of $$1 - (1 - 1/2^{800})^{2^{800}} \approx 1 - e^{-1}$$ of them by the usual reason. The fact that $S$ is chosen independently at random is not relevant to this analysis; the same analysis would apply if $S = 0$.


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.