# Collisions of a compression function

I tried posting this in the math forum but I didn't get any responses. I was hoping someone could give me some advice for how to approach the following problem.

If $n$ is a positive integer, let $S_n$ denote the group of permutations of the set $\{1,2,\dots, n\}$. For a permutation $\pi$ in $S_3$, let $e_\pi$ be the bit permutation of bit strings of length 3. For each $\pi \in S_3$ determine the number of collisions of the compression function $h(x) = e_\pi(x) \oplus x$.

Does anyone have any advice on how to approach this?

• Please give a link to your former question. Also, this seems to be a homework problem, so let me ask the obligatory question: what have you tried, where are you stuck? – Raphael Apr 23 '13 at 17:47
• Hi Raphael, my old question is here: math.stackexchange.com/questions/366678/… – willow Apr 23 '13 at 18:31
• And I realized that I think my confusion is about what is referred to as $\pi$ and what is referred to as $e_\pi$. If there are 8 different bit strings of length 3, then is $e_\pi$ just taking each of these bit strings and rearranging the bits according to one of the 6 different possible arrangements of the set $\{1,2,3\}$? E.g. if I choose $\pi \in S_3$ to be $\{1,2,3\} \to \{1,3,2\}$, then for the bit string 001 is $e_\pi$ just 010? Thanks a lot! – willow Apr 23 '13 at 18:50