# What is the expected number of different sequences of bits in the collection that contains $2^{800}$ elements?

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$?

• 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. Oct 18, 2017 at 20:49
• 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. Oct 18, 2017 at 20:54
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$$.