4
$\begingroup$

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

$\endgroup$
  • $\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 '17 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 '17 at 20:54
  • $\begingroup$ Check the Keccak pad. $\endgroup$ – Q-Club Oct 19 '17 at 2:32
  • $\begingroup$ @back_seat_driver: Keccak padding rule is not related to this question. It is only applied to the entire sequence if we want to compute its hash, but not used for each block when we apply the inner permutation function. $\endgroup$ – lyrically wicked Oct 19 '17 at 8:07
  • $\begingroup$ @MaartenBodewes: I edited the question. $\endgroup$ – lyrically wicked Oct 19 '17 at 8:28
1
$\begingroup$

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

| improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.